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: 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: 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: 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: 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: 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.

Description: Drawing a random variate from a given binomial distribution B ( n ,  p ) is an important subroutine in many large-scale simulations. The naive algorithm takes \(\mathcal {O}(n)\) time w.h.p. in the WordRAM model, which is too slow in many settings, though to its credit, it does not suffer from precision loss. The problem of sampling from a binomial distribution in sublinear time has been extensively studied and implemented in such packages as R [ 22 ] and the GNU Scientific Library  [ 11 ], however, all previous sublinear-time algorithms involve precision loss, which introduces artifacts such as discontinuities into the sampling. In this paper, we present the first algorithm, to the best of our knowledge, that samples binomial distributions in sublinear time with no precision loss. We assume that each bit of p can be obtained in \(\mathcal {O}(1)\) time.

Description: In the 3SUM problem we are given three lists \(\mathcal {A}\) , \(\mathcal {B}\) , \(\mathcal {C}\) , of n real numbers, and are asked to find \((a,b,c)\in \mathcal {A}\times \mathcal {B}\times \mathcal {C}\) such that \(a+b=c\) . The longstanding 3SUM conjecture —that 3SUM could not be solved in subquadratic time—was recently refuted by Grønlund and Pettie. They presented \(\hbox {O}\left( n^2(\log \log n)^{\alpha }/(\log n)^{\beta }\right) \) algorithms for 3SUM and for the related problems Convolution3SUM and ZeroTriangle, where \(\alpha \) and \(\beta \) are constants that depend on the problem and whether the algorithm is deterministic or randomized (and for ZeroTriangle the main factor is \(n^3\) rather than \(n^2\) ). We simplify Grønlund and Pettie’s algorithms and obtain better bounds, namely, \(\alpha =\beta =1\) , deterministically. For 3SUM our bound is better than both the deterministic and the randomized bounds of Grønlund and Pettie. For the other problems our bounds are better than their deterministic bounds, and match their randomized bounds.

Description: In this paper, we are concerned with the weighted backup 2-center problem on a tree. The backup 2-center problem is a kind of center facility location problem, in which one is asked to deploy two facilities, with a given probability to fail, in a network. Given that the two facilities do not fail simultaneously, the goal is to find two locations, possibly on edges, that minimize the expected value of the maximum distance over all vertices to their closest functioning facility. In the weighted setting, each vertex in the network is associated with a nonnegative weight, and the distance from vertex u to v is weighted by the weight of u . With the strategy of prune-and-search, we propose a linear time algorithm, which is asymptotically optimal, to solve the weighted backup 2-center problem on a tree.

Description: In an \(\epsilon \) -Nash equilibrium, a player can gain at most \(\epsilon \) by unilaterally changing his behavior. For two-player (bimatrix) games with payoffs in [0, 1], the best-known  \(\epsilon \) achievable in polynomial time is 0.3393 (Tsaknakis and Spirakis in Internet Math 5(4):365–382, 2008 ). In general, for n -player games an \(\epsilon \) -Nash equilibrium can be computed in polynomial time for an \(\epsilon \) that is an increasing function of n but does not depend on the number of strategies of the players. For three-player and four-player games the corresponding values of \(\epsilon \) are 0.6022 and 0.7153, respectively. Polymatrix games are a restriction of general n -player games where a player’s payoff is the sum of payoffs from a number of bimatrix games. There exists a very small but constant \(\epsilon \) such that computing an \(\epsilon \) -Nash equilibrium of a polymatrix game is \(\mathtt {PPAD}\) -hard. Our main result is that a \((0.5+\delta )\) -Nash equilibrium of an n -player polymatrix game can be computed in time polynomial in the input size and \(\frac{1}{\delta }\) . Inspired by the algorithm of Tsaknakis and Spirakis [ 28 ], our algorithm uses gradient descent style approach on the maximum regret of the players. We also show that this algorithm can be applied to efficiently find a \((0.5+\delta )\) -Nash equilibrium in a two-player Bayesian game.

Description: We study the problem of finding a spanning tree with maximum number of leaves. We present a simple, linear time 2-approximation algorithm for this problem, improving on the previous best known algorithm for the problem, which has approximation ratio 3.

Description: In this paper we initiate the study of job scheduling on related and unrelated machines so as to minimize the maximum flow time or the maximum weighted flow time (when each job has an associated weight). Previous work for these metrics considered only the setting of parallel machines, while previous work for scheduling on unrelated machines only considered \(L_p, p〈\infty \) norms. Our main results are: (1) we give an \(\mathcal {O}({\varepsilon }^{-3})\) -competitive algorithm to minimize maximum weighted flow time on related machines where we assume that the machines of the online algorithm can process \(1+{\varepsilon }\) units of a job in 1 time-unit ( \({\varepsilon }\) speed augmentation). (2) For the objective of minimizing maximum flow time on unrelated machines we give a simple \(2/{\varepsilon }\) -competitive algorithm when we augment the speed by \({\varepsilon }\) . For m machines we show a lower bound of \({\varOmega }(m)\) on the competitive ratio if speed augmentation is not permitted. Our algorithm does not assign jobs to machines as soon as they arrive. To justify this “drawback” we show a lower bound of \({\varOmega }(\log m)\) on the competitive ratio of immediate dispatch algorithms. In both these lower bound constructions we use jobs whose processing times are in \(\left\{ 1,\infty \right\} \) , and hence they apply to the more restrictive subset parallel setting. (3) For the objective of minimizing maximum weighted flow time on unrelated machines we establish a lower bound of \({\varOmega }(\log m)\) -on the competitive ratio of any online algorithm which is permitted to use \(s=\mathcal {O}(1)\) speed machines. In our lower bound construction, job j has a processing time of \(p_j\) on a subset of machines and infinity on others and has a weight \(1/p_j\) . Hence this lower bound applies to the subset parallel setting for the special case of minimizing maximum stretch.

Description: A strong direct product theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k . In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct product theorem for the communication complexity of any complete relation in this model. In particular, our result implies a strong direct product theorem for the two-party constant-round public-coin randomized communication complexity of all complete relations. As an immediate application of our result, we get a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain which can be regarded as the special case when the number of messages is one. Our result can be considered as an important progress towards settling the strong direct product conjecture for two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used by Jain. One key tool used in our work and also by Jain is a message compression technique due to Braverman and Rao, who used it to show a direct sum theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol which, for example, has been used by Holenstein for proving a parallel repetition theorem for two-prover games.

