ALBERT

Description: In the classic k -center problem, we are given a metric graph, and the objective is to select k nodes as centers such that the maximum distance from any vertex to its closest center is minimized. In this paper, we consider two important generalizations of k -center, the matroid center problem and the knapsack center problem. Both problems are motivated by recent content distribution network applications. Our contributions can be summarized as follows: (1) We consider the matroid center problem in which the centers are required to form an independent set of a given matroid. We show this problem is NP-hard even on a line. We present a 3-approximation algorithm for the problem on general metrics. We also consider the outlier version of the problem where a given number of vertices can be excluded as outliers from the solution. We present a 7-approximation for the outlier version. (2) We consider the (multi-)knapsack center problem in which the centers are required to satisfy one (or more) knapsack constraint(s). It is known that the knapsack center problem with a single knapsack constraint admits a 3-approximation. However, when there are at least two knapsack constraints, we show this problem is not approximable at all. To complement the hardness result, we present a polynomial time algorithm that gives a 3-approximate solution such that one knapsack constraint is satisfied and the others may be violated by at most a factor of \(1+\epsilon \) . We also obtain a 3-approximation for the outlier version that may violate the knapsack constraint by \(1+\epsilon \) .

Description: We design a succinct data structure for representing a poset that, given two elements, can report whether one precedes the other in constant time. This is equivalent to succinctly representing the transitive closure graph of the poset, and we note that the same method can also be used to succinctly represent the transitive reduction graph. For an n element poset, the data structure occupies \(n^2/4 + o(n^2)\) bits in the worst case. Furthermore, a slight extension to this data structure yields a succinct oracle for reachability in arbitrary directed graphs. Thus, using no more than a quarter of the space required to represent an arbitrary directed graph, reachability queries can be supported in constant time. We also consider the operation of listing all the successors or predecessors of a given element, and show how to do this in constant time per element reported using a slightly modified version of our succinct data structure.

Description: We consider a graph observability problem: how many edge colors are needed for an unlabeled graph so that an agent, walking from node to node, can uniquely determine its location from just the observed color sequence of the walk? Specifically, let G ( n ,  d ) be an edge-colored subgraph of d -dimensional (directed or undirected) lattice of size \(n^d = n \times n \times \cdots \times n\) . We say that G ( n ,  d ) is t -observable if an agent can uniquely determine its current position in the graph from the color sequence of any t -dimensional walk, where the dimension is the number of different directions spanned by the edges of the walk. A walk in an undirected lattice G ( n ,  d ) has dimension between 1 and d , but a directed walk can have dimension between 1 and 2 d because of two different orientations for each axis. We derive bounds on the number of colors needed for t -observability. Our main result is that \(\varTheta (n^{d/t})\) colors are both necessary and sufficient for t -observability of G ( n ,  d ), where d is considered a constant. This shows an interesting dependence of graph observability on the ratio between the dimension of the lattice and that of the walk. In particular, the number of colors for full-dimensional walks is \(\varTheta (n^{1/2})\) in the directed case, and \(\varTheta (n)\) in the undirected case, independent of the lattice dimension. All of our results extend easily to non-square lattices: given a lattice graph of size \(N = n_1 \times n_2 \times \cdots \times n_d\) , the number of colors for t -observability is \(\varTheta (\root t \of {N})\) .

Description: We revisit the matrix problems sparse null space and matrix sparsification , and show that they are equivalent. We then proceed to seek algorithms for these problems: we prove the hardness of approximation of these problems, and also give a powerful tool to extend algorithms and heuristics for sparse approximation theory to these problems.

Description: We introduce Planar Disjoint Paths Completion , a completion counterpart of the Disjoint Paths problem, and study its parameterized complexity. The problem can be stated as follows: given a, not necessarily connected, plane graph G ,  k pairs of terminals, and a face F of G ,  find a minimum-size set of edges, if one exists, to be added inside F so that the embedding remains planar and the pairs become connected by k disjoint paths in the augmented network. Our results are twofold: first, we give an upper bound on the number of necessary additional edges when a solution exists. This bound is a function of k , independent of the size of G . Second, we show that the problem is fixed-parameter tractable, in particular, it can be solved in time \(f(k)\cdot n^{2}\) .

Description: We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time \(\mathcal {O}(2^{\lambda n})\) for some \(\lambda 〈1\) . These are the first algorithms breaking the trivial \(2^n n^{\mathcal {O}(1)}\) bound of the brute-force search for these problems.

Description: We investigate the effect of limiting the number of reserve prices on the revenue in a probabilistic single item auction. In the model considered, bidders compete for an impression drawn from a known distribution of possible types. The auction mechanism sets up to \(\ell \) reserve prices, and each impression type is assigned the highest reserve price lower than the valuation of some bidder for it. The bidder proposing the highest bid for an arriving impression gets it provided his bid is at least the corresponding reserve price, and pays the maximum between the reserve price and the second highest bid. Since the number of impression types may be huge, we consider the revenue \(R_{\ell }\) that can be ensured using only \(\ell \) reserve prices. Our main results are tight lower bounds on \(R_{\ell }\) for the cases where the impressions are drawn from the uniform or a general probability distribution.

Description: The new dual-pivot Quicksort by Vladimir Yaroslavskiy—used in Oracle’s Java runtime library since version 7—features intriguing asymmetries. They make a basic variant of this algorithm use less comparisons than classic single-pivot Quicksort. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample. Surprisingly, dual-pivot Quicksort then needs more comparisons than a corresponding version of classic Quicksort, so it is clear that counting comparisons is not sufficient to explain the running time advantages observed for Yaroslavskiy’s algorithm in practice. Consequently, we take a more holistic approach and give also the precise leading term of the average number of swaps, the number of executed Java Bytecode instructions and the number of scanned elements, a new simple cost measure that approximates I/O costs in the memory hierarchy. We determine optimal order statistics for each of the cost measures. It turns out that the asymmetries in Yaroslavskiy’s algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, we finally have a convincing explanation for the success of Yaroslavskiy’s algorithm in practice: compared with corresponding versions of classic single-pivot Quicksort, dual-pivot Quicksort needs significantly less I/Os, both with and without pivot sampling.

Description: In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present new approximation algorithms for it. This problem is a generalization of the classical facility location problem where each facility can serve at most u units of demand and each client must be served by exactly one facility. This problem is motivated by its applications in many practical problems including supply chain problems of indivisible goods (Verter in Foundations of location analysis, chapter 2. International series in operations research and management science. Springer, Berlin, 2011 ) and the assignment problem in the content distribution networks (Bateni and Hajiaghayi in Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, pp 805–814, 2009 ). While there are several approximation algorithms for the soft capacitated version of this problem (in which one can open multiple copies of each facility) or the splittable version (in which the demand of each client can be divided to be served by multiple open facilities), there are very few results for the UCFLP. It is known that it is NP-hard to approximate this problem within any factor without violating the capacities. So we consider bicriteria \((\alpha ,\beta )\) -approximations where the algorithm returns a solution whose cost is within factor \(\alpha \) of the optimum and violates the capacity constraints within factor \(\beta \) . Shmoys et al. (Proceedings of the twenty-ninth annual ACM symposium on theory of computing, pp 265–274, 1997 ) were the first to consider this problem and gave a (9, 4)-approximation. Later results imply ( O (1), 2)-approximations, however, no constant factor approximation is known with capacity violation of less than 2. We present a framework for designing bicriteria approximation algorithms for this problem and show two new approximation algorithms with factors (9, 3 / 2) and (29.315, 4 / 3). These are the first algorithms with constant approximation in which the violation of capacities is below 2. The heart of our algorithm is a reduction from the UCFLP to a restricted version of the problem. One feature of this reduction is that any \((O(1),1+{\epsilon })\) -approximation for the restricted version implies an \((O(1),1+{\epsilon })\) -approximation for the UCFLP and we believe our techniques might be useful towards finding such approximations or perhaps \((f({\epsilon }),1+{\epsilon })\) -approximation for the UCFLP for some function f . In addition, we present a quasi-polynomial time \((1+\epsilon ,1+\epsilon )\) -approximation for the (uniform) UCFLP in Euclidean metrics, for any constant \({\epsilon }〉0\) .

Description: A commonly studied means of parameterizing graph problems is the deletion distance from triviality (Guo et al., Parameterized and exact computation, Springer, Berlin, pp. 162–173, 2004 ), which counts vertices that need to be deleted from a graph to place it in some class for which efficient algorithms are known. In the context of graph isomorphism, we define triviality to mean a graph with maximum degree bounded by a constant, as such graph classes admit polynomial-time isomorphism tests. We generalise deletion distance to a measure we call elimination distance to triviality, based on elimination trees or tree-depth decompositions. We establish that graph canonisation, and thus graph isomorphism, is \(\mathsf {FPT}\) when parameterized by elimination distance to bounded degree, extending results of Bouland et al. (Parameterized and exact computation, Springer, Berlin, pp. 218–230, 2012 ).

Description: Recent advances in drift analysis have given us better and better tools for understanding random processes, including the run time of randomized search heuristics. In the setting of multiplicative drift we do not only have excellent bounds on the expected run time, but also more general results showing the strong concentration of the run time. In this paper we investigate the setting of additive drift under the assumption of strong concentration of the “step size” of the process. Under sufficiently strong drift towards the goal we show a strong concentration of the hitting time. In contrast to this, we show that in the presence of small drift a Gambler’s-Ruin-like behavior of the process overrides the influence of the drift, leading to a maximal movement of about \(\sqrt{t}\) steps within t iterations. Finally, in the presence of sufficiently strong negative drift the hitting time is superpolynomial with high probability; this corresponds to the well-known Negative Drift Theorem.

Description: Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set  \(\mathbb {T}\) of binary binets or trinets over a taxon set  X , and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an  \(O(3^{|X|} poly(|X|))\) time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted phylogenetic networks.

Description: We consider stochastic versions of OneMax and LeadingOnes and analyze the performance of evolutionary algorithms with and without populations on these problems. It is known that the ( \(1+1\) ) EA on OneMax performs well in the presence of very small noise, but poorly for higher noise levels. We extend these results to LeadingOnes and to many different noise models, showing how the application of drift theory can significantly simplify and generalize previous analyses. Most surprisingly, even small populations (of size \(\varTheta (\log n)\) ) can make evolutionary algorithms perform well for high noise levels, well outside the abilities of the ( \(1+1\) ) EA. Larger population sizes are even more beneficial; we consider both parent and offspring populations. In this sense, populations are robust in these stochastic settings.

Description: Since Tinhofer proposed the MinGreedy algorithm for maximum cardinality matching in 1984, several experimental studies found the randomized algorithm to perform excellently for various classes of random graphs and benchmark instances. In contrast, only few analytical results are known. We show that MinGreedy cannot improve on the trivial approximation ratio of  \(\frac{1}{2}\) whp., even for bipartite graphs. Our hard inputs seem to require a small number of high-degree nodes. This motivates an investigation of greedy algorithms on graphs with maximum degree  \(\varDelta \) : we show that  MinGreedy achieves a  \({\frac{{\varDelta }-1}{2{\varDelta }-3}} \) -approximation for graphs with  \({\varDelta } {=} 3\) and for \(\varDelta \) -regular graphs, and a guarantee of  \({\frac{{\varDelta }-1/2}{2{\varDelta }-2}} \) for graphs with maximum degree  \({\varDelta } \) . Interestingly, our bounds even hold for the deterministic MinGreedy that breaks all ties arbitrarily. Moreover, we investigate the limitations of the greedy paradigm, using the model of priority algorithms introduced by Borodin, Nielsen, and Rackoff. We study deterministic priority algorithms and prove a  \({\frac{{\varDelta }-1}{2{\varDelta }-3}}\) -inapproximability result for graphs with maximum degree  \({\varDelta } \) ; thus, these greedy algorithms do not achieve a  \(\frac{1}{2} {+} \varepsilon \) -approximation and in particular the  \(\frac{2}{3}\) -approximation obtained by the deterministic MinGreedy for  \({\varDelta } {=} 3\) is optimal in this class. For  k -uniform hypergraphs we show a tight  \(\frac{1}{k}\) -inapproximability bound. We also study fully randomized priority algorithms and give a  \(\frac{5}{6}\) -inapproximability bound. Thus, they cannot compete with matching algorithms of other paradigms.

Description: We discuss how string sorting algorithms can be parallelized on modern multi-core shared memory machines. As a synthesis of the best sequential string sorting algorithms and successful parallel sorting algorithms for atomic objects, we first propose string sample sort. The algorithm makes effective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Then we focus on NUMA architectures, and develop parallel multiway LCP-merge and -mergesort to reduce the number of random memory accesses to remote nodes. Additionally, we parallelize variants of multikey quicksort and radix sort that are also useful in certain situations. As base-case sorter for LCP-aware string sorting we describe sequential LCP-insertion sort which calculates the LCP array and accelerates its insertions using it. Comprehensive experiments on five current multi-core platforms are then reported and discussed. The experiments show that our parallel string sorting implementations scale very well on real-world inputs and modern machines.

