Search

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1 / 2 -approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively. Unfortunately, a recent work Konrad and Naidu (Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX/RANDOM 2021, August 16–18, 2021. LIPIcs, vol 207, pp 19:1–19:18, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.19) shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1 / 2 -approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms were previously known, and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs. The main significance of our results is not in the numerical improvements, but in demonstrating the potential of non-maximal-matching-first algorithms. [ABSTRACT FROM AUTHOR]

They give fixed parameter tractable algorithms for the problem parameterized by various structural parameters. The authors give a greedy loop-free algorithm for the exhaustive generation, a successor algorithm that runs in constant amortized time, among other algorithms, as well as results for the fixed spin generalization of this problem. IWOCA (International Workshop on Combinatorial Algorithms) is an annual conference series covering all aspects of combinatorial algorithms. [Extracted from the article]

In this paper we study the computational complexity issues of the problem of secondary domination (known also as (1, 2)-domination) in several graph classes. We also study the computational complexity of the problem of determining whether the domination and secondary domination numbers are equal. In particular, we study the influence of triangles and vertices of degree 1 on these numbers. Also, an optimal algorithm for finding a minimum secondary dominating set in trees is presented. [ABSTRACT FROM AUTHOR]

We revisit the problem of finding a 1-restricted simple 2-matching of maximum cardinality. Recall that, given an undirected graph G = (V , E) , a simple 2-matching is a subset M ⊆ E of edges such that each node in V is incident to at most two edges in M . Clearly, each such M decomposes into a node-disjoint collection of paths and circuits. M is called 1-restricted if it contains no isolated edges (i.e. paths of length one). A combinatorial polynomial algorithm for finding such M of maximum cardinality and also a min-max relation were devised by Hartvigsen. It was shown that finding such M amounts to computing a (not necessarily 1-restricted) simple 2-matching M 0 of maximum cardinality and subsequently altering it into M of the same cardinality so as to minimize the number of isolated edges. While the first phase (which computes M 0 ) runs in O E V time, the second one (which turns M 0 into M ) requires O (V E) time. In this paper we apply the general blocking augmentation approach (initially introduced, e.g., for bipartite matchings by Hopcroft and Karp, and also by Dinic) and present a novel algorithm that reduces the time needed for the second phase to O E V thus completely closing the gap between 1-restricted and unrestricted cases. [ABSTRACT FROM AUTHOR]

A k-page upward book embedding (kUBE) of a directed acyclic graph G is a book embeddings of G on k pages with the additional requirement that the vertices appear in a topological ordering along the spine of the book. The kUBE Testing problem, which asks whether a graph admits a kUBE, was introduced in 1999 by Heath, Pemmaraju, and Trenk (SIAM J Comput 28(4), 1999). In a companion paper, Heath and Pemmaraju (SIAM J Comput 28(5), 1999) proved that the problem is linear-time solvable for k = 1 and NP-complete for k = 6 . Closing this gap has been a central question in algorithmic graph theory since then. In this paper, we make a major contribution towards a definitive answer to the above question by showing that kUBE Testing is NP-complete for k ≥ 3 , even for st-graphs, i.e., acyclic directed graphs with a single source and a single sink. Indeed, our result, together with a recent work of Bekos et al. (Theor Comput Sci 946, 2023) that proves the NP-completeness of 2UBE for planar st-graphs, closes the question about the complexity of the kUBE problem for any k. Motivated by this hardness result, we then focus on the 2UBE Testing for planar st-graphs. On the algorithmic side, we present an O (f (β) · n + n 3) -time algorithm for 2UBE Testing, where β is the branchwidth of the input graph and f is a singly-exponential function on β . Since the treewidth and the branchwidth of a graph are within a constant factor from each other, this result immediately yields an FPT algorithm for st-graphs of bounded treewidth. Furthermore, we describe an O(n)-time algorithm to test whether a plane st-graph whose faces have a special structure admits a 2UBE that additionally preserves the plane embedding of the input st-graph. On the combinatorial side, we present two notable families of plane st-graphs that always admit an embedding-preserving 2 UBE. [ABSTRACT FROM AUTHOR]

Surrogate functions are often employed to reduce the number of objective function evaluations in a continuous optimization. However, their effects have seldom been investigated theoretically. This paper analyzes the effect of a surrogate function in the information-geometric optimization (IGO) framework, which includes as an algorithm instance a variant of the covariance matrix adaptation evolution strategy—a widely used solver for black-box continuous optimization. We derive a sufficient condition on the surrogate function for the parameter update in the IGO algorithms to point to a descent direction of the objective function expected over the search distribution. The condition is expressed in terms of three measures of correlation between the objective function and the surrogate function. Our result constitutes a partial justification for the use of a surrogate function in IGO algorithms. [ABSTRACT FROM AUTHOR]