Description: Let \(G = (A \cup B, E)\) be a bipartite graph, where every vertex ranks its neighbors in an order of preference (with ties allowed) and let \(r\) be the worst rank used. A matching \(M\) is fair in \(G\) if it has maximum cardinality, subject to this, \(M\) matches the minimum number of vertices to rank  \(r\) neighbors, subject to that, \(M\) matches the minimum number of vertices to rank  \((r-1)\) neighbors, and so on. We show an efficient combinatorial algorithm based on LP duality to compute a fair matching in \(G\) . We also show a scaling based algorithm for the fair b-matching problem. Our two algorithms can be extended to solve other profile-based matching problems. In designing our combinatorial algorithm, we show how to solve a generalized version of the minimum weighted vertex cover problem in bipartite graphs, using a single-source shortest paths computation—this can be of independent interest.

Description: The \(k\) -d tree was one of the first spatial data structures proposed for nearest neighbor search. Its efficacy is diminished in high-dimensional spaces, but several variants, with randomization and overlapping cells, have proved to be successful in practice. We analyze three such schemes. We show that the probability that they fail to find the nearest neighbor, for any data set and any query point, is directly related to a simple potential function that captures the difficulty of the point configuration. We then bound this potential function in several situations of interest: when the data are drawn from a doubling measure; when the data and query distributions are identical and are supported on a set of bounded doubling dimension; and when the data are documents from a topic model.

Description: We present original average-case results on the performance of the Ford–Fulkerson maxflow algorithm on grid graphs (sparse) and random geometric graphs (dense). The analysis technique combines experiments with probability generating functions, stochastic context free grammars and an application of the maximum likelihood principle enabling us to make statements about the performance, where a purely theoretical approach has little chance of success. The methods lends itself to automation allowing us to study more variations of the Ford–Fulkerson maxflow algorithm with different graph search strategies and several elementary operations. A simple depth-first search enhanced with random iterators provides the best performance on grid graphs. For random geometric graphs a simple priority-first search with a maximum-capacity heuristic provides the best performance. Notable is the observation that randomization improves the performance even when the inputs are created from a random process.

Description: The Closest String Problem is defined as follows. Let \(S\) be a set of \(k\) strings \(\{s_1,\ldots ,s_k\}\) , each of length \(\ell \) . Find a string \(s^*\) , such that the maximum Hamming distance of \(s^*\) from each of the strings is minimized. We denote this distance with \(d\) . The string \(s^*\) is called a consensus string. In this paper we present two main algorithms, the Configuration algorithm with \(O(k^2 \ell ^ k)\) running time for this problem, and the Minority algorithm. The problem was introduced by Lanctot et al. [SODA’99 and (Inf Comput 185(1):41–55, 2003 )]. They showed that the problem is \(\mathcal {NP}\) -hard and provided an approximation algorithm based on Integer Programming. Since then the closest string problem has been studied extensively both in computational biology and theoretical computer science. This research can be roughly divided into three categories: Approximate, exact and practical solutions. This paper falls under the exact solutions category. Despite the great effort to obtain efficient algorithms for this problem an algorithm with the natural running time of \(O(\ell ^ k)\) was not known. In this paper we close this gap. Our result means that algorithms solving the closest string problem in times \(O(\ell ^2), O(\ell ^3), O(\ell ^4)\) and \(O(\ell ^5)\) exist for the cases of \(k=2,3,4\) and \(5\) , respectively. It is known that, in fact, the cases of \(k=2,3,\) and \(4\) can be solved in linear time. No efficient algorithm is currently known for the case of \(k=5\) . We prove two lemmas, the unit square lemma and the minority lemma that exploit surprising properties of the closest string problem and enable constructing the closest string in a sequential fashion. These lemmas with some additional ideas give a \(O(\ell ^2)\) algorithm for computing a closest string of \(5\) binary strings. Algorithm Minority is based on these lemmas.

Description: Boldyreva, Palacio and Warinschi introduced a multiple forking game as an extension of general forking. The notion of (multiple) forking is a useful abstraction from the actual simulation of cryptographic scheme to the adversary in a security reduction, and is achieved through the intermediary of a so-called wrapper algorithm. Multiple forking has turned out to be a useful tool in the security argument of several cryptographic protocols. However, a reduction employing multiple forking incurs a significant degradation of \(\text {O}(q^{2n})\) , where \(q\) denotes the upper bound on the underlying random oracle calls and \(n\) , the number of forkings. In this work we take a closer look at the reasons for the degradation with a tighter security bound in mind. We nail down the exact set of conditions for success in the multiple forking game. A careful analysis of the cryptographic schemes and corresponding security reduction employing multiple forking leads to the formulation of ‘dependence’ and ‘independence’ conditions pertaining to the output of the wrapper in different rounds. Based on the ( in )dependence conditions we propose a general framework of multiple forking and a General Multiple Forking Lemma. Leveraging ( in )dependence to the full allows us to improve the degradation factor in the multiple forking game by a factor of \(\text {O}({q^n})\) . By implication, the cost of a single forking involving two random oracles (augmented forking) matches that involving a single random oracle (elementary forking). Finally, we study the effect of these observations on the concrete security of existing schemes employing multiple forking. We conclude that by careful design of the protocol (and the wrapper in the security reduction) it is possible to harness our observations to the full extent.

Description: The generalized function matching (GFM) problem has been intensively studied starting with Ehrenfreucht and Rozenberg (Inf Process Lett 9(2):86–88, 1979 ). Given a pattern p and a text t, the goal is to find a mapping from the letters of p to non-empty substrings of t, such that applying the mapping to p results in t. Very recently, the problem has been investigated within the framework of parameterized complexity (Fernau et al. in FSTTCS, 2013 ). In this paper we study the parameterized complexity of the optimization variant of GFM (called Max-GFM), which has been introduced in Amir and Amihood (J Discrete Algorithms 5(3):514–523, 2007 ). Here, one is allowed to replace some of the pattern letters with some special symbols “?”, termed wildcards or don’t cares, which can be mapped to an arbitrary substring of the text. The goal is to minimize the number of wildcards used. We give a complete classification of the parameterized complexity of Max-GFM and its variants under a wide range of parameterizations, such as, the number of occurrences of a letter in the text, the size of the text alphabet, the number of occurrences of a letter in the pattern, the size of the pattern alphabet, the maximum length of a string matched to any pattern letter, the number of wildcards and the maximum size of a string that a wildcard can be mapped to.

Description: We study the problem of augmenting a weighted graph by inserting edges of bounded total cost while minimizing the diameter of the augmented graph. Our main result is an FPT \(4\) -approximation algorithm for the problem.