Description: Stochastic boolean function evaluation (SBFE) is the problem of determining the value of a given boolean function f on an unknown input x , when each bit \(x_i\) of x can only be determined by paying a given associated cost \(c_i\) . Further, x is drawn from a given product distribution: for each \(x_i\) , \(\mathbf{Pr}[x_i=1] = p_i\) and the bits are independent. The goal is to minimize the expected cost of evaluation. In this paper, we study the complexity of the SBFE problem for classes of DNF formulas. We consider both exact and approximate versions of the problem for subclasses of DNF, for arbitrary costs and product distributions, and for unit costs and/or the uniform distribution.

Description: Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition , asks whether an input graph G can be represented by closed intervals, i.e., whether G is an interval graph. There are several linear-time algorithms known for recognizing interval graphs, the oldest one is by Booth and Lueker (J Comput Syst Sci 13:335–379, 1976 ) based on PQ-trees. In this paper, we study a generalization of recognition, called partial representation extension . The input of this problem consists of a graph G with a partial representation \({{{\mathcal {R}}}}'\) fixing the positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation \({{{\mathcal {R}}}}\) of the entire graph G extending \({{{\mathcal {R}}}}'\) . We generalize the characterization of interval graphs by Fulkerson and Gross (Pac J Math 15:835–855, 1965 ) to extendible partial representations. Using it, we give a linear-time algorithm for partial representation extension based on a reordering problem of PQ-trees.

Description: Modern data management systems often need to deal with massive, dynamic and inherently distributed data sources. We collect the data using a distributed network, and at the same time try to maintain a global view of the data at a central coordinator using a minimal amount of communication. Such applications have been captured by the distributed monitoring model which has attracted a lot of attention in recent years. In this paper we investigate the monitoring of the entropy functions, which are very useful in network monitoring applications such as detecting distributed denial-of-service attacks. Our results improve the previous best results by Arackaparambil et al. in ICLP 1: 95–106 ( 2009 ). Our technical contribution also includes implementing the celebrated AMS sampling method (by Alon et al. in J Comput Syst Sci 58(1): 137–147 1999 ) in the distributed monitoring model, which could be of independent interest.

Description: In the Boundary Labeling problem, we are given a set of  n points, referred to as sites , inside an axis-parallel rectangle  R , and a set of  n pairwise disjoint rectangular labels that are attached to  R from the outside. The task is to connect the sites to the labels by non-intersecting rectilinear paths, so-called leaders , with at most one bend. In this paper, we study the Multi-Sided Boundary Labeling problem, with labels lying on at least two sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases in which labels lie on one side or on two opposite sides of  R (here a crossing-free solution always exists). The case where labels may lie on adjacent sides is more difficult. We present efficient algorithms for testing the existence of a crossing-free leader layout that labels all sites and also for maximizing the number of labeled sites in a crossing-free leader layout. For two-sided boundary labeling with adjacent sides, we further show how to minimize the total leader length in a crossing-free layout.

Description: In this paper we consider the problem of the strict self-assembly of infinite fractals within tile self-assembly. In particular, we provide tile assembly algorithms for the assembly of a Sierpinski triangle and the discrete Sierpinski carpet within a class of models we term the h - handed assembly model ( h -HAM), which generalizes the 2-HAM to allow up to h assemblies to combine in a single assembly step. Despite substantial consideration, no purely growth self-assembly model has yet been shown to strictly assemble an infinite fractal without significant modification to the fractal shape. In this paper we not only achieve this, but in the case of the Sierpinski carpet are able to achieve it within the 2-HAM, one of the most well studied tile assembly models in the literature. Our specific results are as follows: We provide a 6-HAM construction for a Sierpinski triangle that works at scale factor 1, 30 tile types, and assembles the fractal in a near perfect way in which all intermediate assemblies are finite-sized iterations of the recursive fractal. We further assemble a Sierpinski triangle within the 3-HAM at scale factor 3 and 990 tile types. For the Sierpinski carpet, we present a 2-HAM result that works at scale factor 3 and uses 1216 tile types. We further include analysis showing that the aTAM is incapable of strictly assembling the Sierpinski triangle considered in this paper, and that multiple hands are needed for the near-perfect assembly of a Sierpinski triangle and the Sierpinski carpet.

Description: We consider k -Facility Location games, where n strategic agents report their locations on the real line and a mechanism maps them to k facilities. Each agent seeks to minimize his connection cost, given by a nonnegative increasing function of his distance to the nearest facility. Departing from previous work, that mostly considers the identity cost function, we are interested in mechanisms without payments that are (group) strategyproof for any given cost function, and achieve a good approximation ratio for the social cost and/or the maximum cost of the agents. We present a randomized mechanism, called Equal Cost , which is group strategyproof and achieves a bounded approximation ratio for all k and n , for any given concave cost function. The approximation ratio is at most 2 for Max Cost and at most n for Social Cost . To the best of our knowledge, this is the first mechanism with a bounded approximation ratio for instances with \(k \ge 3\) facilities and any number of agents. Our result implies an interesting separation between deterministic mechanisms, whose approximation ratio for Max Cost jumps from 2 to unbounded when k increases from 2 to 3, and randomized mechanisms, whose approximation ratio remains at most 2 for all k . On the negative side, we exclude the possibility of a mechanism with the properties of Equal Cost for strictly convex cost functions. We also present a randomized mechanism, called Pick the Loser , which applies to instances with k facilities and only \(n = k+1\) agents. For any given concave cost function, Pick the Loser is strongly group strategyproof and achieves an approximation ratio of 2 for Social Cost .

Description: We give a deterministic #SAT algorithm for de Morgan formulas of size up to \(n^{2.63}\) , which runs in time \(2^{n-n^{{\varOmega }(1)}}\) . This improves upon the deterministic #SAT algorithm of Chen et al. (Proceedings of the twenty-ninth annual IEEE conference on computational complexity, 2014 ), which has similar running time but works only for formulas of size less than \(n^{2.5}\) . Our new algorithm is based on the shrinkage of de Morgan formulas under random restrictions, shown by Paterson and Zwick (Random Struct Algorithms 4(2):135–150, 1993 ). We prove a concentrated and constructive version of their shrinkage result. Namely, we give a deterministic polynomial-time algorithm that selects variables in a given de Morgan formula so that, with high probability over the random assignments to the chosen variables, the original formula shrinks in size, when simplified using a given deterministic polynomial-time formula-simplification algorithm.

Description: We consider Conditional random fields ( CRFs ) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) \(x_1\ldots x_n\) is the sum of terms over intervals [ i ,  j ] where each term is non-zero only if the substring \(x_i\ldots x_j\) equals a prespecified pattern w . Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively \(O(\textit{nL})\) , \(O(\textit{nL} \ell _{\max })\) and \(O(\textit{nL} \min \{|D|,\log (\ell _{\max }\!+\!1)\})\) where L is the combined length of input patterns, \(\ell _{\max }\) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009 ) whose complexities are respectively \(O(\textit{nL} |D|)\) , \(O\left( n |\varGamma | L^2 \ell _{\max }^2\right) \) and \(O(\textit{nL} |D|)\) , where \(|\varGamma |\) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights.

Description: Estimating the number of triangles in graph streams using a limited amount of memory has become a popular topic in the last decade. Different variations of the problem have been studied, depending on whether the graph edges are provided in an arbitrary order or as incidence lists. However, with a few exceptions, the algorithms have considered insert-only streams. We present a new algorithm estimating the number of triangles in dynamic graph streams where edges can be both inserted and deleted. We show that our algorithm achieves better time and space complexity than previous solutions for various graph classes, for example sparse graphs with a relatively small number of triangles. Also, for graphs with constant transitivity coefficient, a common situation in real graphs, this is the first algorithm achieving constant processing time per edge. The result is achieved by a novel approach combining sampling of vertex triples and sparsification of the input graph. In the course of the analysis of the algorithm we present a lower bound on the number of pairwise independent 2-paths in general graphs which might be of independent interest. At the end of the paper we discuss lower bounds on the space complexity of triangle counting algorithms that make no assumptions on the structure of the graph.

Description: We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted Identifying Code , (Open) Open Locating-Dominating Set and Metric Dimension ) of an interval or a permutation graph. In these problems, one asks to distinguish all vertices of a graph by a subset of the vertices, using either the neighbourhood within the solution set or the distances to the solution vertices. Using a general reduction for this class of problems, we prove that the decision problems associated to these four notions are NP-complete, even for interval graphs of diameter 2 and permutation graphs of diameter 2. While Identifying Code and (Open) Locating-Dominating Set are trivially fixed-parameter-tractable when parameterized by solution size, it is known that in the same setting Metric Dimension is W [2]-hard. We show that for interval graphs, this parameterization of Metric Dimension is fixed-parameter-tractable.

Description: Given a partition of an n element set into equivalence classes, we study the problem of assigning unique labels to these elements in order to support the query that asks whether the elements corresponding to two given labels belong to the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models. Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of \(\sum _{i=1}^n \lfloor {n \over i} \rfloor \) is necessary and sufficient. In other words, \(\lg n + \lg \lg n + O(1)\) bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of \(\lceil \lg n \rceil \) for the label length, if each vertex need not get a unique label. Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set \(\{1,\ldots , n\}\) , we first show that \(\varTheta (\sqrt{n})\) bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O (1) time in the standard word RAM model. We also develop a dynamic structure that uses \(O(\sqrt{n} \lg n)\) bits to support equivalence queries and unions in \(O(\lg n/\lg \lg n)\) worst case time or \(O(\alpha (n))\) expected amortized time where \(\alpha (n)\) is the inverse Ackermann function. Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set \(\{1,\ldots , cn\}\) for any constant \(c 〉 1\) , we show that \(\varTheta (\lg n)\) bits are necessary and sufficient to represent the equivalence class information. Moreover, we can support the query in such a structure in O (1) time in the standard word RAM model. We believe that our work can trigger further work on tradeoffs between label space and auxiliary data structure space for other labeling problems.

Description: We perform a thorough study of various characteristics of the asynchronous push–pull protocol for spreading a rumor on Erdős–Rényi random graphs \(G_{n,p}\) , for any \(p〉c\ln (n)/n\) with \(c〉1\) . In particular, we provide a simple strategy for analyzing the asynchronous push–pull protocol on arbitrary graph topologies and apply this strategy to \(G_{n,p}\) . We prove tight bounds of logarithmic order for the total time that is needed until the information has spread to all nodes. Surprisingly, the time required by the asynchronous push–pull protocol is asymptotically almost unaffected by the average degree of the graph. Similarly tight bounds for Erdős–Rényi random graphs have previously only been obtained for the synchronous push protocol, where it has been observed that the total running time increases significantly for sparse random graphs. Finally, we quantify the robustness of the protocol with respect to transmission and node failures. Our analysis suggests that the asynchronous protocols are particularly robust with respect to these failures compared to their synchronous counterparts.

Description: We study connectivity relations among points, where the precise location of each input point lies in a region of uncertainty. We distinguish two fundamental scenarios under which uncertainty arises. In the favorable Best-Case Uncertainty , each input point can be chosen from a given set to yield the best possible objective value. In the unfavorable Worst-Case Uncertainty , the input set has worst possible objective value among all possible point locations, which are uncertain due, for example, to imprecise data. We consider these notions of uncertainty for the bottleneck spanning tree problem, giving rise to the following Best-Case Connectivity with Uncertainty problem: given a family of geometric regions, choose one point per region, such that the longest edge length of an associated geometric spanning tree is minimized. We show that this problem is NP-hard even for very simple scenarios in which the regions are line segments or squares. On the other hand, we give an exact solution for the case in which there are \(n+k\) regions, where k of the regions are line segments and n of the regions are fixed points. We then give approximation algorithms for cases where the regions are either all line segments or all unit discs. We also provide approximation methods for the corresponding Worst-Case Connectivity with Uncertainty problem: Given a set of uncertainty regions, find the minimal distance r such that for any choice of points, one per region, there is a spanning tree among the points with edge length at most r .

Description: We define the modular treewidth of a graph as its treewidth after contraction of modules. This parameter properly generalizes treewidth and is itself properly generalized by clique-width. We show that the number of satisfying assignments can be computed in polynomial time for CNF formulas whose incidence graphs have bounded modular treewidth. Our result generalizes known results for the treewidth of incidence graphs and is incomparable with known results for clique-width (or rank-width) of signed incidence graphs. The contraction of modules is an effective data reduction procedure. Our algorithm is the first one to harness this technique for #SAT. The order of the polynomial bounding the runtime of our algorithm depends on the modular treewidth of the input formula. We show that it is unlikely that this dependency can be avoided by proving that SAT is W[1]-hard when parameterized by the modular incidence treewidth of the given CNF formula.