A function f : V (G) → { 0 , 1 , 2 } is called a Roman dominating function on G = (V (G) , E (G)) if for every vertex v with f (v) = 0 , there exists a vertex u ∈ N G (v) such that f (u) = 2 . A function f : V (G) → { 0 , 1 , 2 } induces an ordered partition (V 0 , V 1 , V 2) of V(G), where V i = { v ∈ V (G) : f (v) = i } for i ∈ { 0 , 1 , 2 } . A function f : V (G) → { 0 , 1 , 2 } with ordered partition (V 0 , V 1 , V 2) is called a unique response Roman function if for every vertex v with f (v) = 0 , | N G (v) ∩ V 2 | ≤ 1 , and for every vertex v with f (v) = 1 or 2, | N G (v) ∩ V 2 | = 0 . A function f : V (G) → { 0 , 1 , 2 } is called a unique response Roman dominating function (URRDF) on G if it is a unique response Roman function as well as a Roman dominating function on G. The weight of a unique response Roman dominating function f is the sum f (V (G)) = ∑ v ∈ V (G) f (v) , and the minimum weight of a unique response Roman dominating function on G is called the unique response Roman domination number of G and is denoted by u R (G) . Given a graph G, the Min-URRDF problem asks to find a unique response Roman dominating function of minimum weight on G. In this paper, we study the algorithmic aspects of Min-URRDF. We show that the decision version of Min-URRDF remains NP-complete for chordal graphs and bipartite graphs. We show that for a given graph with n vertices, Min-URRDF cannot be approximated within a ratio of n 1 - ε for any ε > 0 unless P = NP . We also show that Min-URRDF can be approximated within a factor of Δ + 1 for graphs having maximum degree Δ . On the positive side, we design a linear-time algorithm to solve Min-URRDF for distance-hereditary graphs. Also, we show that Min-URRDF is polynomial-time solvable for interval graphs, and strengthen the result by showing that Min-URRDF can be solved in linear-time for proper interval graphs, a proper subfamily of interval graphs. [ABSTRACT FROM AUTHOR]

Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form L x = b , where L is the Laplacian matrix of a weighted graph with weights w (i , j) > 0 on the edges. The solution x of the linear system can be interpreted as the potentials of an electrical flow in which the resistance on edge (i, j) is 1/w(i, j). Kelner et al. (in: Proceedings of the 45th Annual ACM Symposium on the Theory of Computing, pp 911–920, 2013. https://doi.org/10.1145/2488608.2488724) give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a near-linear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vector–matrix-vector problem, which has been conjectured to be difficult for dynamic algorithms (Henzinger et al., in: Proceedings of the 47th Annual ACM Symposium on the Theory of Computing, pp 21–30, 2015. https://doi.org/10.1145/2746539.2746609). The conjecture implies that the data structure does not have an O (n 1 - ϵ) time algorithm for any ϵ > 0 , and thus a straightforward implementation of the cut-toggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an O ~ (m 1.5) time cut-toggling algorithm for solving Laplacian systems. Furthermore, we show that if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, we can reduce the running time to O (m 1 + ϵ) for any ϵ > 0 . Thus, the dual cut-toggling algorithm can achieve (almost) the same running time as its primal cycle-toggling counterpart. [ABSTRACT FROM AUTHOR]

When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be huge, including sometimes exponential. Furthermore, depending on the application, many of these solutions can be considered equivalent. The problem of an efficient enumeration of the equivalence classes or of one representative per class (without generating all the solutions), although identified as a need in many areas, has been addressed only for very few specific cases. In this paper, we provide a general framework that solves this problem in polynomial delay for a wide variety of optimization problems solvable by dynamic programming algorithms, and for certain types of equivalence relations between solutions. [ABSTRACT FROM AUTHOR]

Solving problems on graphs dynamically calls for algorithms to function under repeated modifications to the graph and to be more efficient than solving the problem for the whole graph from scratch after each modification. Dynamic algorithms have been considered for several graph properties, for example connectivity, shortest paths and graph recognition. In this paper we present fully dynamic algorithms for the recognition of threshold graphs and chain graphs, which are optimal in the sense that the costs per modification are linear in the number of modified edges. Furthermore, our algorithms also consider the addition and deletion of sets of vertices as well as edges. In the negative case, i.e., where the graph is not a threshold graph or chain graph anymore, our algorithms return a certificate of constant size. Additionally, we present optimal fully dynamic algorithms for the Hamiltonian cycle problem and the Hamiltonian path problem on threshold and chain graphs which return a vertex cutset as certificate for the non-existence of such a path or cycle in the negative case. [ABSTRACT FROM AUTHOR]

Fradkin and Seymour (J Comb Theory Ser B 110:19–46, 2015) defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of bounded independence number is structured enough to be exploited algorithmically. In this paper, we further strengthen this belief by showing that several cut problems that admit sub-exponential time parameterized algorithms (a trait uncommon to parameterized algorithms) on tournaments, including Directed Feedback Arc Set, Directed Cutwidth and Optimal Linear Arrangement, also admit such algorithms on digraphs of bounded independence number. Towards this, we rely on the generic approach of Fomin and Pilipczuk (in: Proceedings of the Algorithms—ESA 2013—21st Annual European Symposium, Sophia Antipolis, France, September 2–4, 2013, pp. 505–516, 2013), where to get the desired algorithms, it is enough to bound the number of k-cuts in digraphs of bounded independence number by a sub-exponential FPT function (Fomin and Pilipczuk bounded the number of k-cuts in transitive tournaments). Specifically, our main technical contribution is a combinatorial result that proves that the yes-instances of the problems (defined above) have a sub-exponential number of k-cuts. We prove this bound by using a combination of chromatic coding, inductive reasoning and exploiting the structural properties of these digraphs. [ABSTRACT FROM AUTHOR]

In this paper, we initiate the study of average-case complexity and circuit analysis algorithms for comparator circuits. Departing from previous approaches, we exploit the technique of shrinkage under random restrictions to obtain a variety of new results for this model. Among them, we show Average-case Lower Bounds For every k = k (n) with k ⩾ log n , there exists a polynomial-time computable function f k on n bits such that, for every comparator circuit C with at most n 1.5 / O k · log n gates, we have Pr x ∈ 0 , 1 n C (x) = f k (x) ⩽ 1 2 + 1 2 Ω (k) . This average-case lower bound matches the worst-case lower bound of Gál and Robere by letting k = O log n . # SAT Algorithms There is an algorithm that counts the number of satisfying assignments of a given comparator circuit with at most n 1.5 / O k · log n gates, in time 2 n - k · poly (n) , for any k ⩽ n / 4 . The running time is non-trivial (i.e., 2 n / n ω (1) ) when k = ω (log n) . Pseudorandom Generators and MCSP Lower Bounds There is a pseudorandom generator of seed length s 2 / 3 + o (1) that fools comparator circuits with s gates. Also, using this PRG, we obtain an n 1.5 - o (1) lower bound for MCSP against comparator circuits. [ABSTRACT FROM AUTHOR]

In this work, we introduce a multi-vehicle (or multi-postman) extension of the classical Mixed Rural Postman Problem, which we call the Min–Max Mixed Rural Postmen Cover Problem (MRPCP). The MRPCP is defined on a mixed graph G = (V , E , A) , where V is the vertex set, E denotes the (undirected) edge set and A represents the (directed) arc set. Let F ⊆ E ( H ⊆ A ) be the set of required edges (required arcs). There is a nonnegative weight associated with each edge and arc. The objective is to determine no more than k closed walks to cover all the required edges in F and all the required arcs in H such that the weight of the maximum weight closed walk is minimized. By replacing closed walks with (open) walks in the MRPCP, we obtain the Min–Max Mixed Rural Postmen Walk Cover Problem (MRPWCP). The Min–Max Mixed Chinese Postmen Cover Problem (MCPCP) is a special case of the MRPCP where F = E and H = A . The Min–Max Stacker Crane Cover Problem (SCCP) is another special case of the MRPCP where F = ∅ and H = A For the MRPCP with the input graph satisfying the weakly symmetric condition, i.e., for each arc there exists a parallel edge whose weight is not greater than this arc, we devise a 27 4 -approximation algorithm. This algorithm achieves an approximation ratio of 33 5 for the SCCP with the weakly symmetric condition. Moreover, we obtain the first 5-approximation algorithm (4-approximation algorithm) for the MRPWCP (MCPCP) with the weakly symmetric condition. [ABSTRACT FROM AUTHOR]

We would like to thank the authors for contributing their manuscripts, the referees for thoroughly reviewing these articles and the WADS 2021 program committee for helping with the selection of these articles. This special issue is dedicated to selected papers from those presented at the 17th Algorithms and Data Structures Symposium (WADS 2021), which was held from August 9-11 fully online. [Extracted from the article]

A 2-dimensional lattice animal is a set of edge-connected cells on some lattice. In this paper, we address the problem of counting minimum-perimeter lattice animals, that is, animals that have the minimum possible perimeter of all animals of the same area. We provide two types of algorithms for counting minimum-perimeter animals on two lattices, namely, the square and hexagonal lattices, and analyze and compare the algorithms. [ABSTRACT FROM AUTHOR]

In the general max–min fair allocation problem, there are m players and n indivisible resources, each player has his/her own utilities for the resources, and the goal is to find an assignment that maximizes the minimum total utility of resources assigned to a player. The problem finds many natural applications such as bandwidth distribution in telecom networks, processor allocation in computational grids, and even public-sector decision making. We introduce an over-estimation strategy to design approximation algorithms for this problem. When all utilities are positive, we obtain an approximation ratio of c 1 - ϵ , where c is the maximum ratio of the largest utility to the smallest utility of any resource. When some utilities are zero, we obtain an approximation ratio of (1 + 3 c ^ + O (δ c ^ 2)) , where c ^ is the maximum ratio of the largest utility to the smallest positive utility of any resource. [ABSTRACT FROM AUTHOR]

We prove that Simulated Annealing with an appropriate cooling schedule computes arbitrarily tight constant-factor approximations to the minimum spanning tree problem in polynomial time. This result was conjectured by Wegener (Automata, Languages and Programming, ICALP, Berlin, 2005). More precisely, denoting by n , m , w max , and w min the number of vertices and edges as well as the maximum and minimum edge weight of the MST instance, we prove that simulated annealing with initial temperature T 0 ≥ w max and multiplicative cooling schedule with factor 1 - 1 / ℓ , where ℓ = ω (m n ln (m)) , with probability at least 1 - 1 / m computes in time O (ℓ (ln ln (ℓ) + ln (T 0 / w min))) a spanning tree with weight at most 1 + κ times the optimum weight, where 1 + κ = (1 + o (1)) ln (ℓ m) ln (ℓ) - ln (m n ln (m)) . Consequently, for any ϵ > 0 , we can choose ℓ in such a way that a (1 + ϵ) -approximation is found in time O ((m n ln (n)) 1 + 1 / ϵ + o (1) (ln ln n + ln (T 0 / w min))) with probability at least 1 - 1 / m . In the special case of so-called (1 + ϵ) -separated weights, this algorithm computes an optimal solution (again in time O ((m n ln (n)) 1 + 1 / ϵ + o (1) (ln ln n + ln (T 0 / w min))) ), which is a significant speed-up over Wegener's runtime guarantee of O (m 8 + 8 / ϵ) . Our tighter upper bound also admits the result that in some situations a hybridization of simulated annealing and the (1 + 1) EA can lead to stronger runtime guarantees than either algorithm alone. [ABSTRACT FROM AUTHOR]

While the theoretical analysis of evolutionary algorithms (EAs) has made significant progress for pseudo-Boolean optimization problems in the last 25 years, only sporadic theoretical results exist on how EAs solve permutation-based problems. To overcome the lack of permutation-based benchmark problems, we propose a general way to transfer the classic pseudo-Boolean benchmarks into benchmarks defined on sets of permutations. We then conduct a rigorous runtime analysis of the permutation-based (1 + 1) EA proposed by Scharnow et al. (J Math Model Algorithm 3:349–366, 2004) on the analogues of the LeadingOnes and Jump benchmarks. The latter shows that, different from bit-strings, it is not only the Hamming distance that determines how difficult it is to mutate a permutation σ into another one τ , but also the precise cycle structure of σ τ - 1 . For this reason, we also regard the more symmetric scramble mutation operator. We observe that it not only leads to simpler proofs, but also reduces the runtime on jump functions with odd jump size by a factor of Θ (n) . Finally, we show that a heavy-tailed version of the scramble operator, as in the bit-string case, leads to a speed-up of order m Θ (m) on jump functions with jump size m. A short empirical analysis confirms these findings, but also reveals that small implementation details like the rate of void mutations can make an important difference. [ABSTRACT FROM AUTHOR]

We study the Non-preemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Non-preemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a (5 / 3 + ε) -approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption (1 + ε) OPT . The remaining jobs fit into a thin container of height 1. This AEPTAS is used as a subroutine to acquire the (5 / 3 + ε) -approximation algorithm. The previous best result for NPDM was a 2.7-approximation based on FFDH (Ranjan et al., in: 2015 IEEE symposium on computers and communication (ISCC), pp 758–763, IEEE, 2015). One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg's algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above, such that it does not exceed the bound of (5 / 3 + ε) OPT . [ABSTRACT FROM AUTHOR]

This paper is concerned with the 1 | | ∑ p j U j problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental scheduling problem, but also an important problem from a theoretical point of view as it generalizes the Subset Sum problem and is closely related to the 0/1-Knapsack problem. The problem is well-known to be NP-hard, but only in a weak sense, meaning it admits pseudo-polynomial time algorithms. The best known running time follows from the famous Lawler and Moore algorithm that solves a more general weighted version in O (P · n) time, where P is the total processing time of all n jobs in the input. This algorithm has been developed in the late 60s, and has yet to be improved to date. In this paper we develop two new algorithms for problem, each improving on Lawler and Moore's algorithm in a different scenario. Our first algorithm runs in O ~ (P 7 / 4) time, and outperforms Lawler and Moore's algorithm in instances where n = ω ~ (P 3 / 4) . Our second algorithm runs in O ~ (min { P · D # , P + D }) time, where D # is the number of different due dates in the instance, and D is the sum of all different due dates. This algorithm improves on Lawler and Moore's algorithm when n = ω ~ (D #) or n = ω ~ (D / P) . Further, it extends the known O ~ (P) algorithm for the single due date special case of 1 | | ∑ p j U j in a natural way. Both algorithms rely on basic primitive operations between sets of integers and vectors of integers for the speedup in their running times. The second algorithm relies on fast polynomial multiplication as its main engine, and can be easily extended to the case of a fixed number of machines. For the first algorithm we define a new "skewed" version of (max , min) -Convolution which is interesting in its own right. [ABSTRACT FROM AUTHOR]

In this paper, we study the following pattern search problem: Given a pair of point sets A and B in fixed dimensional space R d , with | B | = n , | A | = m and n ≥ m , the pattern search problem is to find the translations T 's of A such that each of the identified translations induces a matching between T (A) and a subset B ′ of B with cost no more than some given threshold, where the cost is defined as the minimum bipartite matching cost of T (A) and B ′ . We present a novel algorithm to produce a small set of candidate translations for the pattern search problem. For any B ′ ⊆ B with | B ′ | = | A | , there exists at least one translation T in the candidate set such that the minimum bipartite matching cost between T (A) and B ′ is no larger than (1 + ϵ) times the minimum bipartite matching cost between A and B ′ under any translation (i.e., the optimal translational matching cost). We also show that there exists an alternative solution to this problem, which constructs a candidate set of size O d , ϵ (n log 2 n) in O d , ϵ (n log 2 n) time with high probability of success. As a by-product of our construction, we obtain a weak ϵ -net for hypercube ranges, which significantly improves the construction time and the size of the candidate set. Our technique can be applied to a number of applications, including the translational pattern matching problem. [ABSTRACT FROM AUTHOR]

We design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called Minimum Weight λ -connected Spanning Subgraph and (ii) augmenting a given network to a desired value of edge connectivity at a minimum cost which is called Minimum Weight λ -connectivity Augmentation. It is easy to see that a minimum solution to these problems contains at most 2 λ (n - 1) edges. Using this fact one can design a brute-force algorithm which runs in time 2 O (λ n log n) , however no better algorithms were known previously. In this paper, we give the first single exponential time algorithm for these problems, i.e. running in time 2 O (λ n) , for both undirected and directed networks. Our results are obtained via well known characterizations of λ -connected graphs, their connections to linear matroids and the recently developed technique of dynamic programming with representative sets. [ABSTRACT FROM AUTHOR]

For a non-negative integer ℓ , the ℓ -leaf power of a tree T is a simple graph G on the leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most ℓ . We provide a polynomial kernel for the problem of deciding whether we can delete at most k vertices to make an input graph a 3-leaf power of some tree. More specifically, we present a polynomial-time algorithm for an input instance (G, k) for the problem to output an equivalent instance (G ′ , k ′) such that k ′ ⩽ k and G ′ has at most O (k 14) vertices. [ABSTRACT FROM AUTHOR]

The challenge for graph matching algorithms is to extend known time bounds for bipartite graphs to general graphs. We discuss combinatorial algorithms for finding a maximum weight f-factor on an arbitrary multigraph, for given integral weights of magnitude at most W. (An f-factor is a subgraph whose degree function is the given function f : V → N .) For simple bipartite graphs the best-known time bound for combinatorial algorithms is O (n 2 / 3 m log n W) [Gabow and Tarjan, SIAM J Comput 18(5):1013–1036, 1989; n and m are respectively the number of vertices and edges.] A recent algorithm of Duan et al. [in: Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 2020] for f-factors of simple general graphs comes within logarithmic factors of this bound, O ~ (n 2 / 3 m log W) . The best-known bound for bipartite multigraphs is O (Φ m log Φ W) ( Φ ≤ m is the size of the f-factor, Φ = ∑ v ∈ V f (v) / 2 ). This bound is more general than the restriction to simple graphs, and is even superior on "small" simple graphs, i.e., Φ = o (n 4 / 3) . We present an algorithm that comes within a log Φ factor of this bound, i.e., O (Φ log Φ m log Φ W) . The algorithm is a direct generalization of the algorithm of Gabow and Tarjan [J ACM 38(4):815–853, 1991] for the special case of ordinary matching ( f ≡ 1 ). We present that algorithm first. Our analysis is a simplified and more concrete version of Gabow and Tarjan [J ACM 38(4):815–853, 1991] and has independent interest. Furthermore the algorithm and analysis are both incorporated, without modification, into the f-factor algorithm. To extend these ideas to f-factors, the first step is "expanding" edges (i.e., replacing an edge by a length 3 alternating path). Duan et al. [in: Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 2020] uses a one-time expansion of the entire graph. In contrast, our algorithm keeps the graph small by only expanding selected edges (edges incident to blossoms, in "I(B) sets"). Expanded edges get "compressed" back to their source when no longer needed. Expansion necessitates using an alternate graph model for blossoms (we call them "e-blossoms"). Compression requires coordinating e-blossoms with standard blossoms. [ABSTRACT FROM AUTHOR]

Refereed conferences require every submission to be reviewed by members of a program committee (PC) in charge of selecting the conference program. There are many software packages available to manage the review process. Typically, in a bidding phase PC members express their personal preferences by ranking the submissions. This information is used by the system to compute an assignment of the papers to referees (PC members). We study the problem of assigning papers to referees. We propose to optimize a number of criteria that aim at achieving fairness among referees/papers. Some of these variants can be solved optimally in polynomial time, while others are NP-hard, in which case we design approximation algorithms. Experimental results strongly suggest that the assignments computed by our algorithms are considerably better than those computed by popular conference management software. [ABSTRACT FROM AUTHOR]

We consider the following dynamic load-balancing process: given an underlying graph G with n nodes, in each step t ≥ 0 , a random edge is chosen, one unit of load is created, and placed at one of the endpoints. In the same step, assuming that loads are arbitrarily divisible, the two nodes balance their loads by averaging them. We are interested in the expected gap between the minimum and maximum loads at nodes as the process progresses, and its dependence on n and on the graph structure. Peres et al. (Random Struct Algorithms 47(4):760–775, 2015) studied the variant of this process, where the unit of load is placed in the least loaded endpoint of the chosen edge, and the averaging is not performed. In the case of dynamic load balancing on the cycle of length n the only known upper bound on the expected gap is of order O (n log n) , following from the majorization argument due to the same work. In this paper, we leverage the power of averaging and provide an improved upper bound of O (n log n) . We introduce a new potential analysis technique, which enables us to bound the difference in load between k-hop neighbors on the cycle, for any k ≤ n / 2 . We complement this with a "gap covering" argument, which bounds the maximum value of the gap by bounding its value across all possible subsets of a certain structure, and recursively bounding the gaps within each subset. We also show that our analysis can be extended to the specific instance of Harary graphs. On the other hand, we prove that the expected second moment of the gap is lower bounded by Ω (n) . Additionally, we provide experimental evidence that our upper bound on the gap is tight up to a logarithmic factor. [ABSTRACT FROM AUTHOR]

A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. In this paper, we study the problem of computing MUSs for a sliding window over a given string T. We first show how the set of MUSs can change when the window slides over T. We then present an O (n log σ ′) -time and O(d)-space algorithm to compute MUSs for a sliding window of size d over the input string T of length n, where σ ′ ≤ d is the maximum number of distinct characters in every window. [ABSTRACT FROM AUTHOR]

The problem of merging sorted lists in the least number of pairwise comparisons has been solved completely only for a few special cases. Graham and Karp (Sorting Search 3:197–207, 1999) independently discovered that the tape merge algorithm is optimal in the worst case when the two lists have the same size. In their seminal papers, Stockmeyer and Yao (SIAM J Comput 9(1):85–90, 1980), Murphy and Paull (Inf Control 42(1):87–96, 1979), and Christen (On the optimality of the straight merging algorithm, 1978) independently showed when the lists to be merged are of size m and n satisfying m ≤ n ≤ ⌊ 3 2 m ⌋ + 1 , the tape merge algorithm is optimal in the worst case. This paper extends this result by showing that the tape merge algorithm is optimal in the worst case whenever the size of one list is no larger than 1.52 times the size of the other. The main tool we use to prove the lower bound is Knuth's (1999) adversary methods. In addition, we show that the lower bound cannot be improved to 1.8 via Knuth's adversary methods. Moreover, we design a simple procedure, and by invoking this procedure recursively until the remaining subproblem can be solved efficiently by another known algorithm, we achieve constant improvement of the upper bound for 2 m - 2 ≤ n ≤ 3 m . [ABSTRACT FROM AUTHOR]

In this paper we study regular expression matching in cases in which the identity of the symbols received is subject to uncertainty. We develop a model of symbol emission and uses a modification of the shortest path algorithm to find optimal matches on the Cartesian Graph of an expression provided that the input is a finite list. In the case of infinite streams, we show that the problem is in general undecidable but, if each symbols is received with probability 0 infinitely often, then with probability 1 the problem is decidable. [ABSTRACT FROM AUTHOR]

In the classic minimum makespan scheduling problem, we are given an input sequence of n jobs with sizes. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. In this paper, we consider online scheduling algorithms without preemption. However, we allow the online algorithm to change the assignment of up to k jobs at the end for some limited number k. For m identical machines, Albers and Hellwig (Algorithmica 79(2):598–623, 2017) give tight bounds on the competitive ratio in this model. The precise ratio depends on, and increases with, m. It lies between 4/3 and ≈ 1.4659 . They show that k = O (m) is sufficient to achieve this bound and no k = o (n) can result in a better bound. We study m uniform machines, i.e., machines with different speeds, and show that this setting is strictly harder. For sufficiently large m, there is a δ = Θ (1) such that, for m machines with only two different machine speeds, no online algorithm can achieve a competitive ratio of less than 1.4659 + δ with k = o (n) . We present a new algorithm for the uniform machine setting. Depending on the speeds of the machines, our scheduling algorithm achieves a competitive ratio that lies between 4/3 and ≈ 1.7992 with k = O (m) . We also show that k = Ω (m) is necessary to achieve a competitive ratio below 2. Our algorithm is based on maintaining a specific imbalance with respect to the completion times of the machines, complemented by a bicriteria approximation algorithm that minimizes the makespan and maximizes the average completion time for certain sets of machines. [ABSTRACT FROM AUTHOR]

Randomized search heuristics such as evolutionary algorithms are frequently applied to dynamic combinatorial optimization problems. Within this paper, we present a dynamic model of the classic weighted vertex cover problem and analyze the runtime performances of the well-studied algorithms randomized local search and (1 + 1) EA adapted to it, to contribute to the theoretical understanding of evolutionary computing for problems with dynamic changes. In our investigations, we use an edge-based representation based on the dual form of the Linear Programming formulation for the problem and study the expected runtime that the adapted algorithms require to maintain a 2-approximate solution when the given weighted graph is modified by an edge-editing or weight-editing operation. Considering the weights on the vertices may be exponentially large with respect to the size of the graph, the step size adaption strategy is incorporated, with or without the 1/5-th rule that is employed to control the increasing/decreasing rate of the step size. Our results show that three of the four algorithms presented in the paper can recompute 2-approximate solutions for the studied dynamic changes in polynomial expected runtime, but the (1 + 1) EA with 1/5-th rule requires pseudo-polynomial expected runtime. [ABSTRACT FROM AUTHOR]

This work introduces scheduling algorithms to maximize the expected number of independent tasks that can be executed on a parallel platform within a given budget and under a deadline constraint. The main motivation for this problem comes from imprecise computations, where each job has a mandatory part and an optional part, and the objective is to maximize the number of optional parts that are successfully executed, in order to improve the accuracy of the results. The optional parts of the jobs represent the independent tasks of our problem. Task execution times are not known before execution; instead, the only information available to the scheduler is that they obey some (unknown) probability distribution. The scheduler needs to acquire some information before deciding for a cutting threshold: instead of allowing all tasks to run until completion, one may want to interrupt long-running tasks at some point. In addition, the cutting threshold may be reevaluated as new information is acquired when the execution progresses further. This work presents several algorithms to determine a good cutting threshold, and to decide when to re-evaluate it. In particular, we use the Kaplan-Meier estimator to account for tasks that are still running when making a decision. The efficiency of our algorithms is assessed through an extensive set of simulations with various budget and deadline values, and ranging over 13 probability distributions. In particular, the AutoPerSurvival(40%,0.005) strategy is proved to have a performance of 77% compared to the upper bound even in the worst case. This shows the robustness of our strategy. [ABSTRACT FROM AUTHOR]

In this work, we advance the understanding of the fundamental limits of computation for binary polynomial optimization (BPO), which is the problem of maximizing a given polynomial function over all binary points. In our main result we provide a novel class of BPO that can be solved efficiently both from a theoretical and computational perspective. In fact, we give a strongly polynomial-time algorithm for instances whose corresponding hypergraph is β -acyclic. We note that the β -acyclicity assumption is natural in several applications including relational database schemes and the lifted multicut problem on trees. Due to the novelty of our proving technique, we obtain an algorithm which is interesting also from a practical viewpoint. This is because our algorithm is very simple to implement and the running time is a polynomial of very low degree in the number of nodes and edges of the hypergraph. Our result completely settles the computational complexity of BPO over acyclic hypergraphs, since the problem is NP-hard on α -acyclic instances. Our algorithm can also be applied to any general BPO problem that contains β -cycles. For these problems, the algorithm returns a smaller instance together with a rule to extend any optimal solution of the smaller instance to an optimal solution of the original instance. [ABSTRACT FROM AUTHOR]

An n-vertex graph is equitably k-colorable if there is a proper coloring of its vertices such that each color is used either n / k or n / k times. While classic Vertex Coloring is fixed parameter tractable under well established parameters such as pathwidth and feedback vertex set, equitable coloring is W[1]-hard. We present an extensive study of structural parameterizations of Equitable Coloring, tackling both tractability and kernelization questions. We begin by showing that the problem is fixed parameter tractable when parameterized by distance to cluster or by distance to co-cluster—improving on the FPT algorithm of Fiala et al. (Theor Comput Sci 412(23):2513–2523, 2011) parameterized by vertex cover—and also when parameterized by distance to disjoint paths of bounded length. To justify the latter result, we adapt a proof of Fellows et al. (Inf Comput 209(2):143–153, 2011) to show that Equitable Coloring is W[1]-hard when simultaneously parameterized by distance to disjoint paths and number of colors. In terms of kernelization, on the positive side we present a linear kernel for the distance to clique parameter and a cubic kernel when parameterized by the maximum leaf number; on the other hand, we show that, unlike Vertex Coloring, Equitable Coloring does not admit a polynomial kernel when jointly parameterized by vertex cover and number of colors, unless NP ⊆ coNP / poly . We also revisit the literature and derive other results on the parameterized complexity of the problem through minor reductions or other observations. [ABSTRACT FROM AUTHOR]

Motivated by placement of jobs in physical machines, we introduce and analyze the problem of online recoloring, or online disengagement. In this problem, we are given a set of n weighted vertices and a k-coloring of the vertices (vertices represent jobs, and colors represent physical machines). Edges, representing conflicts between jobs, are inserted in an online fashion. After every edge insertion, the algorithm must output a proper k-coloring of the vertices. The cost of recoloring a vertex is the vertex's weight. Our aim is to minimize the competitive ratio of the algorithm, i.e., the ratio between the cost paid by the online algorithm and the cost paid by an optimal, offline algorithm. We consider a couple of polynomially-solvable coloring variants. Specifically, for 2-coloring bipartite graphs we present an O (log n) -competitive deterministic algorithm and an Ω (log n) lower bound on the competitive ratio of randomized algorithms. For (Δ + 1) -coloring, where Δ is the maximal node degree, we present tight bounds of Θ (Δ) and Θ (log Δ) on the competitive ratios of deterministic and randomized algorithms, respectively (where Δ denotes the maximum degree). We also consider the fully dynamic case which allows edge deletions as well as insertions. All our algorithms are applicable to the case where vertices are arbitrarily weighted, and all our lower bounds hold even in the uniform weights (unweighted) case. [ABSTRACT FROM AUTHOR]

We study the problem of matching a string in a labeled graph. Previous research has shown that unless the Orthogonal Vectors Hypothesis (OVH) is false, one cannot solve this problem in strongly sub-quadratic time, nor index the graph in polynomial time to answer queries efficiently (Equi et al. ICALP 2019, SOFSEM 2021). These conditional lower-bounds cover even deterministic graphs with binary alphabet, but there naturally exist also graph classes that are easy to index: For example, Wheeler graphs (Gagie et al. Theor. Comp. Sci. 2017) cover graphs admitting a Burrows-Wheeler transform -based indexing scheme. However, it is NP-complete to recognize if a graph is a Wheeler graph (Gibney, Thankachan, ESA 2019). We propose an approach to alleviate the construction bottleneck of Wheeler graphs. Rather than starting from an arbitrary graph, we study graphs induced from multiple sequence alignments (MSAs). Elastic degenerate strings (Bernadini et al. SPIRE 2017, ICALP 2019) can be seen as such graphs, and we introduce here their generalization: elastic founder graphs. We first prove that even such induced graphs are hard to index under OVH. Then we introduce two subclasses, repeat-free and semi-repeat-free graphs, that are easy to index. We give a linear time algorithm to construct a repeat-free (non-elastic) founder graph from a gapless MSA, and (parameterized) near-linear time algorithms to construct a semi-repeat-free (repeat-free, respectively) elastic founder graph from general MSA. Finally, we show that repeat-free founder graphs admit a reduction to Wheeler graphs in polynomial time. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of designing a β -additive fault-tolerant approximate BFS (or FT-ABFS for short) structure, namely, a subgraph H of the network G such that subsequent to the failure of a single edge e, the surviving part of H still contains an approximate BFS spanning tree for (the surviving part of) G, whose distances satisfy dist (s , v , H \ { e }) ≤ dist (s , v , G \ { e }) + β for every v ∈ V . It was shown in Parter and Peleg (SODA, 2014), that for every β ∈ [ 1 , O (log n) ] there exists an n-vertex graph G with a source s for which any β -additive FT-ABFS structure rooted at s has Ω (n 1 + ϵ (β)) edges, for some function ϵ (β) ∈ (0 , 1) . In particular, 3-additive FT-ABFS structures admit a lower bound of Ω (n 5 / 4) edges. In this paper we present the first upper bound, showing that there exists a poly-time algorithm that for every n-vertex unweighted undirected graph G and source s constructs a 4-additive FT-ABFS structure rooted at s with at most O (n 4 / 3) edges. The main technical contribution of our algorithm is in adapting the path-buying strategy used in Baswana et al. (ACM Trans Algorithms 7:A5, 2010) and Cygan et al. (Proceedings of the 30th symposium on theoretical aspects of computer science, pp 209–220, 2013) to failure-prone settings. [ABSTRACT FROM AUTHOR]

Biró et al. (Discrete. Math 100(1–3):267–279, 1992) introduced the concept of H-graphs, intersection graphs of connected subgraphs of a subdivision of a graph H. They are related to and generalize many important classes of geometric intersection graphs, e.g., interval graphs, circular-arc graphs, split graphs, and chordal graphs. Our paper starts a new line of research in the area of geometric intersection graphs by studying several classical computational problems on H-graphs: recognition, graph isomorphism, dominating set, clique, and colorability. We negatively answer the 25-year-old question of Biró, Hujter, and Tuza which asks whether H-graphs can be recognized in polynomial time, for a fixed graph H. We prove that it is NP -complete if H contains the diamond graph as a minor. On the positive side, we provide a polynomial-time algorithm recognizing T-graphs, for each fixed tree T. For the special case when T is a star S d of degree d, we have an O (n 3.5) -time algorithm. We give FPT - and XP -time algorithms solving the minimum dominating set problem on S d -graphs and H-graphs, parametrized by d and the size of H, respectively. The algorithm for H-graphs adapts to an XP -time algorithm for the independent set and the independent dominating set problems on H-graphs. If H contains the double-triangle as a minor, we prove that the graph isomorphism problem is GI-complete and that the clique problem is APX-hard. On the positive side, we show that the clique problem can be solved in polynomial time if H is a cactus graph. Also, when a graph has a Helly H-representation, the clique problem is polynomial-time solvable. Further, we show that both the k-clique and the list k-coloring problems are solvable in FPT-time on H-graphs, parameterized by k and the treewidth of H. In fact, these results apply to classes of graphs with treewidth bounded by a function of the clique number. We observe that H-graphs have at most n O (‖ H ‖) minimal separators which allows us to apply the meta-algorithmic framework of Fomin, Todinca, and Villanger (2015) to show that for each fixed t, finding a maximum induced subgraph of treewidtht can be done in polynomial time. In the case when H is a cactus, we improve the bound to O (‖ H ‖ n 2) . [ABSTRACT FROM AUTHOR]

We study a security game over a network played between a defender and kattackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of λ nodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717–728, 2006). We are interested in Nash equilibria of this game, as well as in characterizing defense-optimal networks which allow for the best equilibrium defense ratio; this is the ratio of k over the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for λ constantly close to 1 or n. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is NP -hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for the Price of Defense for any λ ; this is the worst equilibrium defense ratio over all graphs. [ABSTRACT FROM AUTHOR]

An introduction to the journal is presented in which the editor discusses several papers selected at the 20th Annual European Symposium on Algorithms (ESA) held in Ljubljana, Slovenia on September 10?12, 2012 on topics including algorithmic, use of hash functions, and induced graph matching.

In this paper, we consider the following sum query problem: Given a point set P in R d , and a distance-based function f(p, q) (i.e., a function of the distance between p and q) satisfying some general properties, the goal is to develop a data structure and a query algorithm for efficiently computing a (1 + ϵ) -approximate solution to the sum ∑ p ∈ P f (p , q) for any query point q ∈ R d and any small constant ϵ > 0 . Existing techniques for this problem are mainly based on some core-set techniques which often have difficulties to deal with functions with local domination property. Based on several new insights to this problem, we develop in this paper a novel technique to overcome these encountered difficulties. Our algorithm is capable of answering queries with high success probability in time no more than O ~ ϵ , d (n 0.5 + c) , and the underlying data structure can be constructed in O ~ ϵ , d (n 1 + c) time for any c > 0 , where the hidden constant has only polynomial dependence on 1 / ϵ and d. Our technique is simple and can be easily implemented for practical purpose. [ABSTRACT FROM AUTHOR]

Recent empirical evaluations of exact algorithms for Feedback Vertex Set have demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning. In this paper, we prove that this empirically fast algorithm runs in O (3. 460 k n) time, where k is the solution size. This improves the previous best O (3. 619 k n) -time deterministic algorithm obtained by Kociumaka and Pilipczuk (Inf Process Lett 114:556–560, 2014. https://doi.org/10.1016/j.ipl.2014.05.001). [ABSTRACT FROM AUTHOR]

A resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The Metric Dimension problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer. This problem is NP-complete, and remains so in very restricted classes of graphs. It is also W[2]-complete with respect to the size of the solution. Metric Dimension has proven elusive on graphs of bounded treewidth. On the algorithmic side, a polynomial time algorithm is known for trees, and even for outerplanar graphs, but the general case of treewidth at most two is open. On the complexity side, no parameterized hardness is known. This has led several papers on the topic to ask for the parameterized complexity of Metric Dimension with respect to treewidth. We provide a first answer to the question. We show that Metric Dimension parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential Time Hypothesis fails, there is no algorithm solving Metric Dimension in time f (pw) n o (pw) on n-vertex graphs of constant degree, with pw the pathwidth of the input graph, and f any computable function. This is in stark contrast with an FPT algorithm of Belmonte et al. (SIAM J Discrete Math 31(2):1217–1243, 2017) with respect to the combined parameter tl + Δ , where tl is the tree-length and Δ the maximum-degree of the input graph. [ABSTRACT FROM AUTHOR]

Longest common substring (LCS), longest palindrome substring (LPS), and Ulam distance (UL) are three fundamental string problems that can be classically solved in near linear time. In this work, we present sublinear time quantum algorithms for these problems along with quantum lower bounds. Our results shed light on a very surprising fact: Although the classic solutions for LCS and LPS are almost identical (via suffix trees), their quantum computational complexities are different. While we give an exact O ~ (n) time algorithm for LPS, we prove that LCS needs at least time Ω ~ (n 2 / 3) even for 0/1 strings. [ABSTRACT FROM AUTHOR]

For any odd t ≥ 9 , we present a polynomial-time algorithm that solves the 3-colouring problem, and finds a 3-colouring if one exists, in P t -free graphs of odd girth at least t - 2 . In particular, our algorithm works for (P 9 , C 3 , C 5) -free graphs, thus making progress towards determining the complexity of 3-colouring in P t -free graphs, which is open for t ≥ 8 . [ABSTRACT FROM AUTHOR]

We present a Hamilton cycle in the k-sided pancake network and four combinatorial algorithms to traverse the cycle. The network's vertices are coloured permutations π = p 1 p 2 ⋯ p n , where each p i has an associated colour in { 0 , 1 , ... , k - 1 } . There is a directed edge (π 1 , π 2) if π 2 can be obtained from π 1 by a "flip" of length ℓ , which reverses the first ℓ elements and increments their colour modulo k. Our particular cycle is created using a greedy min-flip strategy, and the average flip length of the edges we use is bounded by a constant. By reinterpreting the order recursively, we can generate successive coloured permutations in O(1)-amortized time, or each successive flip by a loop-free algorithm. We also show how to compute the successor of any coloured permutation in O(n) time. Our greedy min-flip construction generalizes known Hamilton cycles for the pancake network (where k = 1 ) and the burnt pancake network (where k = 2 ). Interestingly, a greedy max-flip strategy works on the pancake and burnt pancake networks, but it does not work on the k-sided network when k > 2 . In addition to our generation results, we provide ranking and unranking algorithms for our Hamiltion cycle that run in O (n 2) time, and show that the cycle is globally optimal in terms of minimizing the total number of pancakes that are flipped. Finally, we characterize the Hamiltonicity of k-sided pancake networks with any fixed "spin" s. [ABSTRACT FROM AUTHOR]

We propose and analyze a self-adaptive version of the (1 , λ) evolutionary algorithm in which the current mutation rate is encoded within the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time (number of fitness evaluations) of O (n λ / log λ + n log n) when λ is at least C ln n for some constant C > 0 . For all values of λ ≥ C ln n , this performance is asymptotically best possible among all λ -parallel mutation-based unbiased black-box algorithms. Our result rigorously proves for the first time that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. In particular, it gives asymptotically the same performance as the relatively complicated self-adjusting scheme for the mutation rate proposed by Doerr, Gießen, Witt, and Yang (Algorithmica 2019). On the technical side, the paper contributes new tools for the analysis of two-dimensional drift processes arising in the analysis of dynamic parameter choices in EAs, including bounds on occupation probabilities in processes with non-constant drift. [ABSTRACT FROM AUTHOR]

The paper considers scheduling jobs online to minimize the objective ∑ i ∈ [ n ] w i g (C i - r i) , where w i is the weight of job i, r i is its release time, C i is its completion time and g is any non-decreasing convex function. It is known that the clairvoyant algorithm Highest-Density-First (HDF) is (2 + ϵ) -speed O(1)-competitive for this objective on a single machine for any fixed 0 < ϵ < 1 (Im et al., in: ACM-SIAM symposium on discrete algorithms, pp 1254–1265, 2012). In this paper, we give the first non-trivial results for this problem when g is a non-decreasing convex function and the algorithm must be non-clairvoyant. More specifically, our results include: A (2 + ϵ) -speed O(1)-competitive non-clairovyant algorithm on a single machine for all non-decreasing convex g, matching the performance of HDF for any fixed 0 < ϵ < 1 . A (3 + ϵ) -speed O(1)-competitive non-clairovyant algorithm on multiple identical machines for all non-decreasing convex g for any fixed 0 < ϵ < 1 . The paper gives the first non-trivial upper-bound on multiple machines even if the algorithm is allowed to be clairvoyant. All performance guarantees above hold for all non-decreasing convex functions gsimultaneously. The positive results are supplemented by almost matching lower bounds. We show that any algorithm that is oblivious to g is not O(1)-competitive with speed augmentation less than 2 on a single machine. Further, any non-clairvoyent algorithm that knows the function g cannot be O(1)-competitive with speed augmentation less than 2 on a single machine or (2 - 1 m) on m identical machines. [ABSTRACT FROM AUTHOR]