Description: We consider range queries that search for low-frequency elements (least frequent elements and \(\alpha \) -minorities) in arrays. An \(\alpha \) -minority of a query range has multiplicity no greater than an \(\alpha \) fraction of the elements in the range. Our data structure for the least frequent element range query problem requires \(O(n)\) space, \(O(n^{3/2})\) preprocessing time, and \(O(\sqrt{n})\) query time. A reduction from boolean matrix multiplication to this problem shows the hardness of simultaneous improvements in both preprocessing time and query time. Our data structure for the \(\alpha \) -minority range query problem requires \(O(n)\) space, supports queries in \(O(1/\alpha )\) time, and allows \(\alpha \) to be specified at query time.

Description: A graph is 1-planar if it can be embedded in the plane with at most one crossing per edge. It is known that the problem of testing 1-planarity of a graph is NP-complete. In this paper, we study outer-1-planar graphs. A graph is outer-1-planar if it has an embedding in which every vertex is on the outer face and each edge has at most one crossing. We present a linear time algorithm to test whether a given graph is outer-1-planar. The algorithm can be used to produce an outer-1-planar embedding in linear time if it exists.

Description: In memory-constrained algorithms, access to the input is restricted to be read-only, and the number of extra variables that the algorithm can use is bounded. In this paper we introduce the compressed stack technique , a method that allows to transform algorithms whose main memory consumption takes the form of a stack into memory-constrained algorithms. Given an algorithm \(\mathcal {A}\) that runs in \(O(n)\) time using a stack of length \(\Theta (n)\) , we can modify it so that it runs in \(O(n^2\log n/2^s)\) time using a workspace of \(O(s)\) variables (for any \(s\in o(\log n)\) ) or \(O(n^{1+1/\log p})\) time using \(O(p\log _p n)\) variables (for any \(2\le p\le n\) ). We also show how the technique can be applied to solve various geometric problems, namely computing the convex hull of a simple polygon, a triangulation of a monotone polygon, the shortest path between two points inside a monotone polygon, a 1-dimensional pyramid approximation of a 1-dimensional vector, and the visibility profile of a point inside a simple polygon. Our approach improves or matches up to a \(O(\log n)\) factor the running time of the best-known results for these problems in constant-workspace models (when they exist), and gives a trade-off between the size of the workspace and running time. To the best of our knowledge, this is the first general framework for obtaining memory-constrained algorithms.

Description: Given an input undirected graph \(G=(V,E)\) , we say that a vertex \(\ell \) separates \(u\) from \(v\) (where \(u,v\in V\) ) if the distance between \(u\) and \(\ell \) differs from the distance from \(v\) to \(\ell \) . A set of vertices \(L\subseteq V\) is a feasible solution if for every pair of vertices, \(u,v\in V\) ( \(u\ne v\) ), there is a vertex \(\ell \in L\) that separates \(u\) from \(v\) . Such a feasible solution is called a landmark set , and the metric dimension of a graph is the minimum cardinality of a landmark set. Here, we extend this well-studied problem to the case where each vertex \(v\) has a non-negative cost, and the goal is to find a feasible solution with a minimum total cost. This weighted version is NP-hard since the unweighted variant is known to be NP-hard. We show polynomial time algorithms for the cases where \(G\) is a path, a tree, a cycle, a cograph, a \(k\) -edge-augmented tree (that is, a tree with additional \(k\) edges) for a constant value of \(k\) , and a (not necessarily complete) wheel. The results for paths, trees, cycles, and complete wheels extend known polynomial time algorithms for the unweighted version, whereas the other results are the first known polynomial time algorithms for these classes of graphs even for the unweighted version. Next, we extend the set of graph classes for which computing the unweighted metric dimension of a graph is known to be NP-hard. We show that for split graphs, bipartite graphs, co-bipartite graphs, and line graphs of bipartite graphs, the problem of computing the unweighted metric dimension of the graph is NP-hard.

Description: Back in the eighties, Heath [Algorithms for embedding graphs in books. PhD thesis, University of North Carolina, Chapel Hill, 1985 ] showed that every 3-planar graph is subhamiltonian and asked whether this result can be extended to a class of graphs of degree greater than three. In this paper we affirmatively answer this question for the class of 4-planar graphs. Our contribution consists of two algorithms: The first one is limited to triconnected graphs, but runs in linear time and uses existing methods for computing hamiltonian cycles in planar graphs. The second one, which solves the general case of the problem, is a quadratic-time algorithm based on the book embedding viewpoint of the problem.

Description: We give an algorithm for computing the directed pathwidth of a digraph with n vertices in \(O(1.89^{n})\) time. This is the first algorithm with running time better than the straightforward \(O^{*}(2^n)\) . As a special case, it computes the pathwidth of an undirected graph in the same amount of time, improving on the algorithm due to Suchan and Villanger which runs in \(O(1.9657^n)\) time.

Description: We show that all minimal edge dominating sets of a graph can be generated in incremental polynomial time. We present an algorithm that solves the equivalent problem of enumerating minimal (vertex) dominating sets of line graphs in incremental polynomial, and consequently output polynomial, time. Enumeration of minimal dominating sets in graphs has recently been shown to be equivalent to enumeration of minimal transversals in hypergraphs. The question whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a fundamental and challenging question; it has been open for several decades and has triggered extensive research. To obtain our result, we present a flipping method to generate all minimal dominating sets of a graph. Its basic idea is to apply a flipping operation to a minimal dominating set \(D^*\) to generate minimal dominating sets \(D\) such that \(G[D]\) contains more edges than \(G[D^*]\) . We show that the flipping method works efficiently on line graphs, resulting in an algorithm with delay \(O(n^2m^2|\mathcal {L}|)\) between each pair of consecutively output minimal dominating sets, where \(n\) and \(m\) are the numbers of vertices and edges of the input graph, respectively, and \(\mathcal {L}\) is the set of already generated minimal dominating sets. Furthermore, we are able to improve the delay to \(O(n^2m|\mathcal {L}|)\) on line graphs of bipartite graphs. Finally we show that the flipping method is also efficient on graphs of large girth, resulting in an incremental polynomial time algorithm to enumerate the minimal dominating sets of graphs of girth at least 7.