Description: In a classical online network design problem, traffic requirements are gradually revealed to an algorithm. Each time a new request arrives, the algorithm has to satisfy it by augmenting the network under construction in a proper way (with no possibility of recovery). In this paper we study a natural generalization of online network design problems, where a fraction of the requests (the outliers ) can be disregarded. Now, each time a request arrives, the algorithm first decides whether to satisfy it or not, and only in the first case it acts accordingly. We cast three classical network design problems into this framework: (i) Online Steiner tree with outliers In this case a set of t terminals that belong to an n -node graph is presented, one at a time, to an algorithm. Each time a new terminal arrives, the algorithm can either discard or select it. In the latter case, the algorithm connects it to the Steiner tree under construction (initially consisting of a given root node). At the end of the process, at least k terminals must be selected. (ii) Online TSP with outliers This is the same problem as above, but with the Steiner tree replaced by a TSP tour. (iii) Online facility location with outliers In this case, we are also given a set of facility nodes, each one with an opening cost. Each time a terminal is selected, we have to connect it to some facility (and open that facility, if it is not already open). We focus on the known distribution model, where terminals are independently sampled from a given distribution. For all the above problems, we present bicriteria online algorithms that, for any constant \(\epsilon 〉0\) , select at least \((1-\epsilon )k\) terminals with high probability and pay in expectation \(O(\log ^2n)\) times more than the expected cost of the optimal offline solution (selecting k terminals). These upper bounds are complemented by inapproximability results for the case that one insists on selecting exactly k terminals, and by lower bounds including an \(\varOmega (\log n/\log \log n)\) lower bound for the case that the online algorithm is allowed to select \(\alpha \,k\) terminals only, for a sufficiently large constant \(\alpha \in (0,1)\) .

Description: A well known result in graph algorithms, due to Edmonds, states that given a digraph D and a positive integer \(\ell \) , we can test whether D contains \(\ell \) arc-disjoint out-branchings in polynomial time. However, if we ask whether there exists an out-branching and an in-branching which are arc-disjoint, then the problem becomes NP -complete. In fact, even deciding whether a digraph D contains an out-branching which is arc-disjoint from some spanning tree in the underlying undirected graph remains NP -complete. In this paper we formulate some natural optimization questions around these problems and initiate its study in the realm of parameterized complexity. More precisely, the problems we study are the following: Arc - Disjoint Branchings and Non - Disconnecting Out - Branching . In Arc - Disjoint Branchings ( Non - Disconnecting Out - Branching ), a digraph D and a positive integer k are given as input and the goal is to test whether there exist an out-branching and in-branching (respectively, a spanning tree in the underlying undirected graph) that differ on at least k arcs. We obtain the following results for these problems. Non - Disconnecting Out - Branching is fixed parameter tractable (FPT) and admits a linear vertex kernel. Arc - Disjoint Branchings is FPT on strong digraphs. The algorithm for Non - Disconnecting Out - Branching runs in time \(2^{\mathcal {O}(k)}n^{\mathcal {O}(1)}\) and the approach we use to obtain this algorithms seems useful in designing other moderately exponential time algorithms for edge/arc partitioning problems.

Description: We study the stable roommates problem in networks where players are embedded in a social context and may incorporate positive externalities into their decisions. Each player is a node in a social network and strives to form a good match with a neighboring player. We consider the existence, computation, and inefficiency of stable matchings from which no pair of players wants to deviate. We characterize prices of anarchy and stability, which capture the ratio of the total profit in the optimum matching over the total profit of the worst and best stable matching, respectively. When the benefit from a match (which we model by associating a reward with each edge) is the same for both players, we show that externalities can significantly improve the price of stability, while the price of anarchy remains unaffected. Furthermore, a good stable matching achieving the bound on the price of stability can be obtained in polynomial time. We extend these results to more general matching rewards, when players matched to each other may receive different benefits from the match. For this more general case, we show that network externalities (i.e., “caring about your friends”) can make an even larger difference and greatly reduce the price of anarchy. We show a variety of existence results and present upper and lower bounds on the prices of anarchy and stability for various structures of matching benefits. All our results on stable matchings immediately extend to the more general case of fractional stable matchings.

Description: We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noise \(\beta \) describes the behavior of a complex system whose individual components act selfishly according to some partial (“noisy”) knowledge of the system, where the capacity of the agent to know the system and compute her best move is measured by parameter \(\beta \) . In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that for potential games the mixing time is bounded by an exponential in \(\beta \) and in the maximum potential difference. Instead, for games with dominant strategies the mixing time cannot grow arbitrarily with \(\beta \) . Finally, we refine our analysis for a subclass of potential games called graphical coordination games, often used for modeling the diffusion of new technologies. We prove that the mixing time of the logit dynamics for these games can be upper bounded by a function that is exponential in the cutwidth of the underlying graph and in \(\beta \) . Moreover, we consider two specific and popular network topologies, the clique and the ring. For the clique, we prove an almost matching lower bound on the mixing time of the logit dynamics that is exponential in \(\beta \) and in the maximum potential difference, while for the ring we prove that the time of convergence of the logit dynamics to its stationary distribution is significantly shorter.

Description: Given a plane graph G (i.e., a planar graph with a fixed planar embedding and outer face) and a biconnected subgraph \(G^{\prime }\) with a fixed planar straight-line convex drawing, we consider the question whether this drawing can be extended to a planar straight-line drawing of G . We characterize when this is possible in terms of simple necessary conditions, which we prove to be sufficient. This also leads to a linear-time testing algorithm. If a drawing extension exists, one can be computed in the same running time.

Description: The rotor–router model , also called the Propp machine , was first considered as a deterministic alternative to the random walk. The edges adjacent to each node  v (or equivalently, the exit ports at  v ) are arranged in a fixed cyclic order, which does not change during the exploration. Each node  v maintains a port pointer   \(\pi _v\) which indicates the exit port to be adopted by an agent on the conclusion of the next visit to this node (the “next exit port”). The rotor–router mechanism guarantees that after each consecutive visit at the same node, the pointer at this node is moved to the next port in the cyclic order. It is known that, in an undirected graph  G with  m edges, the route adopted by an agent controlled by the rotor–router mechanism eventually forms an Euler tour based on arcs obtained via replacing each edge in  G by two arcs with opposite direction. The process of ushering the agent to an Euler tour is referred to as the lock-in problem . In Yanovski et al. (Algorithmica 37(3):165–186, 2003 ), it was proved that, independently of the initial configuration of the rotor–router mechanism in  G , the agent locks-in in time bounded by  \(2mD\) , where \(D\) is the diameter of  G . In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor–router mechanism. Our analysis is performed in the form of a game between a player \({\mathcal {P}}\) intending to lock-in the agent in an Euler tour as quickly as possible and its adversary \({\mathcal {A}}\) with the counter objective. We consider all cases of who decides the initial cyclic orders and the initial values \(\pi _v\) . We show, for example, that if \({\mathcal {A}}\) provides its own port numbering after the initial setup of pointers by \({\mathcal {P}}\) , the worst-case complexity of the lock-in problem is \({\varTheta }(m\cdot \min \{\log m,D\})\) . We also investigate the robustness of the rotor–router graph exploration in presence of faults in the pointers \(\pi _v\) or dynamic changes in the graph. We show, for example, that after the exploration establishes an Eulerian cycle, if k edges are added to the graph, then a new Eulerian cycle is established within \(\mathcal {O}(km)\) steps.

Description: Consider the problem of selecting k items that maximize the value of a monotone submodular set function f , where f can be accessed using value queries. It is well known that polynomially many queries suffice in order to obtain an approximation ratio of \(1 - \frac{1}{e}\) . We consider a variation on this problem in which the value queries are required to be of uniform size: each queried set, like the desired solution itself, must contain k items. We show that polynomially many uniform size queries suffice in order to obtain an approximation ratio of \(\frac{1}{2}\) , and that an approximation ratio of \(\frac{1 + \epsilon }{2}\) requires a number of queries that is exponential in \(\epsilon k\) . For the interesting special case of coverage functions, we show that an approximation ratio strictly better than \(\frac{1}{2}\) is attainable with polynomially many uniform size queries. The “uniform size” requirement is motivated by situations in which a firm may offer a menu of exactly k items to its clients, where k is a parameter determined by external considerations. Performing a query corresponds to physically changing the identities of the items offered, and the reply to the query is deduced by observing the behavior of clients in response to the change. Queries that involve a number of items that differs from k may not be desirable due to these external considerations. In such situations it is natural to ask whether the same approximation ratios that can be guaranteed by general value queries can also be obtained by uniform size queries.

Description: In this paper, we study the approximability of the Maximum Labeled Path problem: given a vertex-labeled directed acyclic graph D , find a path in D that collects a maximum number of distinct labels. For any \(\epsilon 〉0\) , we provide a polynomial time approximation algorithm that computes a solution of value at least \(OPT^{1-\epsilon }\) and a self-reduction showing that any constant ratio approximation algorithm for this problem can be converted into a PTAS. This last result, combined with the APX -hardness of the problem, shows that the problem cannot be approximated within any constant ratio unless \(P=NP\) .

Description: We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration variant of an optimization problem \(\mathcal {Q}\) takes as input two feasible solutions S and T and determines if there is a sequence of reconfiguration steps, i.e. a reconfiguration sequence, that can be applied to transform S into T such that each step results in a feasible solution to \(\mathcal {Q}\) . For most of the results in this paper, S and T are sets of vertices of a given graph and a reconfiguration step adds or removes a vertex. Our study is motivated by results establishing that for many NP -hard problems, the classical complexity of reconfiguration is PSPACE -complete. We address the question for several important graph properties under two natural parameterizations: k , a bound on the size of solutions, and \(\ell \) , a bound on the length of reconfiguration sequences. Our first general result is an algorithmic paradigm, the reconfiguration kernel, used to obtain fixed-parameter tractable algorithms for reconfiguration variants of Vertex Cover and, more generally, Bounded Hitting Set and Feedback Vertex Set , all parameterized by k . In contrast, we show that reconfiguring Unbounded Hitting Set is W[2] -hard when parameterized by \(k+\ell \) . We also demonstrate the W[1] -hardness of reconfiguration variants of a large class of maximization problems parameterized by \(k+\ell \) , and of their corresponding deletion problems parameterized by \(\ell \) ; in doing so, we show that there exist problems in FPT when parameterized by k , but whose reconfiguration variants are W[1] -hard when parameterized by \(k+\ell \) .

Description: The greedy spanner is the highest quality geometric spanner (in e.g. edge count and weight, both in theory and practice) known to be computable in polynomial time. Unfortunately, all known algorithms for computing it on n points take \(\varOmega (n^2)\) time, limiting its applicability on large data sets. We propose a novel algorithm design which uses the observation that for many point sets, the greedy spanner has many ‘short’ edges that can be determined locally and usually quickly. To find the usually few remaining ‘long’ edges, we use a combination of already determined local information and the well-separated pair decomposition. We give experimental results showing large to massive performance increases over the state-of-the-art on nearly all tests and real-life data sets. On the theoretical side we prove a near-linear expected time bound on uniform point sets and a near-quadratic worst-case bound. Our bound for point sets drawn uniformly and independently at random in a square follows from a local characterization of t -spanners we give on such point sets. We give a geometric property that holds with high probability, which in turn implies that if an edge set on these points has t -paths between pairs of points ‘close’ to each other, then it has t -paths between all pairs of points. This characterization gives an \(O(n \log ^2 n \log ^2 \log n)\) expected time bound on our greedy spanner algorithm, making it the first subquadratic time algorithm for this problem on any interesting class of points. We also use this characterization to give an \(O((n + |E|) \log ^2 n \log \log n)\) expected time algorithm on uniformly distributed points that determines whether E is a t -spanner, making it the first subquadratic time algorithm for this problem that does not make assumptions on E .