Description: We present a new overlay, called the Deterministic Decentralized tree ( \(D^2\) -tree). The \(D^2\) -tree compares favorably to other overlays for the following reasons: (a) it provides matching and better complexities, which are deterministic for the supported operations; (b) the management of nodes (peers) and elements are completely decoupled from each other; and (c) an efficient deterministic load-balancing mechanism is presented for the uniform distribution of elements into nodes, while at the same time probabilistic optimal bounds are provided for the congestion of operations at the nodes. The load-balancing scheme of elements into nodes is deterministic and general enough to be applied to other hierarchical tree-based overlays. This load-balancing mechanism is based on an innovative lazy weight-balancing mechanism, which is interesting in its own right.

Description: The boxicity of a graph G is the least integer d such that G has an intersection model of axis-aligned d -dimensional boxes. Boxicity , the problem of deciding whether a given graph G has boxicity at most d , is NP-complete for every fixed \(d \ge 2\) . We show that Boxicity is fixed-parameter tractable when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Adiga et al. ( 2010 ), that Boxicity is fixed-parameter tractable in the vertex cover number. Moreover, we show that Boxicity admits an additive 1-approximation when parameterized by the pathwidth of the input graph. Finally, we provide evidence in favor of a conjecture of Adiga et al. ( 2010 ) that Boxicity remains NP-complete even on graphs of constant treewidth.

Description: We give a subexponential fixed parameter algorithm for one-sided crossing minimization. It runs in \(O(k2^{\sqrt{2k}} + n)\) time, where n is the number of vertices of the given graph and parameter k is the number of crossings. The exponent of \(O(\sqrt{k})\) in this bound is asymptotically optimal assuming the Exponential Time Hypothesis and the previously best known algorithm runs in \(2^{O(\sqrt{k}\log k)} + n^{O(1)}\) time. We achieve this significant improvement by the use of a certain interval graph naturally associated with the problem instance and a simple dynamic program on this interval graph. The linear dependency on n is also achieved through the use of this interval graph.

Description: Winfree’s abstract Tile Assembly Model is a model of molecular self-assembly of DNA complexes known as tiles, which float freely in solution and attach one at a time to a growing “seed” assembly based on specific binding sites on their four sides. We show that there is a polynomial-time algorithm that, given an \(n \times n\) square, finds the minimal tile system (i.e., the system with the smallest number of distinct tile types) that uniquely self-assembles the square, answering an open question of Adleman et al. ( Combinatorial optimization problems in self-assembly , STOC 2002 ). Our investigation leading to this algorithm reveals other positive and negative results about the relationship between the size of a tile system and its “temperature” (the binding strength threshold required for a tile to attach).

Description: In many stream monitoring situations, the data arrival rate is so high that it is not even possible to observe each element of the stream. The most common solution is to sub-sample the data stream and use the sample to infer properties and estimate aggregates of the original stream. However, in many cases, the estimation of aggregates on the original stream cannot be accomplished through simply estimating them on the sampled stream, followed by a normalization. We present algorithms for estimating frequency moments, support size, entropy, and heavy hitters of the original stream, through a single pass over the sampled stream.

Description: The k -feedback arc set problem is to determine whether there is a set  F of at most  k arcs in a directed graph  G such that the removal of  F makes  G acyclic. The k -feedback arc set problems in tournaments and bipartite tournaments ( k -FAST and k -FASBT) have applications in ranking aggregation and have been extensively studied from the viewpoint of parameterized complexity. By introducing a new concept called “bimodule”, we provide a problem kernel with O ( k 2 ) vertices for k -FASBT, which improves the previous result by a factor of  k .

Description: The 1-Steiner tree problem, the problem of constructing a Steiner minimum tree containing at most one Steiner point, has been solved in the Euclidean plane by Georgakopoulos and Papadimitriou using plane subdivisions called oriented Dirichlet cell partitions. Their algorithm produces an optimal solution within O ( n 2 ) time. In this paper we generalise their approach in order to solve the k -Steiner tree problem, in which the Steiner minimum tree may contain up to k Steiner points for a given constant k . We also extend their approach further to encompass other normed planes, and to solve a much wider class of problems, including the k -bottleneck Steiner tree problem and other generalised k -Steiner tree problems. We show that, for any fixed k , such problems can be solved in O ( n 2 k ) time.

Description: The problem of metrical service systems with multiple servers ( \((k,l)\) -MSSMS), proposed by Feuerstein (LATIN’98: Theoretical Informatics, Third Latin American Symposium, 1998 ), is to service requests, each of which is an \(l\) -point subset of a metric space, using \(k\) servers in an online manner, minimizing the distance traveled by the servers. We prove that Feuerstein’s deterministic algorithm for \((k,l)\) -MSSMS actually achieves an improved competitive ratio of \(k\left( {{k+l}\atopwithdelims (){l}}-1\right) \) on uniform metrics. In the randomized online setting on uniform metrics, we give an algorithm which achieves a competitive ratio \(\mathcal {O}(k^3\log l)\) , beating the deterministic lower bound of \({{k+l}\atopwithdelims (){l}}-1\) . We prove that any randomized algorithm for \((k,l)\) -MSSMS on uniform metrics must be \(\varOmega (\log kl)\) -competitive. For the offline \((k,l)\) -MSSMS, we give a factor \(l\) pseudo-approximation algorithm using \(kl\) servers on any metric space, and prove a matching hardness result, that a pseudo-approximation using less than \(kl\) servers is unlikely, even on uniform metrics.

Description: The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. The problem has important applications in numerical algebra, in particular in sparse matrix computations. We develop kernelization algorithms for the problem on several classes of sparse graphs. We obtain linear kernels on planar graphs, and kernels of size \(\mathcal {O}(k^{3/2})\) in graphs excluding some fixed graph as a minor and in graphs of bounded degeneracy. As a byproduct of our results, we obtain approximation algorithms with approximation ratios \(\mathcal {O}(\log{k})\) on planar graphs and \(\mathcal {O}(\sqrt{k}\log{k})\) on H -minor-free graphs. These results significantly improve the previously known kernelization and approximation results for Minimum Fill-in on sparse graphs.

Description: The min-rank of a graph was introduced by Haemers (Algebr. Methods Graph Theory 25:267–272, 1978 ) to bound the Shannon capacity of a graph. This parameter of a graph has recently gained much more attention from the research community after the work of Bar-Yossef et al. (in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 197–206, 2006 ). In their paper, it was shown that the min-rank of a graph \(\mathcal {G}\) characterizes the optimal scalar linear solution of an instance of the Index Coding with Side Information (ICSI) problem described by the graph \(\mathcal {G}\) . It was shown by Peeters (Combinatorica 16(3):417–431, 1996 ) that computing the min-rank of a general graph is an NP-hard problem. There are very few known families of graphs whose min-ranks can be found in polynomial time. In this work, we introduce a new family of graphs with efficiently computed min-ranks. Specifically, we establish a polynomial time dynamic programming algorithm to compute the min-ranks of graphs having simple tree structures . Intuitively, such graphs are obtained by gluing together, in a tree-like structure, any set of graphs for which the min-ranks can be determined in polynomial time. A polynomial time algorithm to recognize such graphs is also proposed.

Description: The bisection problem asks for a partition of the \(n\) vertices of a graph into two sets of size at most  \(\lceil n/2\rceil \) , so that the number of edges connecting the sets is minimised. A grid graph is a finite connected subgraph of the infinite two-dimensional grid. It is called solid if it has no holes. Papadimitriou and Sideri (Theory Comput Syst 29:97–110, 1996 ) gave an \(O(n^5)\) time algorithm to solve the bisection problem on solid grid graphs. We propose a novel approach that exploits structural properties of optimal cuts within a dynamic program. We show that our new technique leads to an \(O(n^4)\) time algorithm.

Description: We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called terminals in  \({\mathbb {R}}^{d}\) , find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pair’s Manhattan (that is, L 1 -) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless \({\mathcal{P}} = \mathcal{NP}\) ). Approximation algorithms are known for 2D, but not for 3D. We present, for any fixed dimension  d and any ε 〉0, an O ( n ε )-approximation algorithm. For 3D, we also give a 4( k −1)-approximation algorithm for the case that the terminals are contained in the union of k ≥2 parallel planes.

Description: We study the behavior of a population-based EA and the Max–Min Ant System (MMAS) on a family of deterministically-changing fitness functions, where, in order to find the global optimum, the algorithms have to find specific local optima within each of a series of phases. In particular, we prove that a (2+1) EA with genotype diversity is able to find the global optimum of the Maze function, previously considered by Kötzing and Molter [ 9 ], in polynomial time. This is then generalized to a hierarchy result stating that for every \(\mu \) , a ( \(\mu \) +1) EA with genotype diversity is able to track a Maze function extended over a finite alphabet of \(\mu \) symbols, whereas population size  \(\mu -1\) is not sufficient. Furthermore, we show that MMAS does not require additional modifications to track the optimum of the finite-alphabet Maze functions, and, using a novel drift statement to simplify the analysis, reduce the required phase length of the Maze function.

Description: The paper presents an \(O^*(1.2312^n)\) -time and polynomial-space algorithm for the traveling salesman problem in an \(n\) -vertex graph with maximum degree 3. This improves all previous time bounds of polynomial-space algorithms for this problem. Our algorithm is a simple branch-and-search algorithm with only one branch rule designed on a cut-circuit structure of a graph induced by unprocessed edges. To improve a time bound by a simple analysis on measure and conquer, we introduce an amortization scheme over the cut-circuit structure by defining the measure of an instance to be the sum of not only weights of vertices but also weights of connected components of the induced graph.

Description: We consider a basic problem in unsupervised learning: learning an unknown Poisson binomial distribution . A Poisson binomial distribution (PBD) over \(\{0,1,\ldots ,n\}\) is the distribution of a sum of \(n\) independent Bernoulli random variables which may have arbitrary, potentially non-equal, expectations. These distributions were first studied by Poisson (Recherches sur la Probabilitè des jugements en matié criminelle et en matiére civile. Bachelier, Paris, 1837 ) and are a natural \(n\) -parameter generalization of the familiar Binomial Distribution. Surprisingly, prior to our work this basic learning problem was poorly understood, and known results for it were far from optimal. We essentially settle the complexity of the learning problem for this basic class of distributions. As our first main result we give a highly efficient algorithm which learns to \(\epsilon \) -accuracy (with respect to the total variation distance) using \(\tilde{O}(1/ \epsilon ^{3})\) samples independent of \(n\) . The running time of the algorithm is quasilinear in the size of its input data, i.e., \(\tilde{O}(\log (n)/\epsilon ^{3})\) bit-operations (we write \(\tilde{O}(\cdot )\) to hide factors which are polylogarithmic in the argument to \(\tilde{O}(\cdot )\) ; thus, for example, \(\tilde{O}(a \log b)\) denotes a quantity which is \(O(a \log b \cdot \log ^c(a \log b))\) for some absolute constant \(c\) . Observe that each draw from the distribution is a \(\log (n)\) -bit string). Our second main result is a proper learning algorithm that learns to \(\epsilon \) -accuracy using \(\tilde{O}(1/\epsilon ^{2})\) samples, and runs in time \((1/\epsilon )^{\mathrm {poly}(\log (1/\epsilon ))} \cdot \log n\) . This sample complexity is nearly optimal, since any algorithm for this problem must use \(\Omega (1/\epsilon ^{2})\) samples. We also give positive and negative results for some extensions of this learning problem to weighted sums of independent Bernoulli random variables.

Description: The Two-Handed Tile Assembly Model (2HAM) is a model of algorithmic self-assembly in which large structures, or assemblies of tiles, are grown by the binding of smaller assemblies. In order to bind, two assemblies must have matching glues that can simultaneously touch each other, and stick together with strength that is at least the temperature \(\tau \) , where \(\tau \) is some fixed positive integer. We ask whether the 2HAM is intrinsically universal. In other words, we ask: is there a single 2HAM tile set \(U\) which can be used to simulate any instance of the model? Our main result is a negative answer to this question. We show that for all \(\tau ' 〈 \tau \) , each temperature- \(\tau '\) 2HAM tile system does not simulate at least one temperature- \(\tau \) 2HAM tile system. This impossibility result proves that the 2HAM is not intrinsically universal and stands in contrast to the fact that the (single-tile addition) abstract Tile Assembly Model is intrinsically universal. On the positive side, we prove that, for every fixed temperature  \(\tau \ge 2\) , temperature- \(\tau \) 2HAM tile systems are indeed intrinsically universal. In other words, for each  \(\tau \) there is a single intrinsically universal 2HAM tile set  \(U_{\tau }\) that, when appropriately initialized, is capable of simulating the behavior of any temperature- \(\tau \) 2HAM tile system. As a corollary, we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. Finally, we show that for each  \(\tau \) , there is a temperature- \(\tau \) 2HAM system that simultaneously simulates all temperature- \(\tau \) 2HAM systems.