Description: Let \(\mathcal {D} = \{\mathsf {T}_1,\mathsf {T}_2, \ldots ,\mathsf {T}_D\}\) be a collection of D string documents of n characters in total, that are drawn from an alphabet set \(\varSigma =[\sigma ]\) . The top-k document retrieval problem is to preprocess \(\mathcal{D}\) into a data structure that, given a query \((P[1\ldots p],k)\) , can return the k documents of \(\mathcal{D}\) most relevant to the pattern P . The relevance is captured using a predefined ranking function, which depends on the set of occurrences of P in \(\mathsf {T}_d\) . For example, it can be the term frequency (i.e., the number of occurrences of P in \(\mathsf {T}_d\) ), or it can be the term proximity (i.e., the distance between the closest pair of occurrences of P in \(\mathsf {T}_d\) ), or a pattern-independent importance score of \(\mathsf {T}_d\) such as PageRank. Linear space and optimal query time solutions already exist for the general top- k document retrieval problem. Compressed and compact space solutions are also known, but only for a few ranking functions such as term frequency and importance. However, space efficient data structures for term proximity based retrieval have been evasive. In this paper we present the first sub-linear space data structure for this relevance function, which uses only o ( n ) bits on top of any compressed suffix array of \(\mathcal{D}\) and solves queries in \(O((p+k) {{\mathrm{polylog}}}\,\,n)\) time. We also show that scores that consist of a weighted combination of term proximity, term frequency, and document importance, can be handled using twice the space required to represent the text collection.

Description: We study the parameterized complexity of Geometric Graph Isomorphism (Known as the Point Set Congruence problem in computational geometry): given two sets of n points A and B with rational coordinates in k -dimensional euclidean space, with k as the fixed parameter, the problem is to decide if there is a bijection \(\pi :A \rightarrow B\) such that for all \(x,y \in A\) , \(\Vert x-y\Vert = \Vert \pi (x)-\pi (y)\Vert \) , where \(\Vert \cdot \Vert \) is the euclidean norm. Our main result is the following: We give a \(O^*(k^{O(k)})\) time (The \(O^*(\cdot )\) notation here, as usual, suppresses polynomial factors) FPT algorithm for Geometric Isomorphism. This is substantially faster than the previous best time bound of \(O^*(2^{O(k^4)})\) for the problem (Evdokimov and Ponomarenko in Pure Appl Algebra 117–118:253–276, 1997 ). In fact, we show the stronger result that even canonical forms for finite point sets with rational coordinates can also be computed in \(O^*(k^{O(k)})\) time. We also briefly discuss the isomorphism problem for other \(l_p\) metrics. Specifically, we describe a deterministic polynomial-time algorithm for finite point sets in \(\mathbb {Q}^2\) .

Description: We present deterministic and randomized algorithms for the problem of online packet routing in grids in the competitive network throughput model (Aiello et al. in SODA, pp 771–780 2003 ). In this model the network has nodes with bounded buffers and bounded link capacities. The goal in this model is to maximize the throughput, i.e., the number of delivered packets. Our deterministic algorithm is the first online algorithm with an \(O\left( \log ^{O(1)}(n)\right) \) competitive ratio for uni-directional grids (where n denotes the size of the network). The deterministic online algorithm is centralized and handles packets with deadlines. This algorithm is applicable to various ranges of values of buffer sizes and communication link capacities. In particular, it holds for buffer size and communication link capacity in the range \([3 \ldots \log n]\) . Our randomized algorithm achieves an expected competitive ratio of \(O(\log n)\) for the uni-directional line. This algorithm is applicable to a wide range of buffer sizes and communication link capacities. In particular, it holds also for unit size buffers and unit capacity links. This algorithm improves the best previous \(O(\log ^2 n)\) -competitive ratio of Azar and Zachut (ESA, pp 484–495, 2005 ).

Description: In the Shortest Superstring problem we are given a set of strings \(S=\{s_1, \ldots , s_n\}\) and integer \(\ell \) and the question is to decide whether there is a superstring s of length at most \(\ell \) containing all strings of S as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time \(2^{\mathcal {O}(k)} {\text {poly}}(n)\) finds a superstring of length at most \(\ell \) containing at least k strings of S . We complement this by a lower bound showing that such a parameterization does not admit a polynomial kernel up to some complexity assumption. We also obtain several results about “below guaranteed values” parameterization of the problem. We show that parameterization by compression admits a polynomial kernel while parameterization “below matching” is hard.

Description: We prove that given a bipartite graph G with vertex set V and an integer  k , deciding whether there exists a subset of V of size at most k hitting all maximal independent sets of G is complete for the class \(\varSigma_{2}^{\mathrm{P}}\) .

Description: We present the first approximate distance oracle for sparse directed networks with time-dependent arc-travel-times determined by continuous, piecewise linear, positive functions possessing the FIFO property. Our approach precomputes \((1+\varepsilon )\) -approximate distance summaries from selected landmark vertices to all other vertices in the network. Our oracle uses subquadratic space and time preprocessing, and provides two sublinear-time query algorithms that deliver constant and \((1+\sigma )\) -approximate shortest-travel-times, respectively, for arbitrary origin–destination pairs in the network, for any constant \(\sigma 〉 \varepsilon \) . Our oracle is based only on the sparsity of the network, along with two quite natural assumptions about travel-time functions which allow the smooth transition towards asymmetric and time-dependent distance metrics.

Description: A Bloom filter is a method for reducing the space (memory) required for representing a set by allowing a small error probability. In this paper we consider a Sliding Bloom Filter: a data structure that, given a stream of elements, supports membership queries of the set of the last n elements (a sliding window), while allowing a small error probability and a slackness parameter. The problem of sliding Bloom filters has appeared in the literature in several communities, but this work is the first theoretical investigation of it. We formally define the data structure and its relevant parameters and analyze the time and memory requirements needed to achieve them. We give a low space construction that runs in \(O(1)\) time per update with high probability (that is, for all sequences with high probability all operations take constant time) and provide an almost matching lower bound on the space that shows that our construction has the best possible space consumption up to an additive lower order term.

Description: We study the complexity of the Channel Assignment problem. By applying the meet-in-the-middle approach we get an algorithm for the \(\ell \) -bounded Channel Assignment (when the edge weights are bounded by \(\ell \) ) running in time \(O^*((2\sqrt{\ell +1})^n)\) . This is the first algorithm which breaks the \((O(\ell ))^n\) barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. Very recently the second author showed that Channel Assignment does not admit a \(O(c^n)\) -time algorithm, for a constant c independent of \(\ell \) . We consider a similar question for Generalized \(T\) - Coloring , a CSP problem that generalizes Channel Assignment . We show that Generalized \(T\) - Coloring   does not admit a \(2^{2^{o\left( \sqrt{n}\right) }} \mathrm{poly}(r)\) -time algorithm, where r is the size of the instance.

Description: We introduce and investigate a new notion of resilience in graph spanners. Let \(S\) be a spanner of a weighted graph \(G\) . Roughly speaking, we say that \(S\) is resilient if all its point-to-point distances are resilient to edge failures. Namely, whenever any edge in \(G\) fails, then as a consequence of this failure all distances do not degrade in \(S\) substantially more than in \(G\) (i.e., the relative distance increases in \(S\) are very close to those in the underlying graph \(G\) ). In this paper we show that sparse resilient spanners exist, and that they can be computed efficiently.

Description: A variety of algorithms have been proposed for reconstructing trees that show the evolutionary relationships between species by comparing differences in genetic data across present-day species. If the leaf-to-leaf distances in a tree can be accurately estimated, then it is possible to reconstruct this tree from these estimated distances, using polynomial-time methods such as the popular ‘Neighbor-Joining’ algorithm. There is a precise combinatorial condition under which distance-based methods are guaranteed to return a correct tree (in full or in part) based on the requirement that the input distances all lie within some ‘safety radius’ of the true distances. Here, we explore a stochastic analogue of this condition, and mathematically establish upper and lower bounds on this ‘stochastic safety radius’ for distance-based tree reconstruction methods. Using simulations, we show how this notion provides a new way to compare the performance of distance-based tree reconstruction methods. This may help explain why Neighbor-Joining performs so well, as its stochastic safety radius appears close to optimal (while its more classical safety radius is the same as many other less accurate methods).

Description: The \(k\) -colouring reconfiguration problem asks whether, for a given graph \(G\) , two proper \(k\) -colourings \(\alpha \) and \(\beta \) of \(G\) , and a positive integer \(\ell \) , there exists a sequence of at most \(\ell +1\) proper \(k\) -colourings of \(G\) which starts with \(\alpha \) and ends with \(\beta \) and where successive colourings in the sequence differ on exactly one vertex of \(G\) . We give a complete picture of the parameterized complexity of the \(k\) -colouring reconfiguration problem for each fixed \(k\) when parameterized by \(\ell \) . First we show that the \(k\) -colouring reconfiguration problem is polynomial-time solvable for \(k=3\) , settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all \(k \ge 4\) , we show that the \(k\) -colouring reconfiguration problem, when parameterized by \(\ell \) , is fixed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses.

Description: Stackelberg pricing of vertex covers in a bipartite graph, with the priceable nodes on one side of the bipartition, reduces to a sequence of maximum flow problems. This was shown by Briest et al. (Algorithmica 62:733–753, 2012 ), leading to an \(O(n^6)\) algorithm. Here \(n\) is the number of nodes of the graph. We show how the use of the preflow algorithm gives an \(O(n^4)\) algorithm.

Description: We consider a hybrid two-stage optimization problem that generalizes two classic combinatorial optimization problems: (i) weighted vertex cover in graphs, and (ii) makespan minimization in multiprocessor scheduling. An instance specifies a machine environment, a set of jobs, and an undirected graph over the jobs. The goal is to select a subset of the jobs that forms a vertex cover and to schedule it on a set of parallel machines so as to minimize the makespan. We call this problem family vertex cover meets multiprocessor scheduling (VCMS). The problem is motivated by networks where vertices represent servers and each edge corresponds to a task that can be done by any of the two servers of its endpoint. Each selected server can complete any number of tasks assigned to it within a given time defined by its weight, as the time consumption of the server is roughly equal to its activation time. The activation is performed by a set of \(m\) processors, such that every selected server is activated by one processor, and the goal is to minimize the maximum total activation time assigned to any processor. We design a multitude of approximation algorithms for VCMS and its variants, many of which match or almost match the best approximation bound known for the vertex cover problem. In particular, we give a \(2\) -approximation for the case of a fixed number of unrelated machines, a \(3\) -approximation for an arbitrary number of unrelated machines, and a \((2+\varepsilon )\) -approximation for an arbitrary number of identical machines. Furthermore we consider special graph classes for which the weighted vertex cover problem can be solved to optimality in polynomial time: for many of these classes, there is a PTAS for VCMS on identical machines; for bipartite graphs, however, VCMS on identical machines turns out to be APX-hard. Finally, we study the bin packing counterpart of VCMS and design a \((2+\varepsilon )\) -approximation algorithm for it.

Description: The development of randomized algorithms for numerical linear algebra, e.g. for computing approximate QR and SVD factorizations, has recently become an intense area of research. This paper studies one of the most frequently discussed algorithms in the literature for dimensionality reduction—specifically for approximating an input matrix with a low-rank element. We introduce a novel and rather intuitive analysis of the algorithm in [ 6 ], which allows us to derive sharp estimates and give new insights about its performance. This analysis yields theoretical guarantees about the approximation error and at the same time, ultimate limits of performance (lower bounds) showing that our upper bounds are tight. Numerical experiments complement our study and show the tightness of our predictions compared with empirical observations.

Description: The greedy spanner is a high-quality spanner: its total weight, edge count and maximal degree are asymptotically optimal and in practice significantly better than for any other spanner with reasonable construction time. Unfortunately, all known algorithms that compute the greedy spanner on \(n\) points use \(\varOmega (n^2)\) space, which is impractical on large instances. To the best of our knowledge, the largest instance for which the greedy spanner was computed so far has about 13,000 vertices. We present a linear-space algorithm that computes the same spanner for points in \(\mathbb {R}^d\) running in \(O(n^2 \log ^2 n)\) time for any fixed stretch factor and dimension. We discuss and evaluate a number of optimizations to its running time, which allowed us to compute the greedy spanner on a graph with a million vertices. To our knowledge, this is also the first algorithm for the greedy spanner with a near-quadratic running time guarantee that has actually been implemented.

Description: Persistent homology with coefficients in a field \(\mathbb {F}\) coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substantially the amount of matrix operations. In addition, we propose a heuristic to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology.

Description: A graph is outer 1-planar ( o1p ) if it can be drawn in the plane such that all vertices are in the outer face and each edge is crossed at most once. o1p graphs generalize outerplanar graphs, which can be recognized in linear time, and specialize 1-planar graphs, whose recognition is \({NP}\) -hard. We explore o1p graphs. Our first main result is a linear-time algorithm that takes a graph as input and returns a positive or a negative witness for o1p . If a graph  \(G\) is o1p , then the algorithm computes an embedding and can augment \(G\) to a maximal o1p graph. Otherwise, \(G\) includes one of six minors, which is detected by the recognition algorithm. Secondly, we establish structural properties of o1p graphs. o1p graphs are planar and are subgraphs of planar graphs with a Hamiltonian cycle. They are neither closed under edge contraction nor under subdivision. Several important graph parameters, such as treewidth, colorability, stack number, and queue number, increase by one from outerplanar to o1p graphs. Every o1p graph of size \(n\) has at most \(\frac{5}{2} n - 4\) edges and there are maximal o1p graphs with \(\frac{11}{5} n - \frac{18}{5}\) edges, and these bounds are tight. Finally, every o1p graph has a straight-line grid drawing in \(\fancyscript{O}(n^2)\) area with all vertices in the outer face, a planar visibility representation in \(\fancyscript{O}(n \log n)\) area, and a 3D straight-line drawing in linear volume, and these drawings can be constructed in linear time.

Description: Given an edge-weighted directed graph \(G=(V,E)\) on n vertices and a set \(T=\{t_1, t_2, \ldots , t_p\}\) of p terminals, the objective of the Strongly Connected Steiner Subgraph ( p -SCSS) problem is to find an edge set \(H\subseteq E\) of minimum weight such that G [ H ] contains an \(t_{i}\rightarrow t_j\) path for each \(1\le i\ne j\le p\) . The p -SCSS problem is NP-hard, but Feldman and Ruhl [FOCS ’99; SICOMP ’06] gave a novel \(n^{O(p)}\) time algorithm. In this paper, we investigate the computational complexity of a variant of 2-SCSS where we have demands for the number of paths between each terminal pair. Formally, the \(2\) -SCSS- \((k_1, k_2)\) problem is defined as follows: given an edge-weighted directed graph \(G=(V,E)\) with weight function \(\omega : E\rightarrow {\mathbb {R}}^{\ge 0}\) , two terminal vertices s ,  t , and integers \(k_1, k_2\) ; the objective is to find a set of \(k_1\) paths \(F_1, F_2, \ldots , F_{k_1}\) from \(s\leadsto t\) and \(k_2\) paths \(B_1, B_2, \ldots , B_{k_2}\) from \(t\leadsto s\) such that \(\sum _{e\in E} \omega (e)\cdot \phi (e)\) is minimized, where \(\phi (e)= \max \Big \{|\{i\in [k_1] : e\in F_i\}|\ ,\ |\{j\in [k_2] : e\in B_j\}|\Big \}\) . For each \(k\ge 1\) , we show the following: The \(2\) -SCSS- \((k,1)\) problem can be solved in time \(n^{O(k)}\) . A matching lower bound for our algorithm: the \(2\) -SCSS- \((k,1)\) problem does not have an \(f(k)\cdot n^{o(k)}\) time algorithm for any computable function f , unless the Exponential Time Hypothesis fails. Our algorithm for \(2\) -SCSS- \((k,1)\) relies on a structural result regarding an optimal solution followed by using the idea of a “token game” similar to that of Feldman and Ruhl. We show with an example that the structural result does not hold for the \(2\) -SCSS- \((k_1, k_2)\) problem if \(\min \{k_1, k_2\}\ge 2\) . Therefore \(2\) -SCSS- \((k,1)\) is the most general problem one can attempt to solve with our techniques. To obtain the lower bound matching the algorithm, we reduce from a special variant of the Grid Tiling problem introduced by Marx [FOCS ’07; ICALP ’12].

Description: Algorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer and selfish agents involved. This is principally because in absence of money, very little can be done to enforce truthfulness. However, in certain applications, money is unavailable, morally unacceptable or might simply be at odds with the objective of the mechanism. For example, in combinatorial auctions (CAs), the paradigmatic problem of the area, we aim at solutions of maximum social welfare but still charge the society to ensure truthfulness. Additionally, truthfulness of CAs is poorly understood already in the case in which bidders happen to be interested in only two different sets of goods. We focus on the design of incentive-compatible CAs without money in the general setting of k -minded bidders. We trade monetary transfers with the observation that the mechanism can detect certain lies of the bidders: i.e., we study truthful CAs with verification and without money. We prove a characterization of truthful mechanisms, which makes an interesting parallel with the well-understood case of CAs with money for single-minded bidders. We then give a host of upper bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms when the sets and valuations are private knowledge of the bidders. (Most of these mechanisms run in polynomial time and return solutions with (nearly) best possible approximation guarantees.) We complement these positive results with a number of lower bounds (some of which are essentially tight) that hold in the easier case of public sets. We thus provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.

Description: Communication in “natural” settings, e.g., between humans, is distinctly different from that in classical designed settings, in that the former is invariably characterized by the sender and receiver not being in perfect agreement with each other. Solutions to classical communication problems thus have to overcome an extra layer of uncertainty introduced by this lack of prior agreement. One of the classical goals of communication is compression of information, and in this context lack of agreement implies that sender and receiver may not agree on the “prior” from which information is being generated. Most classical mechanisms for compressing turn out to be non-robust when sender and receiver do not agree on the prior. Juba et al. (Proc. ITCS 2011) showed that there do exists compression schemes with shared randomness between sender and receiver that do not share a prior that can compress information down roughly to its entropy. In this work, we explore the assumption of shared randomness between the sender and receiver and highlight why this assumption is problematic when dealing with natural communication. We initiate the study of deterministic compression schemes amid uncertain priors, and expose some of the mathematical facets of this problem. We show some non-trivial deterministic compression schemes, and some lower bounds on natural classes of compression schemes. We show that a full understanding of deterministic communication turns into challenging (open) questions in graph theory and communication complexity.

Description: This paper deals with a matching game in which the nodes of a simple graph are independent agents who try to form pairs. If we let the agents make their decision without any central control then a possible outcome is a Nash equilibrium, that is a situation in which no unmatched player can change his strategy and find a partner. However, there can be a big difference between two possible outcomes of the same instance, in terms of number of matched nodes. A possible solution is to force all the nodes to follow a centrally computed maximum matching but it can be difficult to implement this approach. This article proposes a tradeoff between the total absence and the full presence of a central control. Concretely, we study the optimization problem where the action of a minimum number of agents is centrally fixed and any possible equilibrium of the modified game must be a maximum matching. In algorithmic game theory, this approach is known as the price of optimum of a game. For the price of optimum of the matching game, deciding whether a solution is feasible is not straightforward, but we prove that it can be done in polynomial time. In addition, the problem is shown APX -hard, since its restriction to graphs admitting a perfect matching is equivalent, from the approximability point of view, to vertex cover . Finally we prove that this problem admits a polynomial 6-approximation algorithm in general graphs.

Description: This article is motivated by the following satisfiability question: pick uniformly at random an \(\mathsf {and/or}\) Boolean expression of length n , built on a set of \(k_n\) Boolean variables. What is the probability that this expression is satisfiable? asymptotically when n tends to infinity? The model of random Boolean expressions developed in the present paper is the model of Boolean Catalan trees, already extensively studied in the literature for a constant sequence \((k_n)_{n\ge 1}\) . The fundamental breakthrough of this paper is to generalise the previous results for any (reasonable) sequence of integers \((k_n)_{n\ge 1}\) , which enables us, in particular, to solve the above satisfiability question. We also analyse the effect of introducing a natural equivalence relation on the set of Boolean expressions. This new quotient model happens to exhibit a very interesting threshold (or saturation) phenomena at \(k_n = {n}\big /{\ln n}\) .

Description: Partial match queries constitute the most basic type of associative queries in multidimensional data structures such as \(K\) -d trees or quadtrees. Given a query \(\mathbf {q}=(q_0,\ldots ,q_{K-1})\) where s of the coordinates are specified and \(K-s\) are left unspecified ( \(q_i=*\) ), a partial match search returns the subset of data points \(\mathbf {x}=(x_0,\ldots ,x_{K-1})\) in the data structure that match the given query, that is, the data points such that \(x_i=q_i\) whenever \(q_i\not =*\) . There exists a wealth of results about the cost of partial match searches in many different multidimensional data structures, but most of these results deal with random queries. Only recently a few papers have begun to investigate the cost of partial match queries with a fixed query \(\mathbf {q}\) . This paper represents a new contribution in this direction, giving a detailed asymptotic estimate of the expected cost \(P_{{n},\mathbf {q}}\) for a given fixed query \(\mathbf {q}\) . From previous results on the cost of partial matches with a fixed query and the ones presented here, a deeper understanding is emerging, uncovering the following functional shape for \(P_{{n},\mathbf {q}}\) $$\begin{aligned} P_{{n},\mathbf {q}} = \nu \cdot \left( \prod _{i:q_i\text { is specified}}\, q_i(1-q_i)\right) ^{\alpha /2}\cdot n^\alpha + \text {l.o.t.} \end{aligned}$$ (l.o.t. lower order terms, throughout this work) in many multidimensional data structures, which differ only in the exponent \(\alpha \) and the constant \(\nu \) , both dependent on s and K , and, for some data structures, on the whole pattern of specified and unspecified coordinates in \(\mathbf {q}\) as well. Although it is tempting to conjecture that this functional shape is “universal”, we have shown experimentally that it seems not to be true for a variant of \(K\) -d trees called squarish \(K\) -d trees.

Description: In this paper we introduce and study the strip planarity testing problem, which takes as an input a planar graph G ( V ,  E ) and a function \(\gamma :V \rightarrow \{1,2,\dots ,k\}\) and asks whether a planar drawing of G exists such that each edge is represented by a curve that is monotone in the y -direction and, for any \(u,v\in V\) with \(\gamma (u)〈\gamma (v)\) , it holds that \(y(u)〈y(v)\) . The problem has strong relationships with some of the most deeply studied variants of the planarity testing problem, such as clustered planarity , upward planarity , and level planarity . Most notably, we provide a polynomial-time reduction from strip planarity testing to clustered planarity. We show that the strip planarity testing problem is polynomial-time solvable if G has a prescribed combinatorial embedding.

Description: Polynomial Identity Testing (PIT) algorithms have focussed on polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted formulas. Read-once polynomials (ROPs) are computed by read-once formulas (ROFs) and are the simplest of read-restricted polynomials. Building structures above these, we show the following: (1) a deterministic polynomial-time non-black-box PIT algorithm for \(\sum ^{(2)}\times \prod \times \mathsf{ROF}\) . (2) Weak hardness of representation theorems for sums of powers of constant-free ROP s and for \(\mathsf{ROF}\) s of the form \(\sum \times \prod \times \sum \) . (3) A partial characterization of multilinear monotone constant-free ROPs.

Description: In 1967, Moon and Moser proved a tight bound on the critical density of squares in squares: any set of squares with a total area of at most 1/2 can be packed into a unit square, which is tight. The proof requires full knowledge of the set, as the algorithmic solution consists in sorting the objects by decreasing size, and packing them greedily into shelves. Since then, the online version of the problem has remained open; the best upper bound is still 1/2, while the currently best lower bound is 1/3, due to Han et al. (Theory Comput Syst 43(1):38–55, 2008 ). In this paper, we present a new lower bound of 11/32, based on a dynamic shelf allocation scheme, which may be interesting in itself. We also give results for the closely related problem in which the size of the square container is not fixed, but must be dynamically increased in order to accommodate online sequences of objects. For this variant, we establish an upper bound of 3/7 for the critical density, and a lower bound of 1/8. When aiming for accommodating an online sequence of squares, this corresponds to a \(2.82{\ldots }\) -competitive method for minimizing the required container size, and a lower bound of \(1.33{\ldots }\) for the achievable factor.