Description: We present a greedy algorithm for the directed Steiner tree problem (DST), where any tree rooted at any (uncovered) terminal can be a candidate for greedy choice. It will be shown that the algorithm, running in polynomial time for any constant \(l\) , outputs a directed Steiner tree of cost no larger than \(2(l-1)(\ln n+1)\) times the cost of any \(l\) -restricted Steiner tree, which is such a Steiner tree in which every terminal is at most \(l\) arcs away from the root or another terminal. We derive from this result that (1) DST for a class of graphs, including quasi-bipartite graphs, in which the length of paths induced by Steiner vertices is bounded by some constant can be approximated within a factor of \(O(\log n)\) , and (2) the tree cover problem on directed graphs can also be approximated within a factor of \(O(\log n)\) .

Description: We study fault-tolerant spanners in doubling metrics. A subgraph H for a metric space X is called a k -vertex-fault-tolerant t -spanner (( k , t )-VFTS or simply k -VFTS), if for any subset S ⊆ X with | S |≤ k , it holds that d H ∖ S ( x , y )≤ t ⋅ d ( x , y ), for any pair of x , y ∈ X ∖ S . For any doubling metric, we give a basic construction of k -VFTS with stretch arbitrarily close to 1 that has optimal O ( kn ) edges. In addition, we also consider bounded hop-diameter, which is studied in the context of fault-tolerance for the first time even for Euclidean spanners. We provide a construction of k -VFTS with bounded hop-diameter: for m ≥2 n , we can reduce the hop-diameter of the above k -VFTS to O ( α ( m , n )) by adding O ( km ) edges, where α is a functional inverse of the Ackermann’s function. Finally, we construct a fault-tolerant single-sink spanner with bounded maximum degree, and use it to reduce the maximum degree of our basic k -VFTS. As a result, we get a k -VFTS with O ( k 2 n ) edges and maximum degree O ( k 2 ).

Description: The k - Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The List k - Coloring problem requires in addition that every vertex u must receive a color from some given set L ( u )⊆{1,…, k }. Let P n denote the path on n vertices, and G + H and rH the disjoint union of two graphs G and H and r copies of H , respectively. For any two fixed integers k and r , we show that List k - Coloring can be solved in polynomial time for graphs with no induced rP 1 + P 5 , hereby extending the result of Hoàng, Kamiński, Lozin, Sawada and Shu for graphs with no induced  P 5 . Our result is tight; we prove that for any graph H that is a supergraph of P 1 + P 5 with at least 5 edges, already List 5- Coloring is NP -complete for graphs with no induced H .

Description: We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism , denoted CHI, which has running time (2 b N ) O (1) , where the parameter b is the maximum size of the color classes of the given hypergraphs and N is the input size. We also describe an fpt algorithm for a parameterized coset intersection problem that is used as a subroutine in our algorithm for CHI.

Description: Given two sets in the plane, R of n (terminal) points and S of m (Steiner) points, a full Steiner tree is a Steiner tree in which all points of R are leaves. In the bottleneck full Steiner tree (BFST) problem, one has to find a full Steiner tree T (with any number of Steiner points from S ), such that the length of the longest edge in T is minimized, and, in the k -BFST problem, has to find a full Steiner tree T with at most k ≤ m Steiner points from S such that the length of the longest edge in T is minimized. The problems are motivated by wireless network design. In this paper, we present an exact algorithm of \({{{\mathcal {O}}}}((n+m)\log^{2}{m})\) time to solve the BFST problem. Moreover, we show that the k -BFST problem is NP-hard and that there exists a polynomial-time approximation algorithm for the problem with performance ratio 4.

Description: We consider the following Tree-Constrained Bipartite Matching problem: Given a bipartite graph G =( V 1 , V 2 , E ) with edge weights \(w:E \mapsto\mathbb{R}_{+}\) , a rooted tree T 1 on the set V 1 and a rooted tree T 2 on the set V 1 , find a maximum weight matching \(\mathcal{M}\) in G , such that none of the matched nodes is an ancestor of another matched node in either of the trees. This generalization of the classical bipartite matching problem appears, for example, in the computational analysis of live cell video data. We show that the problem is \(\mathcal{APX}\) -hard and thus, unless \(\mathcal{P} = \mathcal{NP}\) , disprove a previous claim that it is solvable in polynomial time. Furthermore, we give a 2-approximation algorithm based on a combination of the local ratio technique and a careful use of the structure of basic feasible solutions of a natural LP-relaxation, which we also show to have an integrality gap of 2− o (1). In the second part of the paper, we consider a natural generalization of the problem, where trees are replaced by partially ordered sets (posets). We show that the local ratio technique gives a 2 kρ -approximation for the k -dimensional matching generalization of the problem, in which the maximum number of incomparable elements below (or above) any given element in each poset is bounded by ρ . We finally give an almost matching integrality gap example, and an inapproximability result showing that the dependence on ρ is most likely unavoidable.

Description: Cardinal trees (or tries of degree \(k\) ) are a fundamental data structure, in particular for many text-processing algorithms. Each node in a cardinal tree has at most \(k\) children, each labeled with a symbol from the alphabet \(\{1,\ldots , k\}\) . In this paper we introduce succinct representations for dynamic cardinal trees on \(n\) nodes, requiring \(2n + n\lg {k} + o(n\lg {k})\) bits of space. These are the first dynamic cardinal tree representations that support a (fairly) complete set of operations while using almost optimal space. For \(k= \mathcal {O}(\mathrm{polylog}(n))\) , we show how the navigational and query operations on the tree can be supported in \(\mathcal {O}(1)\) time, while supporting insertions and deletions of leaves in \(\mathcal {O}(1)\) amortized time. For \(k= \omega ({\mathrm{polylog}(n)})\) [and \(\mathcal {O}(n)\) ], we show that the same set of operations can be supported in \(\mathcal {O}(\lg {k}/\lg {\lg {k}})\) time (amortized in the case of insertions/deletions). We also show how to associate \(b\) -bit satellite data to the tree nodes using \(bn+o(n)\) extra bits. Finally, we show how the machinery introduced for dynamic cardinal trees can be adapted to represent dynamic binary trees using \(2n+o(n)\) bits of space, so that the tree operations are supported in \(\mathcal {O}(1)\) time (amortized in the case of insert/delete operations). We support adding satellite data to the tree nodes using \(bn+o(n)\) extra bits [(vs. \(bn+o(bn)\) extra bits of the fastest previous dynamic representation from the literature], while providing several trade-offs for accessing/modifying the data.

Description: We consider the following variant of a classical pursuit-evasion problem: how many pursuers are needed to capture a single ( adversarial ) evader on a closed polyhedral surface in three dimensions? The players move on the polyhedral surface, have the same maximum speed, and are always aware of each others’ current positions. This generalizes the classical lion-and-the-man game, originally proposed by Rado (Littlewood in Littlewood?s miscellany, Cambridge University Press  1986 ), in which the players are restricted to a two-dimensional circular arena. The extension to a polyhedral surface is both theoretically interesting and practically motivated by applications in robotics where the physical environment is often approximated as a polyhedral surface. We analyze the game under the discrete-time model, where the players take alternate turns, however, by choosing an appropriately small time step \(t 〉 0\) , one can approximate the continuous time setting to an arbitrary level of accuracy. Our main result is that four pursuers always suffice (upper bound), and that three are sometimes necessary (lower bound), for catching an adversarial evader on any polyhedral surface with genus zero. Generalizing this bound to surfaces of genus g , we prove the sufficiency of \((4g + 4)\) pursuers. Finally, we show that four pursuers also suffice under the “weighted region” constraints where the movement costs through different regions of the (genus zero) surface have (different) multiplicative weights.

Description: We present a certifying algorithm that tests graphs for 3-edge-connectivity; the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a 2-edge-cut. If it is 3-edge-connected, it returns a construction sequence that constructs the input graph from the graph with two vertices and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity. Additionally, we show how to compute and certify the 3-edge-connected components and a cactus representation of the 2-cuts in linear time. For 3-vertex-connectivity, we show how to compute the 3-vertex-connected components of a 2-connected graph.

Description: We consider the problem of constructing fast and small parallel prefix adders for non-uniform input arrival times. In modern computer chips, adders with up to hundreds of inputs occur frequently, and they are often embedded into more complex circuits, e.g. multipliers, leading to instance-specific non-uniform input arrival times. Most previous results are based on representing binary carry-propagate adders as parallel prefix graphs, in which pairs of generate and propagate signals are combined using complex gates called prefix gates. Examples of commonly-used adders are constructed based on the Kogge–Stone or Ladner–Fischer prefix graphs. Adders constructed in this model usually minimize the delay in terms of these prefix gates. However, the delay in terms of logic gates can be worse by a factor of two. In contrast, we aim to minimize the delay of the underlying logic circuit directly. We prove a lower bound on the delay of a carry bit computation achievable by any prefix carry bit circuit and develop an algorithm that computes a prefix carry bit circuit with optimum delay up to a small additive constant. Our algorithm improves the running time of a previous dynamic program for constructing a prefix carry bit from \(\mathcal {O}(n^3)\) to \(\mathcal {O}(n \log ^2 n)\) while simultaneously improving the delay and size guarantee, where n is the number of bits in the summands. Furthermore, we use this algorithm as a subroutine to compute a full adder in near-linear time, reducing the delay approximation factor of 2 from previous approaches to 1.441 for our algorithm.

Description: We present a new algorithm for subsequence matching in grammar compressed strings. Given a grammar of size n compressing a string of size N and a pattern string of size m over an alphabet of size \(\sigma \) , our algorithm uses \(O(n+\frac{n\sigma }{w})\) space and \(O(n+\frac{n\sigma }{w}+m\log N\log w\cdot occ)\) or \(O(n+\frac{n\sigma }{w}\log w+m\log N\cdot occ)\) time. Here w is the word size and occ is the number of minimal occurrences of the pattern. Our algorithm uses less space than previous algorithms and is also faster for \(occ=o(\frac{n}{\log N})\) occurrences. The algorithm uses a new data structure that allows us to efficiently find the next occurrence of a given character after a given position in a compressed string. This data structure in turn is based on a new data structure for the tree color problem, where the node colors are packed in bit strings.

Description: We introduce a new structure for a set of points in the plane and an angle \(\alpha \) , which is similar in flavor to a bounded-degree MST. We name this structure \(\alpha \) -MST. Let P be a set of points in the plane and let \(0 〈 \alpha \le 2\pi \) be an angle. An \(\alpha \) -ST of P is a spanning tree of the complete Euclidean graph induced by P , with the additional property that for each point \(p \in P\) , the smallest angle around p containing all the edges adjacent to p is at most \(\alpha \) . An \(\alpha \) -MST of P is then an \(\alpha \) -ST of P of minimum weight, where the weight of an \(\alpha \) -ST is the sum of the lengths of its edges. For \(\alpha 〈 \pi /3\) , an \(\alpha \) -ST does not always exist, and, for \(\alpha \ge \pi /3\) , it always exists (Ackerman et al. in Comput Geom Theory Appl 46(3):213–218, 2013 ; Aichholzer et al. in Comput Geom Theory Appl 46(1):17–28, 2013 ; Carmi et al. in Comput Geom Theory Appl 44(9):477–485, 2011 ). In this paper, we study the problem of computing an \(\alpha \) -MST for several common values of \(\alpha \) . Motivated by wireless networks, we formulate the problem in terms of directional antennas. With each point \(p \in P\) , we associate a wedge \({\textsc {w}_{p}}\) of angle \(\alpha \) and apex p . The goal is to assign an orientation and a radius \(r_p\) to each wedge \({\textsc {w}_{p}}\) , such that the resulting graph is connected and its MST is an \(\alpha \) -MST (we draw an edge between p and q if \(p \in {\textsc {w}_{q}}\) , \(q \in {\textsc {w}_{p}}\) , and \(|pq| \le r_p, r_q\) ). We prove that the problem of computing an \(\alpha \) -MST is NP-hard, at least for \(\alpha =\pi \) and \(\alpha =2\pi /3\) , and present constant-factor approximation algorithms for \(\alpha = \pi /2, 2\pi /3, \pi \) . One of our major results is a surprising theorem for \(\alpha = 2\pi /3\) , which, besides being interesting from a geometric point of view, has important applications. For example, the theorem guarantees that given any set P of 3 n points in the plane and any partitioning of the points into n triplets, one can orient the wedges of each triplet independently , such that the graph induced by P is connected. We apply the theorem to the antenna conversion problem and to the orientation and power assignment problem.

Description: We present a technique for representing bounded-degree planar graphs in a succinct fashion while permitting I/O-efficient traversal of paths. Using our representation, a graph with N vertices, (In this paper \(\lg {N}\) denotes \(\log _2{N}\) ) each with an associated key of \(q= \mathrm {O}\left( \lg N\right) \) bits, can be stored in \(Nq+ \mathrm {O}\left( N\right) + \mathrm {o}\left( Nq\right) \) bits and traversing a path of length K takes \(\mathrm {O}\left( K / \lg B\right) \) I/Os, where B denotes the disk block size. By applying our construction to the dual of a terrain represented as a triangular irregular network, we can represent the terrain in the above space bounds and support path traversals on the terrain using \(\mathrm {O}\left( K / \lg B\right) \) I/Os, where K is the number of triangles visited by the path. This is useful for answering a number of queries on the terrain, such as reporting terrain profiles, trickle paths, and connected components.

Description: The projection games (aka Label Cover ) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label Cover . In this paper we design several approximation algorithms for projection games: (1) A polynomial-time approximation algorithm that improves on the previous best approximation by Charikar et al. (Algorithmica 61(1):190–206, 2011 ). (2) A sub-exponential time algorithm with much tighter approximation for the case of smooth projection games. (3) A polynomial-time approximation scheme (PTAS) for projection games on planar graphs and a tight running time lower bound for such approximation schemes. The conference version of this paper had only the PTAS but not the running time lower bound.

Description: This paper provides the first general technique for proving information lower bounds on two-party unbounded-rounds communication problems. We show that the discrepancy lower bound, which applies to randomized communication complexity, also applies to information complexity. More precisely, if the discrepancy of a two-party function f with respect to a distribution \(\mu \) is \(Disc_\mu f\) , then any two party randomized protocol computing f must reveal at least \(\Omega (\log (1/Disc_\mu f))\) bits of information to the participants. As a corollary, we obtain that any two-party protocol for computing a random function on \(\{0,1\}^n\times \{0,1\}^n\) must reveal \(\Omega (n)\) bits of information to the participants. In addition, we prove that the discrepancy of the Greater-Than function is \(\Omega (1/\sqrt{n})\) , which provides an alternative proof to the recent proof of Viola (Proceedings of the twenty-fourth annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, 6–8 Jan 2013, pp 632–651, 2013 ) of the \(\Omega (\log n)\) lower bound on the communication complexity of this well-studied function and, combined with our main result, proves the tight \(\Omega (\log n)\) lower bound on its information complexity. The proof of our main result develops a new simulation procedure that may be of an independent interest. In a followup breakthrough work of Kerenidis et al. (53rd annual IEEE symposium on foundations of computer science, FOCS 2012, New Brunswick, NJ, USA, 20–23 Oct 2012, pp 500–509, 2012 ), our simulation procedure served as a building block towards a proof that almost all known lower bound techniques for communication complexity (and not just discrepancy) apply to information complexity as well.

Description: Say that an edge of a graph G dominates itself and every other edge sharing a vertex of it. An edge dominating set of a graph \(G=(V,E)\) is a subset of edges \(E' \subseteq E\) which dominates all edges of G . In particular, if every edge of G is dominated by exactly one edge of \(E'\) then \(E'\) is a dominating induced matching. It is known that not every graph admits a dominating induced matching, while the problem to decide if it does admit it is NP-complete. In this paper we consider the problems of counting the number of dominating induced matchings and finding a minimum weighted dominating induced matching, if any, of a graph with weighted edges. We describe three exact algorithms for general graphs. The first runs in linear time for a given vertex dominating set of fixed size of the graph. The second runs in polynomial time if the graph admits a polynomial number of maximal independent sets. The third one is an \(O^*(1.1939^n)\) time and polynomial (linear) space, which improves over the existing algorithms for exactly solving this problem in general graphs.

Description: For a graph \(G=(V,E)\) the minimum line-distortion problem asks for the minimum k such that there is a mapping f of the vertices into points of the line such that for each pair of vertices x ,  y the distance on the line \(|f(x) - f(y)|\) can be bounded by the term \(d_G(x, y)\le |f(x)-f(y)|\le k \, d_G(x, y)\) , where \(d_G(x, y)\) is the distance in the graph. The minimum bandwidth problem minimizes the term \(\max _{uv\in E}|f(u)-f(v)|\) , where f is a mapping of the vertices of G into the integers \(\{1, \ldots , n\}\) . We investigate the minimum line-distortion and the minimum bandwidth problems on unweighted graphs and their relations with the minimum length of a Robertson–Seymour’s path-decomposition. The length of a path-decomposition of a graph is the largest diameter of a bag in the decomposition. The path-length of a graph is the minimum length over all its path-decompositions. In particular, we show: there is a simple polynomial time algorithm that embeds an arbitrary unweighted input graph G into the line with distortion \(\mathcal{O}(k^2)\) , where k is the minimum line-distortion of G ; if a graph G can be embedded into the line with distortion k , then G admits a Robertson–Seymour’s path-decomposition with bags of diameter at most k in G ; for every class of graphs with path-length bounded by a constant, there exist an efficient constant-factor approximation algorithm for the minimum line-distortion problem and an efficient constant-factor approximation algorithm for the minimum bandwidth problem; there is an efficient 2-approximation algorithm for computing the path-length of an arbitrary graph; AT-free graphs and some intersection families of graphs have path-length at most 2; for AT-free graphs, there exist a linear time 8-approximation algorithm for the minimum line-distortion problem and a linear time 4-approximation algorithm for the minimum bandwidth problem.

Description: A graph drawn in the plane with \(n\) vertices is \(k\) -fan-crossing free for \(k \geqslant 2\) if there are no \(k+1\) edges \(g,e_1,\ldots , e_k\) , such that \(e_1,e_2,\ldots ,e_k\) have a common endpoint and \(g\) crosses all  \(e_i\) . We prove a tight bound of \(4n-8\) on the maximum number of edges of a \(2\) -fan-crossing free graph, and a tight \(4n-9\) bound for a straight-edge drawing. For \(k \geqslant 3\) , we prove an upper bound of \(3(k-1)(n-2)\) edges. We also discuss generalizations to monotone graph properties.

Description: Given a system of linear equations \(Ax=b\) over the binary field \(\mathbb {F}_2\) and an integer \(t\ge 1\) , we study the following three algorithmic problems: Does \(Ax=b\) have a solution of weight at most t ? Does \(Ax=b\) have a solution of weight exactly t ? Does \(Ax=b\) have a solution of weight at least t ? We investigate the parameterized complexity of these problems with t as parameter. A special aspect of our study is to show how the maximum multiplicity k of variable occurrences in \(Ax=b\) influences the complexity of the problem. We show a sharp dichotomy: for each \(k\ge 3\) the first two problems are \(\textsf {W[1] }\) -hard [which strengthens and simplifies a result of Downey et al. (SIAM J Comput 29(2), 545–570, 1999 )]. For \(k=2\) , the problems turn out to be intimately connected to well-studied matching problems and can be efficiently solved using matching algorithms.