Description: We show that in the model of zero-error communication complexity, direct sum fails for average communication complexity as well as for external information complexity. Our example also refutes a version of a conjecture by Braverman et al. that in the zero-error case amortized communication complexity equals external information complexity. In our examples the underlying distributions do not have full support. One interpretation of a distribution of non full support is as a promise given to the players (the players have a guarantee on their inputs). This brings up the issue of promise versus non-promise problems in this context.

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider a general load balancing problem on parallel machines. Our machine environment in particular generalizes the standard models of identical machines, and the model of uniformly related machines, as well as machines with a constant number of types, and machines with activation costs. The objective functions that we consider contain in particular the makespan objective and the minimization of the 〈span〉 〈span〉\(\ell _p\)〈/span〉 〈/span〉-norm of the vector of loads of the machines, and each case allows the possibility of job rejection. We consider this general model and design an efficient polynomial time approximation scheme (EPTAS) that applies for all its previously-studied special cases. This EPTAS improves the current best approximation scheme for some of these cases where only a polynomial time approximation scheme was known into an EPTAS.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉The parameterised complexity of various consensus string problems (〈span〉Closest String〈/span〉, 〈span〉Closest Substring〈/span〉, 〈span〉Closest String with Outliers〈/span〉) is investigated in a more general setting, i. e., with a bound on the maximum Hamming distance 〈em〉and〈/em〉 a bound on the sum of Hamming distances between solution and input strings. We completely settle the parameterised complexity of these generalised variants of 〈span〉Closest String〈/span〉 and 〈span〉Closest Substring〈/span〉, and partly for 〈span〉Closest String with Outliers〈/span〉; in addition, we answer some open questions from the literature regarding the classical problem variants with only one distance bound. Finally, we investigate the question of polynomial kernels and respective lower bounds.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Let 〈span〉 〈span〉\(P \subset \mathbb {R}^d\)〈/span〉 〈/span〉 be a set of 〈em〉n〈/em〉 points in 〈em〉d〈/em〉 dimensions such that each point 〈span〉 〈span〉\(p \in P\)〈/span〉 〈/span〉 has an 〈em〉associated radius〈/em〉〈span〉 〈span〉\(r_p 〉 0\)〈/span〉 〈/span〉. The 〈em〉transmission graph〈/em〉〈em〉G〈/em〉 for 〈em〉P〈/em〉 is the directed graph with vertex set 〈em〉P〈/em〉 such that there is an edge from 〈em〉p〈/em〉 to 〈em〉q〈/em〉 if and only if 〈span〉 〈span〉\(|pq| \le r_p\)〈/span〉 〈/span〉, for any 〈span〉 〈span〉\(p, q \in P\)〈/span〉 〈/span〉. A 〈em〉reachability oracle〈/em〉 is a data structure that decides for any two vertices 〈span〉 〈span〉\(p, q \in G\)〈/span〉 〈/span〉 whether 〈em〉G〈/em〉 has a path from 〈em〉p〈/em〉 to 〈em〉q〈/em〉. The quality of the oracle is measured by the space requirement 〈em〉S〈/em〉(〈em〉n〈/em〉), the query time 〈em〉Q〈/em〉(〈em〉n〈/em〉), and the preprocessing time. For transmission graphs of one-dimensional point sets, we can construct in 〈span〉 〈span〉\(O(n \log n)\)〈/span〉 〈/span〉 time an oracle with 〈span〉 〈span〉\(Q(n) = O(1)\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(S(n) = O(n)\)〈/span〉 〈/span〉. For planar point sets, the ratio 〈span〉 〈span〉\(\Psi \)〈/span〉 〈/span〉 between the largest and the smallest associated radius turns out to be an important parameter. We present three data structures whose quality depends on 〈span〉 〈span〉\(\Psi \)〈/span〉 〈/span〉: the first works only for 〈span〉 〈span〉\(\Psi 〈 \sqrt{3}\)〈/span〉 〈/span〉 and achieves 〈span〉 〈span〉\(Q(n) = O(1)\)〈/span〉 〈/span〉 with 〈span〉 〈span〉\(S(n) = O(n)\)〈/span〉 〈/span〉 and preprocessing time 〈span〉 〈span〉\(O(n\log n)\)〈/span〉 〈/span〉; the second data structure gives 〈span〉 〈span〉\(Q(n) = O(\Psi ^3 \sqrt{n})\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(S(n) = O(\Psi ^3 n^{3/2})\)〈/span〉 〈/span〉; the third data structure is randomized with 〈span〉 〈span〉\(Q(n) = O(n^{2/3}\log ^{1/3} \Psi \log ^{2/3} n)\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(S(n) = O(n^{5/3}\log ^{1/3} \Psi \log ^{2/3} n)\)〈/span〉 〈/span〉 and answers queries correctly with high probability.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider the construction of the 〈em〉suffix tree〈/em〉 and the 〈em〉directed acyclic word graph〈/em〉 (〈em〉DAWG〈/em〉) indexing data structures for a collection 〈span〉 〈span〉\(\mathcal {T}\)〈/span〉 〈/span〉 of texts, where a new symbol may be appended to any text in 〈span〉 〈span〉\(\mathcal {T} = \{T_1, \ldots , T_K\}\)〈/span〉 〈/span〉, 〈em〉at any time〈/em〉. This 〈em〉fully-online〈/em〉 scenario, which arises in dynamically indexing multi-sensor data, is a natural generalization of the long solved 〈em〉semi-online〈/em〉 text indexing problem, where texts 〈span〉 〈span〉\(T_1, \ldots , T_{k}\)〈/span〉 〈/span〉 are permanently fixed before the next text 〈span〉 〈span〉\(T_{k+1}\)〈/span〉 〈/span〉 is processed for each 〈em〉k〈/em〉 (〈span〉 〈span〉\(1 \le k 〈 K\)〈/span〉 〈/span〉). We first show that a direct application of Weiner’s right-to-left online construction for the suffix tree of a single text to fully-online multiple texts requires superlinear time. This also means that Blumer et al.’s left-to-right online construction for the DAWG of a single text requires superlinear time in the fully-online setting. We then present our fully-online versions of these algorithms that run in 〈span〉 〈span〉\(O(N \log \sigma )\)〈/span〉 〈/span〉 time and 〈em〉O〈/em〉(〈em〉N〈/em〉) space, where 〈em〉N〈/em〉 is the total length of the texts in 〈span〉 〈span〉\(\mathcal {T}\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(\sigma \)〈/span〉 〈/span〉 is their alphabet size. We then show how to extend Ukkonen’s left-to-right online suffix tree construction to fully-online multiple strings, with the aid of Weiner’s suffix tree for the reversed texts. 〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉〈em〉Stochastic dominance〈/em〉 is a technique for evaluating the performance of online algorithms that provides an intuitive, yet powerful stochastic order between the compared algorithms. When there is a uniform distribution over the request sequences, this technique reduces to 〈em〉bijective analysis〈/em〉. These methods have been applied in problems such as paging, list update, bin colouring, routing in array mesh networks, and in connection with Bloom filters, and have often provided a clear separation between algorithms whose performance varies significantly in practice. Despite their appealing properties, the above techniques are quite stringent, in that a relation between online algorithms may be either too difficult to establish analytically, or worse, may not even exist. In this paper, we propose remedies to these shortcomings. Our objective is to make all online algorithms amenable to the techniques of stochastic dominance and bijective analysis. First, we establish sufficient conditions that allow us to prove the bijective optimality of a certain class of algorithms for a wide range of problems; we demonstrate this approach in the context of well-studied online problems such as weighted paging, reordering buffer management, and 2-server on the circle. Second, to account for situations in which two algorithms are incomparable or there is no clear optimum, we introduce the 〈em〉bijective ratio〈/em〉 as a natural extension of (exact) bijective analysis. Our definition readily generalizes to stochastic dominance. This makes it possible to compare two arbitrary online algorithms for an arbitrary online problem. In addition, the bijective ratio is a generalization of the Max/Max ratio (due to Ben-David and Borodin), and allows for the incorporation of other useful techniques such as amortized analysis. We demonstrate the applicability of the bijective ratio to one of the fundamental online problems, namely the continuous 〈em〉k〈/em〉-server problem on metrics such as the line, the circle, and the star. Among other results, we show that the greedy algorithm attains bijective ratios of 〈em〉O〈/em〉(〈em〉k〈/em〉) across these metrics.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this article, 〈em〉q〈/em〉-regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor. Each of these terms corresponds to an eigenvalue of the sum of matrices of a linear representation of the sequence; only the eigenvalues of absolute value larger than the joint spectral radius of the matrices contribute terms which grow faster than the error term. The paper has a particular focus on the Fourier coefficients of the periodic fluctuations: they are expressed as residues of the corresponding Dirichlet generating function. This makes it possible to compute them in an efficient way. The asymptotic analysis deals with Mellin–Perron summations and uses two arguments to overcome convergence issues, namely Hölder regularity of the fluctuations together with a pseudo-Tauberian argument. Apart from the very general result, three examples are discussed in more detail:〈/p〉 〈ul〉 〈li〉 〈p〉sequences defined as the sum of outputs written by a transducer when reading a 〈em〉q〈/em〉-ary expansion of the input;〈/p〉 〈/li〉 〈li〉 〈p〉the amount of esthetic numbers in the first 〈em〉N〈/em〉 natural numbers; and〈/p〉 〈/li〉 〈li〉 〈p〉the number of odd entries in the rows of Pascal’s rhombus.〈/p〉 〈/li〉 〈/ul〉 For these examples, very precise asymptotic formulæ are presented. In the latter two examples, prior to this analysis only rough estimates were known.

Description: 〈h3〉Abstract〈/h3〉 〈p〉For any integer 〈span〉 〈span〉\(n\ge 1\)〈/span〉 〈/span〉, a 〈em〉middle levels Gray code〈/em〉 is a cyclic listing of all 〈em〉n〈/em〉-element and 〈span〉 〈span〉\((n+1)\)〈/span〉 〈/span〉-element subsets of 〈span〉 〈span〉\(\{1,2,\ldots ,2n+1\}\)〈/span〉 〈/span〉 such that any two consecutive sets differ in adding or removing a single element. The question whether such a Gray code exists for any 〈span〉 〈span〉\(n\ge 1\)〈/span〉 〈/span〉 has been the subject of intensive research during the last 30 years, and has been answered affirmatively only recently [T. Mütze. Proof of the middle levels conjecture. 〈em〉Proc. London Math. Soc.〈/em〉, 112(4):677–713, 2016]. In a follow-up paper [T. Mütze and J. Nummenpalo. An efficient algorithm for computing a middle levels Gray code. 〈em〉ACM Trans. Algorithms〈/em〉, 14(2):29 pp., 2018] this existence proof was turned into an algorithm that computes each new set in the Gray code in time 〈span〉 〈span〉\({{\mathcal {O}}}(n)\)〈/span〉 〈/span〉 on average. In this work we present an algorithm for computing a middle levels Gray code in optimal time and space: each new set is generated in time 〈span〉 〈span〉\({{\mathcal {O}}}(1)\)〈/span〉 〈/span〉 on average, and the required space is 〈span〉 〈span〉\({{\mathcal {O}}}(n)\)〈/span〉 〈/span〉.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉〈span〉QuickXsort〈/span〉 is a highly efficient in-place sequential sorting scheme that mixes Hoare’s 〈span〉Quicksort〈/span〉 algorithm with X, where X can be chosen from a wider range of other known sorting algorithms, like 〈span〉Heapsort〈/span〉, 〈span〉Insertionsort〈/span〉 and 〈span〉Mergesort〈/span〉. Its major advantage is that 〈span〉QuickXsort〈/span〉 can be in-place even if X is not. In this work we provide general transfer theorems expressing the number of comparisons of 〈span〉QuickXsort〈/span〉 in terms of the number of comparisons of X. More specifically, if pivots are chosen as medians of (not too fast) growing size samples, the average number of comparisons of 〈span〉QuickXsort〈/span〉 and X differ only by 〈em〉o〈/em〉(〈em〉n〈/em〉)-terms. For median-of-〈em〉k〈/em〉 pivot selection for some constant 〈em〉k〈/em〉, the difference is a linear term whose coefficient we compute precisely. For instance, median-of-three 〈span〉QuickMergesort〈/span〉 uses at most 〈span〉 〈span〉\(n \lg n - 0.8358n + {\mathcal {O}}(\log n)\)〈/span〉 〈/span〉 comparisons. Furthermore, we examine the possibility of sorting base cases with some other algorithm using even less comparisons. By doing so the average-case number of comparisons can be reduced down to 〈span〉 〈span〉\(n \lg n - 1.4112n + o(n)\)〈/span〉 〈/span〉 for a remaining gap of only 0.0315〈em〉n〈/em〉 comparisons to the known lower bound (while using only 〈span〉 〈span〉\({\mathcal {O}}(\log n)\)〈/span〉 〈/span〉 additional space and 〈span〉 〈span〉\({\mathcal {O}}(n\log n)\)〈/span〉 〈/span〉 time overall). Implementations of these sorting strategies show that the algorithms challenge well-established library implementations like Musser’s 〈span〉Introsort〈/span〉.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In a recent breakthrough paper Braverman et al. (in: STOC’13, pp 151–160, 〈span〉2013〈/span〉) developed a local characterization for the zero-error information complexity in the two-party model, and used it to compute the exact internal and external information complexity of the 2-bit AND function. In this article, we extend their results on AND function to the multi-party number-in-hand model by proving that the generalization of their protocol has optimal internal and external information cost for certain natural distributions. Our proof has new components, and in particular, it fixes a minor gap in the proof of Braverman et al.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉The Johnson–Lindenstrauss lemma is one of the cornerstone results in dimensionality reduction. A common formulation of it, is that there exists a random linear mapping 〈span〉 〈span〉\(f : {\mathbb {R}}^n \rightarrow {\mathbb {R}}^m\)〈/span〉 〈/span〉 such that for any vector 〈span〉 〈span〉\(x \in {\mathbb {R}}^n\)〈/span〉 〈/span〉, 〈em〉f〈/em〉 preserves its norm to within 〈span〉 〈span〉\((1 {\pm } \varepsilon )\)〈/span〉 〈/span〉 with probability 〈span〉 〈span〉\(1 - \delta \)〈/span〉 〈/span〉 if 〈span〉 〈span〉\(m = \varTheta (\varepsilon ^{-2} \lg (1/\delta ))\)〈/span〉 〈/span〉. Much effort has gone into developing fast embedding algorithms, with the Fast Johnson–Lindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The current fastest algorithm that yields the optimal 〈span〉 〈span〉\(m = {\mathcal {O}}(\varepsilon ^{-2}\lg (1/\delta ))\)〈/span〉 〈/span〉 dimensions has an embedding time of 〈span〉 〈span〉\({\mathcal {O}}(n \lg n + \varepsilon ^{-2} \lg ^3 (1/\delta ))\)〈/span〉 〈/span〉. An exciting approach towards improving this, due to Hinrichs and Vybíral, is to use a random 〈span〉 〈span〉\(m \times n\)〈/span〉 〈/span〉 Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in 〈span〉 〈span〉\({\mathcal {O}}(n \lg m)\)〈/span〉 〈/span〉 time. The big question is of course whether 〈span〉 〈span〉\(m = {\mathcal {O}}(\varepsilon ^{-2} \lg (1/\delta ))\)〈/span〉 〈/span〉 dimensions suffice for this technique. If so, this would end a decades long quest to obtain faster and faster Johnson–Lindenstrauss transforms. The current best analysis of the embedding of Hinrichs and Vybíral shows that 〈span〉 〈span〉\(m = {\mathcal {O}}(\varepsilon ^{-2}\lg ^2 (1/\delta ))\)〈/span〉 〈/span〉 dimensions suffice. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exist vectors requiring 〈span〉 〈span〉\(m = \varOmega (\varepsilon ^{-2} \lg ^2 (1/\delta ))\)〈/span〉 〈/span〉 for the Toeplitz approach to work.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We consider a two-way trading problem, where investors buy and sell a stock whose price moves within a certain range. Naturally they want to maximize their profit. Investors can perform up to 〈em〉k〈/em〉 trades, where each trade must involve the full amount. We give optimal algorithms for three different models which differ in the knowledge of how the price fluctuates. In the first model, there are global minimum and maximum bounds 〈em〉m〈/em〉 and 〈em〉M〈/em〉. We first show an optimal lower bound of 〈span〉 〈span〉\(\varphi \)〈/span〉 〈/span〉 (where 〈span〉 〈span〉\(\varphi =M/m\)〈/span〉 〈/span〉) on the competitive ratio for one trade, which is the bound achieved by trivial algorithms. Perhaps surprisingly, when we consider more than one trade, we can give a better algorithm that loses only a factor of 〈span〉 〈span〉\(\varphi ^{2/3}\)〈/span〉 〈/span〉 (rather than 〈span〉 〈span〉\(\varphi \)〈/span〉 〈/span〉) per additional trade. Specifically, for 〈em〉k〈/em〉 trades the algorithm has competitive ratio 〈span〉 〈span〉\(\varphi ^{(2k+1)/3}\)〈/span〉 〈/span〉. Furthermore we show that this ratio is the best possible by giving a matching lower bound. In the second model, 〈em〉m〈/em〉 and 〈em〉M〈/em〉 are not known in advance, and just 〈span〉 〈span〉\(\varphi \)〈/span〉 〈/span〉 is known. We show that this only costs us an extra factor of 〈span〉 〈span〉\(\varphi ^{1/3}\)〈/span〉 〈/span〉, i.e., both upper and lower bounds become 〈span〉 〈span〉\(\varphi ^{(2k+2)/3}\)〈/span〉 〈/span〉. Finally, we consider the bounded daily return model where instead of a global limit, the fluctuation from one day to the next is bounded, and again we give optimal algorithms, and interestingly one of them resembles common trading strategies that involve stop loss limits.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉A splittable good provided in 〈em〉n〈/em〉 pieces shall be divided as evenly as possible among 〈em〉m〈/em〉 agents, where every agent can take shares from at most 〈em〉F〈/em〉 pieces. We call 〈em〉F〈/em〉 the fragmentation and mainly restrict attention to the cases 〈span〉 〈span〉\(F=1\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(F=2\)〈/span〉 〈/span〉. For 〈span〉 〈span〉\(F=1\)〈/span〉 〈/span〉, the max–min and min–max problems are solvable in linear time. The case 〈span〉 〈span〉\(F=2\)〈/span〉 〈/span〉 has neat formulations and structural characterizations in terms of weighted graphs. First we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if 〈span〉 〈span〉\(m\ge n-1\)〈/span〉 〈/span〉, and a solution always exists in this case, in contrast to 〈span〉 〈span〉\(F=1\)〈/span〉 〈/span〉. Moreover, the problem is fixed-parameter tractable in the parameter 〈span〉 〈span〉\(2m-n\)〈/span〉 〈/span〉. (Note that this parameter measures the number of agents above the trivial threshold 〈span〉 〈span〉\(m=n/2\)〈/span〉 〈/span〉.) The structural results suggest another related problem where unsplittable items shall be assigned to subsets so as to balance the average sizes (rather than the total sizes) in these subsets. We give an approximation-preserving reduction from our original splitting problem with fragmentation 〈span〉 〈span〉\(F=2\)〈/span〉 〈/span〉 to this averaging problem, and some approximation results in cases when 〈em〉m〈/em〉 is close to either 〈em〉n〈/em〉 or 〈em〉n〈/em〉 / 2.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We introduce a compressed suffix array representation that, on a text 〈em〉T〈/em〉 of length 〈em〉n〈/em〉 over an alphabet of size 〈span〉 〈span〉\(\sigma \)〈/span〉 〈/span〉, can be built in 〈em〉O〈/em〉(〈em〉n〈/em〉) deterministic time, within 〈span〉 〈span〉\(O(n\log \sigma )\)〈/span〉 〈/span〉 bits of working space, and counts the number of occurrences of any pattern 〈em〉P〈/em〉 in 〈em〉T〈/em〉 in time 〈span〉 〈span〉\(O(|P| + \log \log _w \sigma )\)〈/span〉 〈/span〉 on a RAM machine of 〈span〉 〈span〉\(w=\Omega (\log n)\)〈/span〉 〈/span〉-bit words. This time is almost optimal for large alphabets (〈span〉 〈span〉\(\log \sigma =\Theta (\log n)\)〈/span〉 〈/span〉), and it outperforms all the other compressed indexes that can be built in linear deterministic time, as well as some others. The only faster indexes can be built in linear time only in expectation, or require 〈span〉 〈span〉\(\Theta (n\log n)\)〈/span〉 〈/span〉 bits. For smaller alphabets, where 〈span〉 〈span〉\(\log \sigma = o(\log n)\)〈/span〉 〈/span〉, we show how, by using space proportional to a compressed representation of the text, we can build in linear time an index that counts in time 〈span〉 〈span〉\(O(|P|/\log _\sigma n + \log _\sigma ^\epsilon n)\)〈/span〉 〈/span〉 for any constant 〈span〉 〈span〉\(\epsilon 〉0\)〈/span〉 〈/span〉. This is almost RAM-optimal in the typical case where 〈span〉 〈span〉\(w=\Theta (\log n)\)〈/span〉 〈/span〉. 〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph 〈span〉 〈span〉\(G=(V,E)\)〈/span〉 〈/span〉 with 〈span〉 〈span〉\(n=|V|\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(m=|E|\)〈/span〉 〈/span〉, and an integer value 〈span〉 〈span〉\(k\ge 1\)〈/span〉 〈/span〉, there is an algorithm that computes in 〈span〉 〈span〉\(O(2^{k}n\log ^2 n)\)〈/span〉 〈/span〉 time for any set 〈em〉F〈/em〉 of size at most 〈em〉k〈/em〉 the strongly connected components of the graph 〈span〉 〈span〉\(G{\setminus }F\)〈/span〉 〈/span〉. The running time of our algorithm is almost optimal since the time for outputting the SCCs of 〈span〉 〈span〉\(G{\setminus } F\)〈/span〉 〈/span〉 is at least 〈span〉 〈span〉\(\varOmega (n)\)〈/span〉 〈/span〉. The algorithm uses a data structure that is computed in a preprocessing phase in polynomial time and is of size 〈span〉 〈span〉\(O(2^{k} n^2)\)〈/span〉 〈/span〉. Our result is obtained using a new observation on the relation between strongly connected components (SCCs) and reachability. More specifically, one of the main building blocks in our result is a restricted variant of the problem in which we only compute strongly connected components that intersect a certain path. Restricting our attention to a path allows us to implicitly compute reachability between the path vertices and the rest of the graph in time that depends logarithmically rather than linearly in the size of the path. This new observation alone, however, is not enough, since we need to find an efficient way to represent the strongly connected components using paths. For this purpose we use a mixture of old and classical techniques such as the heavy path decomposition of Sleator and Tarjan (J Comput Syst Sci 26:362–391, 〈span〉1983〈/span〉) and the classical Depth-First-Search algorithm. Although, these are by now standard techniques, we are not aware of any usage of them in the context of dynamic maintenance of SCCs. Therefore, we expect that our new insights and mixture of new and old techniques will be of independent interest.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We study popular matchings in the many-to-many matching problem, which is given by a graph 〈span〉 〈span〉\(G = (V,E)\)〈/span〉 〈/span〉 and, for every agent 〈span〉 〈span〉\(u\in V\)〈/span〉 〈/span〉, a capacity 〈span〉 〈span〉\(\textsf {cap}(u) \ge 1\)〈/span〉 〈/span〉 and a preference list strictly ranking her neighbors. A matching in 〈em〉G〈/em〉 is popular if it weakly beats every matching in a majority vote when agents cast votes for one matching versus the other according to their preferences. First, we show that when 〈span〉 〈span〉\(G = (A\cup B,E)\)〈/span〉 〈/span〉 is bipartite, e.g., when matching students to courses, every pairwise stable matching is popular. In particular, popular matchings are guaranteed to exist. Our main contribution is to show that a max-size popular matching in 〈em〉G〈/em〉 can be computed in linear time by the 〈em〉2-level Gale–Shapley〈/em〉 algorithm, which is an extension of the classical Gale–Shapley algorithm. We prove its correctness via linear programming. Second, we consider the problem of computing a max-size popular matching in 〈span〉 〈span〉\(G = (V,E)\)〈/span〉 〈/span〉 (not necessarily bipartite) when every agent has capacity 1, e.g., when matching students to dorm rooms. We show that even when 〈em〉G〈/em〉 admits a stable matching, this problem is 〈span〉 〈span〉\(\mathsf {NP}\)〈/span〉 〈/span〉-hard, which is in contrast to the tractability result in bipartite graphs.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉We study problems that integrate buy-at-bulk network design into the classical (connected) facility location problem. In such problems, we need to open facilities, build a routing network, and route every client demand to an open facility. Furthermore, capacities of the edges can be purchased in discrete units from 〈em〉K〈/em〉 different cable types with costs that satisfy economies of scale. We extend the linear programming framework of Talwar (IPCO 2002) for the single-source buy-at-bulk problem to these variants and prove integrality gap upper bounds for both facility location and connected facility location buy-at-bulk problems. For the unconnected variant we prove an integrality gap bound of 〈em〉O〈/em〉(〈em〉K〈/em〉), and for the connected version, we get the first LP-based bound of 〈em〉O〈/em〉(1).〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low independence. A series of papers, beginning with work by Luby (1988), showed that in many cases these techniques can be combined to give deterministic parallel (NC) algorithms for a variety of combinatorial optimization problems, with low time- and processor-complexity. We extend and generalize a technique of Luby for efficiently handling bilinear objective functions. One noteworthy application is an NC algorithm for maximal independent set. On a graph 〈em〉G〈/em〉 with 〈em〉m〈/em〉 edges and 〈em〉n〈/em〉 vertices, this takes 〈span〉 〈span〉\({\tilde{O}}(\log ^2 n)\)〈/span〉 〈/span〉 time and 〈span〉 〈span〉\((m + n) n^{o(1)}\)〈/span〉 〈/span〉 processors, nearly matching the best randomized parallel algorithms. Other applications include reduced processor counts for algorithms of Berger (SIAM J Comput 26:1188–1207, 〈span〉1997〈/span〉) for maximum acyclic subgraph and Gale–Berlekamp switching games. This bilinear factorization also gives better algorithms for problems involving discrepancy. An important application of this is to automata-fooling probability spaces, which are the basis of a notable derandomization technique of Sivakumar (In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp 619–626, 〈span〉2002〈/span〉). Our method leads to large reduction in processor complexity for a number of derandomization algorithms based on automata-fooling, including set discrepancy and the Johnson–Lindenstrauss Lemma.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Let 〈span〉 〈span〉\(\mathcal {P}(G,X)\)〈/span〉 〈/span〉 be a property associating a boolean value to each pair (〈em〉G〈/em〉, 〈em〉X〈/em〉) where 〈em〉G〈/em〉 is a graph and 〈em〉X〈/em〉 is a vertex subset. Assume that 〈span〉 〈span〉\(\mathcal {P}\)〈/span〉 〈/span〉 is expressible in counting monadic second order logic (CMSO) and let 〈em〉t〈/em〉 be an integer constant. We consider the following optimization problem: given an input graph 〈span〉 〈span〉\(G=(V,E)\)〈/span〉 〈/span〉, find subsets 〈span〉 〈span〉\(X\subseteq F \subseteq V\)〈/span〉 〈/span〉 such that the treewidth of 〈em〉G〈/em〉[〈em〉F〈/em〉] is at most 〈em〉t〈/em〉, property 〈span〉 〈span〉\(\mathcal {P}(G[F],X)\)〈/span〉 〈/span〉 is true and 〈em〉X〈/em〉 is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., 〈span〉Longest Induced Path〈/span〉, 〈span〉Maximum Induced Forest〈/span〉, 〈span〉Independent〈/span〉〈span〉 〈span〉\(\mathcal {H}\)〈/span〉 〈/span〉-〈span〉Packing〈/span〉, etc. Fomin et al. (SIAM J Comput 44(1):54–87, 〈span〉2015〈/span〉) proved that the problem is polynomial on the class of graph 〈span〉 〈span〉\({\mathcal {G}}_{{\text {poly}}}\)〈/span〉 〈/span〉, i.e. the graphs having at most 〈span〉 〈span〉\({\text {poly}}(n)\)〈/span〉 〈/span〉 minimal separators for some polynomial 〈span〉 〈span〉\({\text {poly}}\)〈/span〉 〈/span〉. Here we consider the class 〈span〉 〈span〉\({\mathcal {G}}_{{\text {poly}}}+ kv\)〈/span〉 〈/span〉, formed by graphs of 〈span〉 〈span〉\({\mathcal {G}}_{{\text {poly}}}\)〈/span〉 〈/span〉 to which we add a set of at most 〈em〉k〈/em〉 vertices with arbitrary adjacencies, called 〈em〉modulator〈/em〉. We prove that the generic optimization problem is fixed parameter tractable on 〈span〉 〈span〉\({\mathcal {G}}_{{\text {poly}}}+ kv\)〈/span〉 〈/span〉, with parameter 〈em〉k〈/em〉, if the modulator is also part of the input.〈/p〉

Description: 〈h3〉Abstract〈/h3〉 〈p〉Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is 〈span〉NP〈/span〉-complete, substantial effort has been dedicated to determining the complexity of deciding if a graph has a square root belonging to some specific graph class 〈span〉 〈span〉\({{\mathcal {H}}}\)〈/span〉 〈/span〉. There are both polynomial-time solvable and 〈span〉NP〈/span〉-complete results in this direction, depending on 〈span〉 〈span〉\({{\mathcal {H}}}\)〈/span〉 〈/span〉. We present a general framework for the problem if 〈span〉 〈span〉\(\mathcal{H}\)〈/span〉 〈/span〉 is a class of sparse graphs. This enables us to generalize a number of known results and to give polynomial-time algorithms for the cases where 〈span〉 〈span〉\({{\mathcal {H}}}\)〈/span〉 〈/span〉 is the class of outerplanar graphs and 〈span〉 〈span〉\({{\mathcal {H}}}\)〈/span〉 〈/span〉 is the class of graphs of pathwidth at most 2.〈/p〉

Description: The NP -complete Permutation Pattern Matching problem asks whether a k -permutation P is contained in a n -permutation T as a pattern. This is the case if there exists an order-preserving embedding of P into T . In this paper, we present a fixed-parameter algorithm solving this problem with a worst-case runtime of \({\mathcal O}(1.79^{\mathsf {run}(T)}\cdot n\cdot k)\) , where \(\mathsf {run}(T)\) denotes the number of alternating runs of T . This algorithm is particularly well-suited for instances where T has few runs, i.e., few ups and downs. Moreover, since \(\mathsf {run}(T)〈n\) , this can be seen as a \({\mathcal O}(1.79^{n}\cdot n\cdot k)\) algorithm which is the first to beat the exponential \(2^n\) runtime of brute-force search. Furthermore, we prove that under standard complexity theoretic assumptions such a fixed-parameter tractability result is not possible for \(\mathsf {run}(P)\) .

Description: We study the following optimization problem. The input is a number \(k\) and a directed graph with a specified “start” vertex, each of whose vertices may have one “memory bank requirement”, an integer. There are \(k\) “registers”, labeled \(1, \ldots , k\) . A valid solution associates to the vertices with no bank requirement one or more “load instructions” \(L[b,j]\) , for bank \(b\) and register \(j\) , such that every directed trail from the start vertex to some vertex with bank requirement \(c\) contains a vertex \(u\) that has been associated \(L[c,i]\) (for some register \(i \le k\) ) and no vertex following \(u\) in the trail has been associated an \(L[b,i]\) , for any other bank \(b\) . The objective is to minimize the total number of associated load instructions. We give a \(k(k+1)\) -approximation algorithm based on linear programming rounding, with \((k+1)\) being the best possible unless Vertex Cover has approximation \(2 - {\epsilon }\) for \({\epsilon }〉 0\) . We also present a \(O(k \log n)\) approximation, with \(n\) being the number of vertices in the input directed graph. Based on the same linear program, another rounding method outputs a valid solution with objective at most \(2k\) times the optimum for \(k\) registers, using \(2k-1\) registers.

Description: A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled (that is, the ring is anonymous). We present a unified approach to solve three important problems: the exclusive perpetual exploration, the exclusive perpetual clearing, and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often while avoiding that two robots occupy a same node (exclusivity property); in exclusive perpetual clearing (also known as graph searching), the team of robots aims at clearing the whole ring infinitely often (an edge is cleared if it is traversed by a robot or if both its endpoints are occupied); and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the Look–Compute–Move model where the robots cannot communicate but can perceive the positions of other robots. Each robot is equipped with visibility sensors and motion actuators, and it operates in asynchronous cycles. In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it eventually moves to this neighbor (Move). Moreover, robots are endowed with very weak capabilities. Namely, they are anonymous, asynchronous, oblivious, uniform (execute the same algorithm) and have no common sense of orientation. In this setting, we devise algorithms that, starting from an exclusive and rigid (i.e. aperiodic and asymmetric) configuration, solve the three above problems in anonymous ring-topologies.

Description: This paper provides a systematic study of several proposed measures for online algorithms in the context of a specific problem, namely, the two server problem on three colinear points. Even though the problem is simple, it encapsulates a core challenge in online algorithms which is to balance greediness and adaptability. We examine Competitive Analysis, the Max/Max Ratio, the Random Order Ratio, Bijective Analysis and Relative Worst Order Analysis, and determine how these measures compare the Greedy Algorithm, Double Coverage, and Lazy Double Coverage, commonly studied algorithms in the context of server problems. We find that by the Max/Max Ratio and Bijective Analysis, Greedy is the best of the three algorithms. Under the other measures, Double Coverage and Lazy Double Coverage are better, though Relative Worst Order Analysis indicates that Greedy is sometimes better. Only Bijective Analysis and Relative Worst Order Analysis indicate that Lazy Double Coverage is better than Double Coverage. Our results also provide the first proof of optimality of an algorithm under Relative Worst Order Analysis.

Description: In several areas, for example in bioinformatics and in AI planning, the Shortest Common Superstring problem (SCS) and variants thereof have been successfully applied for string comparison. In this paper we consider two variants of SCS recently introduced, namely Restricted Common Superstring (RCS) and Swapped Common Superstring (SRCS). In RCS we are given a set \(S\) of strings and a multiset \(\mathcal {M}\) of symbols, and we look for an ordering \(\mathcal {M}_o\) of \(\mathcal {M}\) such that the number of input strings which are substrings of \(\mathcal {M}_o\) is maximized. In SRCS we are given a set \(S\) of strings and a text \(\mathcal {T}\) , and we look for a swap ordering \(\mathcal {T}_o\) of \(\mathcal {T}\) (an ordering of \(\mathcal {T}\) obtained by swapping only some pairs of adjacent symbols) such that the number of input strings which are substrings of \(\mathcal {T}_o\) is maximized. In this paper we propose a multivariate algorithmic analysis of the complexity of the two problems, aiming at determining how different parameters influence the complexity of the two problems. We consider as interesting parameters the size of the solutions (that is the number of input strings contained in the computed superstring), the maximum length of the given input strings, the size of the alphabet over which the input strings range. First, we give two fixed-parameter algorithms, where the parameter is the size of the solution, for SRCS and lRCS (the RCS problem restricted to strings of length bounded by a parameter \(\ell \) ). Furthermore, we complement these results by showing that SRCS and lRCS do not admit a polynomial kernel unless \(NP \subseteq coNP/Poly\) . Then, we show that SRCS is APX-hard even when the input strings have length bounded by a constant (equal to \(10\) ) or are over a binary alphabet.

Description: In recent years a large number of problems have been considered in external memory models of computation, where the complexity measure is the number of blocks of data that are moved between slow external memory and fast internal memory (also called I/Os). In practice, however, internal memory time often dominates the total running time once I/O-efficiency has been obtained. In this paper we initiate a study of algorithms for fundamental problems that are simultaneously I/O-efficient and internal memory efficient in the RAM model of computation. For sorting the conventional wisdom is to use merging base algorithms in external memory but we describe how this leads to suboptimal RAM performance. However, by using a splitting based algorithm in combination with existing RAM sorting techniques we obtain a sorting algorithm that is both I/O and RAM model efficient. Furthermore, we design an I/O- and RAM-efficient priority queue. Finally, we prove a sorting lower bound that shows that in most cases our results are optimal both in terms of I/O and internal computation.

Description: Mutation region detection is the first step of searching for a disease gene and has facilitated the identification of several hundred human genes that can harbor mutations leading to a disease phenotype. Recently, the closest shared center problem (CSC) was proposed as a core to solve the mutation region detection problem when the pedigree is not given (Ma et al. in IEEE ACM Trans Comput Biol Bioinform 9(2):372–384, 2012 ). A ratio-2 approximation algorithm was proposed for the CSC problem in Ma et al. (IEEE ACM Trans Comput Biol Bioinform 9(2):372–384, 2012 ). In this paper, we will design a polynomial time approximation scheme for this problem.

Description: We consider d -dimensional lattice path models restricted to the first orthant whose defining step sets exhibit reflective symmetry across every axis. Given such a model, we provide explicit asymptotic enumerative formulas for the number of walks of a fixed length: the exponential growth is given by the number of distinct steps a model can take, while the sub-exponential growth depends only on the dimension of the underlying lattice and the number of steps moving forward in each coordinate. The generating function of each model is first expressed as the diagonal of a multivariate rational function, then asymptotic expressions are derived by analyzing the singular variety of this rational function. Additionally, we show how to compute subdominant growth, reflect on the difference between rational diagonals and differential equations as data structures for D-finite functions, and show how to determine first order asymptotics for the subset of walks that start and end at the origin.

Description: We investigate the design of dynamic programming algorithms in unreliable memories, i.e., in the presence of errors that lead the logical state of some bits to be read differently from how they were last written. Assuming that a limited number of memory faults can be inserted at run-time by an adversary with unbounded computational power, we obtain the first resilient algorithms for a broad range of dynamic programming problems, devising a general framework that can be applied to both iterative and recursive implementations. Besides all local dependency problems, where updates to table entries are determined by the contents of neighboring cells, we also settle challenging non-local problems, such as all-pairs shortest paths and matrix multiplication. All our algorithms are correct with high probability and match the running time of their standard non-resilient counterparts while tolerating a polynomial number of faults. The recursive algorithms are also cache-efficient and can tolerate faults at any level of the memory hierarchy. Our results exploit a careful combination of data replication, majority techniques, fingerprint computations, and lazy fault detection. To cope with the complex data access patterns induced by some of our algorithms, we also devise amplified fingerprints, which might be of independent interest in the design of resilient algorithms for different problems.

Description: We show that the quantum query complexity of detecting if an n -vertex graph contains a triangle is \(O(n^{9/7})\) . This improves the previous best algorithm of Belovs (Proceedings of 44th symposium on theory of computing conference, pp 77–84, 2012 ) making \(O(n^{35/27})\) queries. For the problem of determining if an operation \(\circ : S \times S \rightarrow S\) is associative, we give an algorithm making \(O(|S|^{10/7})\) queries, the first improvement to the trivial \(O(|S|^{3/2})\) application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm.