ALBERT

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

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

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

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

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

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

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

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

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

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

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

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

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

Description: In an \(\epsilon \) -Nash equilibrium, a player can gain at most \(\epsilon \) by changing his behaviour. Recent work has addressed the question of how best to compute \(\epsilon \) -Nash equilibria, and for what values of \(\epsilon \) a polynomial-time algorithm exists. An \(\epsilon \) - well-supported Nash equilibrium ( \(\epsilon \) -WSNE) has the additional requirement that any strategy that is used with non-zero probability by a player must have payoff at most \(\epsilon \) less than a best response. A recent algorithm of Kontogiannis and Spirakis shows how to compute a 2/3-WSNE in polynomial time, for bimatrix games. Here we introduce a new technique that leads to an improvement to the worst-case approximation guarantee.

Description: We prove logarithmic upper bounds for the diameters of the random-surfer Webgraph model and the PageRank-based selection Webgraph model, confirming the small world phenomenon holds for them. In the special case when the generated graph is a tree, we provide close lower and upper bounds for the diameters of both models.

Description: Given two point sets S and T , in a many-to-many matching between S and T each point in S is assigned to one or more points in T and vice versa. A generalization of the many-to-many matching problem is the limited capacity many-to-many matching problem , where the number of points that can be matched to each point (the capacity of each point) is limited. In this paper, we provide an \(O\left( n^2\right) \) time algorithm for the one dimensional minimum-cost limited capacity many-to-many matching problem, where \(\left| S\right| +\left| T\right| =n\) . Our algorithm improves the best previous time complexity of \(O(kn^2)\) , that in which k is the largest capacity of the points in \(S \cup T\) . In this problem, both S and T lie on the real line and the cost of matching \(s \in S\) to \(t \in T\) is equal to the distance between s and t .

Description: In the Directed Feedback Arc (Vertex) Set problem, we are given a digraph D with vertex set V ( D ) and arcs set A ( D ) and a positive integer k , and the question is whether there is a subset X of arcs (vertices) of size at most k such that the digraph obtained after deleting X from D is an acyclic digraph. In this paper we study these two problems in the realm of parametrized and kernelization complexity. More precisely, for these problems we give polynomial time algorithms, known as kernelization algorithms, on several digraph classes that given an instance ( D ,  k ) of the problem returns an equivalent instance \((D',k')\) such that the size of \(D'\) and \(k'\) is at most \(k^{O(1)}\) . We extend previous results for Directed Feedback Arc (Vertex) Set on tournaments to much larger and well studied classes of digraphs. Specifically we obtain polynomial kernels for k -FVS on digraphs with bounded independence number, locally semicomplete digraphs and some totally \(\Phi \) -decomposable digraphs, including quasi-transitive digraphs. We also obtain polynomial kernels for k -FAS on some totally \(\Phi \) -decomposable digraphs, including quasi-transitive digraphs. Finally, we design a subexponential algorithm for k -FAS running in time \(2^{O(\sqrt{k} (\log k)^c)}n^d\) for constants c ,  d . on locally semicomplete digraphs.

Description: Braess’s paradox states that removing a part of a network may improve the players’ latency at equilibrium. In this work, we study the approximability of the best subnetwork problem for the class of random \({\mathcal {G}}_{n,p}\) instances proven prone to Braess’s paradox by Valiant and Roughgarden RSA ’10 (Random Struct Algorithms 37(4):495–515, 2010 ), Chung and Young WINE ’10 (LNCS 6484:194–208, 2010 ) and Chung et al. RSA ’12 (Random Struct Algorithms 41(4):451–468, 2012 ). Our main contribution is a polynomial-time approximation-preserving reduction of the best subnetwork problem for such instances to the corresponding problem in a simplified network where all neighbors of source s and destination t are directly connected by 0 latency edges. Building on this, we consider two cases, either when the total rate r is sufficiently low , or, when r is sufficiently high . In the first case of low \(r= O(n_{+})\) , here \(n_{+}\) is the maximum degree of \(\{s, t\}\) , we obtain an approximation scheme that for any constant \(\varepsilon 〉 0\) and with high probability, computes a subnetwork and an \(\varepsilon \) -Nash flow with maximum latency at most \((1+\varepsilon )L^*+ \varepsilon \) , where \(L^*\) is the equilibrium latency of the best subnetwork. Our approximation scheme runs in polynomial time if the random network has average degree \(O(\mathrm {poly}(\ln n))\) and the traffic rate is \(O(\mathrm {poly}(\ln \ln n))\) , and in quasipolynomial time for average degrees up to o ( n ) and traffic rates of \(O(\mathrm {poly}(\ln n))\) . Finally, in the second case of high \(r= {\varOmega }(n_{+})\) , we compute in strongly polynomial time a subnetwork and an \(\varepsilon \) -Nash flow with maximum latency at most \((1+2\varepsilon + o(1))L^*\) .

Description: A semi-matching in a bipartite graph \(G = (U, V, E)\) is a set of edges \(M \subseteq E\) such that each vertex in U is incident to exactly one edge in M , i.e., \(deg_M(u)=1\) for each \(u \in U\) . An optimal semi-matching is a semi-matching with the minimal value of the cost function \(\sum _{v \in V} \frac{deg_M(v) \cdot (deg_M(v)+1)}{2}\) . Exploiting the divide-and-conquer nature of the semi-matching problem, we reduce the problem to a simpler problem whose objective is to compute a maximum weak bounded-degree semi-matching. Using the reduction we derive three algorithms for the optimal semi-matching problem. The first one runs in time \(O(\sqrt{n} \cdot m \cdot \log {n})\) on a graph with n vertices and m edges. The second one is randomized and computes an optimal semi-matching with high probability in time \(O(n^{\omega } \cdot \log ^{1+o(1)} n)\) , where \(\omega \) is the exponent of the best known matrix multiplication algorithm. Since \(\omega 〈 2.38\) , this algorithm breaks through \(O(n^{2.5})\) barrier for dense graphs. In the case of planar graphs, the third one computes an optimal semi-matching in deterministic time \(O(n\cdot \log ^4{n})\) .

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: Online makespan minimization is a classical problem in which a sequence of jobs \(\sigma = J_1, \ldots , J_n\) has to be scheduled on m identical parallel machines so as to minimize the maximum completion time of any job. In this paper we investigate the problem with an essentially new model of resource augmentation. More specifically, an online algorithm is allowed to build several schedules in parallel while processing \(\sigma \) . At the end of the scheduling process the best schedule is selected. This model can be viewed as providing an online algorithm with extra space, which is invested to maintain multiple solutions. The setting is of particular interest in parallel processing environments where each processor can maintain a single or a small set of solutions. As a main result we develop a \((4/3+\varepsilon )\) -competitive algorithm, for any \(0〈\varepsilon \le 1\) , that uses a constant number of schedules. The constant is equal to \(1/\varepsilon ^{O(\log (1/\varepsilon ))}\) . We also give a \((1+\varepsilon )\) -competitive algorithm, for any \(0〈\varepsilon \le 1\) , that builds a polynomial number of \((m/\varepsilon )^{O(\log (1/\varepsilon ) / \varepsilon )}\) schedules. This value depends on m but is independent of the input \(\sigma \) . The performance guarantees are nearly best possible. We show that any algorithm that achieves a competitiveness smaller than 4 / 3 must construct \(\Omega (m)\) schedules. Our algorithms make use of novel guessing schemes that (1) predict the optimum makespan of a job sequence \(\sigma \) to within a factor of \(1+\varepsilon \) and (2) guess the job processing times and their frequencies in \(\sigma \) . In (2) we have to sparsify the universe of all guesses so as to reduce the number of schedules to a constant. We remark that the competitive ratios achieved using parallel schedules are considerably smaller than those in the standard problem without resource augmentation. Furthermore they are at least as good and in most cases better than the ratios obtained with other means of resource augmentation for makespan minimization.

Description: In the path minimum problem, we preprocess a tree on n weighted nodes, such that given an arbitrary path, the node with the smallest weight along this path can be located. We design novel succinct indices for this problem under the indexing model , for which weights of nodes are read-only and can be accessed with ranks of nodes in the preorder traversal sequence of the input tree. We present an index within O ( m ) bits of additional space that supports queries in \(O(\varvec{\alpha }(m, n))\) time and \(O(\varvec{\alpha }(m, n))\) accesses to the weights of nodes, for any integer \(m \ge n\) ; and an index within \(2n + o(n)\) bits of additional space that supports queries in \(O(\varvec{\alpha }(n))\) time and \(O(\varvec{\alpha }(n))\) accesses to the weights of nodes. Here \(\varvec{\alpha }(m, n)\) is the inverse-Ackermann function, and \(\varvec{\alpha }(n) = \varvec{\alpha }(n, n)\) . These indices give us the first succinct data structures for the path minimum problem. Following the same approach, we also develop succinct data structures for semigroup path sum queries, for which a query asks for the sum of weights along a given query path. One of our data structures requires \(n\lg \sigma + 2n + o(n\lg \sigma )\) bits of space and \(O(\varvec{\alpha }(n))\) query time, where \(\sigma \) is the size of the semigroup. In the path reporting problem, queries ask for the nodes along a query path whose weights are within a two-sided query range. Using the succinct indices for path minimum queries, we achieve three different time/space tradeoffs for path reporting by designing an O ( n )-word data structure with \(O(\lg ^\epsilon n + occ \cdot \lg ^\epsilon n)\) query time; an \(O(n\lg \lg n)\) -word data structure with \(O(\lg \lg n + occ \cdot \lg \lg n)\) query time; and an \(O(n \lg ^\epsilon n)\) -word data structure with \(O(\lg \lg n + occ)\) query time. Here occ is the number of nodes reported and \(\epsilon \) is an arbitrary constant between 0 and 1. These tradeoffs match the state of the art of two-dimensional orthogonal range reporting queries (Chan et al. 2011 ), which can be treated as a special case of path reporting queries. When the number of distinct weights is much smaller than n , we further improve both the query time and the space cost of these three results.

Description: In this paper we provide a systematic treatment of several shape parameters of (random) k -trees. Our research is motivated by many important algorithmic applications of k -trees in the context of tree-decomposition of a graph and graphs of bounded tree-width. On the other hand, k -trees are also a very interesting object from the combinatorial point of view. For both labeled and unlabeled k -trees, we prove that the number of leaves and more generally the number of nodes of given degree satisfy a central limit theorem with mean value and variance that are asymptotically linear in the size of the k -tree. In particular we solve the asymptotic counting problem for unlabeled k -trees. By applying a proper singularity analysis of generating functions we show that the numbers \(U_k(n)\) of unlabeled k -trees of size n are asymptotically given by \(U_k(n) \sim c_k n^{-5/2}\rho _{k}^{-n}\) , where \(c_k〉 0\) and \(\rho _{k}〉0\) denotes the radius of convergence of the generating function \(U(z)=\sum _{n\ge 0} U_k(n) z^n\) .

Description: This paper considers max-min fair rate allocation and routing in energy harvesting networks where fairness is required among both the nodes and the time slots . Unlike most previous work on fairness, we focus on multihop topologies and consider different routing methods . We assume a predictable energy profile and focus on the design of efficient and optimal algorithms that can serve as benchmarks for distributed and approximate algorithms. We first develop an algorithm that obtains a max-min fair rate assignment for any routing that is specified at the input. We then turn to the problem of determining a “good” routing. For time-invariable unsplittable routing , we develop an algorithm that finds routes that maximize the minimum rate assigned to any node in any slot. For fractional routing , we derive a combinatorial algorithm for the time-invariable case with constant rates. We show that the time-variable case is at least as hard as the 2-commodity feasible flow problem and design an FPTAS to combat the high running time. Finally, we show that finding an unsplittable routing or a routing tree that provides lexicographically maximum rate assignment (i.e., the best in the max-min fairness terms) is NP-hard, even for a time horizon of a single slot. Our analysis provides insights into the problem structure and can be applied to other related fairness problems.

Description: In this paper, we consider the problem (denoted as EMDRT) of minimizing the earth mover’s distance between two sets of weighted points A and B in \({\mathbb {R}}^{d}\) under rigid transformation. EMDRT is an important problem in both theory and applications and has received considerable attentions in recent years. Previous research on this problem has resulted in only constant factor approximations and it has been an open problem for a long time to achieve PTAS solution. In this paper, we present the first FPTAS algorithm for EMDRT. Our algorithm runs roughly in \(O((nm)^{d+2}(\log nm)^{2d})\) time (which is close to a lower bound on any PTAS for this problem), where n and m are the sizes of A and B , respectively. Our result is based on several new techniques, such as the Sequential Orthogonal Decomposition and Optimum Guided Base , and can be extended to several related problems, such as the problem of earth mover’s distance under similarity transformation and the alignment problem, to achieve FPTAS for each of them.

Description: We study in limit law the complexity of some anticipated rejection random sampling algorithms. We express this complexity in terms of a probabilistic process, the threshold sum process. We show that, under the right conditions, the complexity is linear and admits as a limit law a so-called Darling–Mandelbrot distribution, studied by Darling (Trans Am Math Soc 73:95–107, 1952 ) and Lew (Constr Approx 10(1):15–30, 1994 ). We also give an explicit form to the density of the Darling–Mandelbrot distribution and derive some of its analytic properties.

Description: A covering problem is an integer linear program of type \(\min \{c^Tx\mid Ax\ge D,\ 0\le x\le d,\ x \in \mathbb {Z}\}\) where \(A\in \mathbb {Z}^{m\times n}_+\) , \(D\in \mathbb {Z}_+^m\) , and \(c,d\in \mathbb {Z}_+^n\) . In this paper, we study covering problems with additional precedence constraints \(\{x_i\le x_j \ \forall j\preceq i \in \mathcal {P}\}\) , where \(\mathcal {P}=([n], \preceq )\) is some arbitrary, but fixed partial order on the items represented by the column-indices of A . Such precedence constrained covering problems ( PCCPs ) are of high theoretical and practical importance even in the special case of the precedence constrained knapsack problem , that is, where \(m=1\) and \(d\equiv 1\) . Our main result is a strongly-polynomial primal–dual approximation algorithm for PCCP with \(d\equiv 1\) . Our approach generalizes the well-known knapsack cover inequalities to obtain an IP formulation which renders any explicit precedence constraints redundant. The approximation ratio of this algorithm is upper bounded by the width of \(\mathcal {P}\) , that is, by the size of a maximum antichain in \(\mathcal {P}\) . Interestingly, this bound is independent of the number of constraints. We are not aware of any other results on approximation algorithms for PCCP on arbitrary posets \(\mathcal {P}\) . For the general case with \(d\not \equiv 1\) , we present pseudo-polynomial algorithms. Finally, we show that the problem does not admit a PTAS under standard complexity assumptions.

Description: Motivated by applications to word-of-mouth advertising, we consider a game-theoretic scenario in which competing advertisers want to target initial adopters in a social network. Each advertiser wishes to maximize the resulting cascade of influence, modeled by a general network diffusion process. However, competition between products may adversely impact the rate of adoption for any given firm. The resulting framework gives rise to complex preferences that depend on the specifics of the stochastic diffusion model and the network topology. We study this model from the perspective of a central mechanism, such as a social networking platform, that can optimize seed placement as a service for the advertisers. We ask: given the reported budgets of the competing firms, how should a mechanism choose seeds to maximize overall efficiency? Beyond the algorithmic problem, competition raises issues of strategic behaviour: rational agents should be incentivized to truthfully report their advertising budget. For a general class of influence spread models, we show that when there are two players, the social welfare can be \(\frac{e}{e-1}\) -approximated by a polynomial-time strategyproof mechanism. Our mechanism uses a dynamic programming procedure to randomize the order in which advertisers are allocated seeds according to a greedy method. For three or more players, we demonstrate that under an additional assumption (satisfied by many existing models of influence spread) there exists a simpler strategyproof \(\frac{e}{e-1}\) -approximation mechanism; notably, this natural greedy mechanism is not necessarily strategyproof when there are only two players.

Description: Analyzing the runtime of a Randomized Search Heuristic (RSH) by theoretical means often turns out to be rather tricky even for simple optimization problems. The main reason lies in the randomized nature of these algorithms. Both the optimization routines and the initialization of RSHs are typically based on random samples. It has often been observed, though, that the expected runtime of RSHs does not deviate much from the expected runtime when starting in an initial solution of average fitness. Having this information a priori could greatly simplify runtime analyses, as it reduces the necessity of analyzing the influence of the random initialization. Most runtime bounds in the literature, however, do not profit from this observation and are either too pessimistic or require a rather complex proof. In this work we show for the two search heuristics Randomized Local Search (RLS) and the (1+1) Evolutionary Algorithm on the two well-studied problems OneMax and LeadingOnes that their expected runtimes indeed deviate by at most a small additive constant from the expected runtime when started in a solution of average fitness. For RLS on OneMax , this additive discrepancy is \(-1/2 \pm o(1)\) , leading to the first runtime statement for this problem that is precise apart from additive o (1) terms: The expected number of iterations until an optimal search point is found, is \(n H_{n/2} - 1/2 \pm o(1)\) , where \(H_{n/2}\) denotes the ( n  / 2)th harmonic number when n is even, and \(H_{n/2}:= (H_{\lfloor n/2 \rfloor } + H_{\lceil n/2 \rceil })/2\) when n is odd. For this analysis and the one of the (1+1) EA optimizing OneMax we use a coupling technique, which we believe to be interesting also for the study of more complex optimization problems. For the analyses of the LeadingOnes test function, we show that one can express the discrepancy solely via the waiting times for leaving fitness level 0 and 1, which then easily yields the discrepancy, and in particular, without having to deal with so-called free-riders.

Description: The ( \(1+1\) ) EA is a simple evolutionary algorithm that is known to be efficient on linear functions and on some combinatorial optimization problems. In this paper, we rigorously study its behavior on three easy combinatorial problems: finding the 2-coloring of a class of bipartite graphs, solving a class of satisfiable 2-CNF formulas, and solving a class of satisfiable propositional Horn formulas. We prove that it is inefficient on all three problems in the sense that the number of iterations the algorithm needs to minimize the cost functions is superpolynomial with high probability. Our motivation is to better understand the influence of problem instance structure on the runtime character of a simple evolutionary algorithm. We are interested in what kind of structural features give rise to so-called metastable states at which, with probability \(1 - o(1)\) , the ( \(1+1\) ) EA becomes trapped and subsequently has difficulty leaving. Finally, we show how to modify the ( \(1+1\) ) EA slightly in order to obtain a polynomial-time performance guarantee on all three problems.

Description: Some recent results (Bauer et al. in Algorithms in bioinformatics, Springer, Berlin, pp 326–337, 2012 ; Cox et al. in Algorithms in bioinformatics, Springer, Berlin, pp. 214–224, 2012 ; Rosone and Sciortino in The nature of computation. Logic, algorithms, applications, Springer, Berlin, pp 353–364, 2013 ) have introduced external-memory algorithms to compute self-indexes of a set of strings, mainly via computing the Burrows–Wheeler transform of the input strings. The motivations for those results stem from Bioinformatics, where a large number of short strings (called reads) are routinely produced and analyzed. In that field, a fundamental problem is to assemble a genome from a large set of much shorter samples extracted from the unknown genome. The approaches that are currently used to tackle this problem are memory-intensive. This fact does not bode well with the ongoing increase in the availability of genomic data. A data structure that is used in genome assembly is the string graph, where vertices correspond to samples and arcs represent two overlapping samples. In this paper we address an open problem of Simpson and Durbin (Bioinformatics 26(12):i367–i373, 2010 ): to design an external-memory algorithm to compute the string graph.

Description: We characterize the best possible trade-off achievable when optimizing the construction of a decision tree with respect to both the worst and the expected cost. It is known that a decision tree achieving the minimum possible worst case cost can behave very poorly in expectation (even exponentially worse than the optimal), and the vice versa is also true. Led by applications where deciding which optimization criterion might not be easy, several authors recently have focussed on the bicriteria optimization of decision trees. Here we sharply define the limits of the best possible trade-offs between expected and worst case cost. More precisely, we show that for every \(\rho 〉0\) there is a decision tree D with worst testing cost at most \((1 + \rho )\textit{OPT}_W\) and expected testing cost at most \(\frac{1}{1 - e^{-\rho }} \textit{OPT}_E,\) where \(\textit{OPT}_W\) and \(\textit{OPT}_E\) denote the minimum worst testing cost and the minimum expected testing cost of a decision tree for the given instance. We also show that this is the best possible trade-off in the sense that there are infinitely many instances for which we cannot obtain a decision tree with both worst testing cost smaller than \((1 + \rho )\textit{OPT}_W\) and expected testing cost smaller than \(\frac{1}{1 - e^{-\rho }} \textit{OPT}_E\) .

Description: A prominent tool in many problems involving metric spaces is a notion of randomized low-diameter decomposition. Loosely speaking, \(\beta \) -decomposition refers to a probability distribution over partitions of the metric into sets of low diameter, such that nearby points (parameterized by \(\beta 〉0\) ) are likely to be “clustered” together. Applying this notion to the shortest-path metric in edge-weighted graphs, it is known that n -vertex graphs admit an \(O(\ln n)\) -padded decomposition (Bartal, 37th annual symposium on foundations of computer science. IEEE, pp 184–193, 1996 ), and that excluded-minor graphs admit O (1)-padded decomposition (Klein et al., 25th annual ACM symposium on theory of computing, pp 682–690, 1993 ; Fakcharoenphol and Talwar, J Comput Syst Sci 69(3), 485–497, 2004 ; Abraham et al., Proceedings of the 46th annual ACM symposium on theory of computing. STOC ’14, pp 79–88. ACM, New York, NY, USA, 2014 ). We design decompositions to the family of p -path-separable graphs, which was defined by Abraham and Gavoille (Proceedings of the twenty-fifth annual acm symposium on principles of distributed computing, PODC ’06, pp 188–197, 2006 ) and refers to graphs that admit vertex-separators consisting of at most p shortest paths in the graph. Our main result is that every p -path-separable n -vertex graph admits an \(O(\ln (p \ln n))\) -decomposition, which refines the \(O(\ln n)\) bound for general graphs, and provides new bounds for families like bounded-treewidth graphs. Technically, our clustering process differs from previous ones by working in (the shortest-path metric of) carefully chosen subgraphs.

Description: Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrences of new mutations is much longer than the time it takes for a mutated genotype to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a stochastic process evolving one genotype by means of mutation and selection between the resident and the mutated genotype. The probability of accepting the mutated genotype then depends on the change in fitness. We study this process, SSWM, from an algorithmic perspective, quantifying its expected optimisation time for various parameters and investigating differences to a similar evolutionary algorithm, the well-known (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.

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: The order- \(k\) Voronoi diagram of line segments has properties surprisingly different from its counterpart for points. For example, a single order- \(k\) Voronoi region may consist of \(\varOmega (n)\) disjoint faces. In this paper, we analyze the structural properties of this diagram and show that its combinatorial complexity is \(O(k(n-k))\) , for \(n\) non-crossing line segments, despite the presence of disconnected regions. The same bound holds for \(n\) intersecting line segments, for \(k\ge n/2\) . We also consider the order- \(k\) Voronoi diagram of line segments that form a planar straight-line graph, and augment the definition of an order- \(k\) diagram to cover sites that are not disjoint. On the algorithmic side, we extend the iterative approach to construct this diagram, handling complications caused by the presence of disconnected regions. All bounds are valid in the general \(L_p\) metric, \(1\le p\le \infty \) . For non-crossing segments in the \(L_\infty \) and \(L_1\) metrics, we show a tighter \(O((n-k)^2)\) bound for \(k〉n/2\) .

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 give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to the ℓ p norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p =1, p even, and p =∞. For p even, we reduce the problem to standard convolution, while for p =∞ and p =1, we reduce the problem to (min,+) convolution and $(\operatorname {median},+)$ convolution. Then we solve the latter two convolution problems in subquadratic time, which are interesting results in their own right. These results shed some light on the classic sorting X + Y problem, because the convolutions can be viewed as computing order statistics on the antidiagonals of the X + Y matrix. All of our algorithms run in o ( n 2 ) time, whereas the obvious algorithms for these problems run in Θ ( n 2 ) time.

Description: This paper gives a precise mathematical analysis of the behaviour of “hiring above the median” strategies for a problem in the context of “on-line selection under uncertainty” that is known (at least in computer science related literature) as the “hiring problem”. Here a sequence of candidates is interviewed sequentially and based on the “score” of the current candidate an immediate decision whether to hire him or not has to be made. For “hiring above the median” selection rules, a new candidate will be hired if he has a score better than the median score of the already recruited candidates. Under the natural probabilistic model assuming that the ranks of the first n candidates are forming a random permutation, we show exact and asymptotic results for various quantities of interest to describe the dynamics of the hiring process and the quality of the hired staff. In particular we can characterize the limiting distribution of the number of hired candidates of a sequence of n candidates, which reveals the somewhat surprising effect, that slight changes in the selection rule, i.e., assuming the “lower” or the “upper” median as the threshold, have a strong influence on the asymptotic behaviour. Thus we could extend considerably previous analyses (Krieger et al., Ann. Appl. Probab., 17:360–385, 2007 ; Broder et al., Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1184–1193, ACM/SIAM, New York/Philadelphia, 2008 and Archibald and Martinez, Proceedings of the 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), Discrete Mathematics and Theoretical Computer Science, pp. 63–76, 2009 ) of such selection rules. Furthermore, we discuss connections between the hiring process and the Chinese restaurant process introduced by Pitman (Combinatorial Stochastic Processes, Springer, Berlin, 2006 ).

Description: Given an undirected graph G =( V , E ) with positive edge lengths and two vertices s and t , the next-to-shortest path problem is to find an st -path which length is minimum amongst all st -paths strictly longer than the shortest path length. In this paper we show that the problem can be solved in linear time if the distances from s and t to all other vertices are given. Particularly our new algorithm runs in O (| V |log| V |+| E |) time for general graphs, which improves the previous result of O (| V | 2 ) time and takes only linear time for unweighted graphs, planar graphs, and graphs with positive integer edge lengths.

Description: We present an efficient data structure for finding the longest prefix of a query string q in a dynamic database of strings. When the database strings are prefixes of IP-addresses then this is the IP-lookup problem. Our data structure is I/O efficient. It supports a query with a string q using $O(\log_{B}(n)+\frac{|q|}{B})$ I/O operations, where B is the size of a disk block. It also supports an insertion and a deletion of a string q with the same number of I/Os. The data structure requires O ( n / B ) blocks, and the running time for each operation is O ( B log B ( n )+| q |).

Description: Given an undirected and edge-weighted graph G together with a set of ordered vertex-pairs, called st -pairs, we consider two problems of finding an orientation of all edges in G : min-sum orientation is to minimize the sum of the shortest directed distances between all st -pairs; and min-max orientation is to minimize the maximum shortest directed distance among all st -pairs. Note that these shortest directed paths for st -pairs are not necessarily edge-disjoint. In this paper, we first show that both problems are strongly NP-hard for planar graphs even if all edge-weights are identical, and that both problems can be solved in polynomial time for cycles. We then consider the problems restricted to cacti, which form a graph class that contains trees and cycles but is a subclass of planar graphs. Then, min-sum orientation is solvable in polynomial time, whereas min-max orientation remains NP-hard even for two st -pairs. However, based on LP-relaxation, we present a polynomial-time 2-approximation algorithm for min-max orientation . Finally, we give a fully polynomial-time approximation scheme (FPTAS) for min-max orientation on cacti if the number of st -pairs is a fixed constant.

Description: Online clustering problems are problems where the classification of points into sets (called clusters) is performed in an online fashion. Points arrive at arbitrary locations, one by one, to be assigned to clusters at the time of arrival. A point can be either assigned to an existing cluster or a new cluster can be opened for it. Here, we study a one-dimensional variant on a line. Each cluster is a closed interval, and there is no restriction on the length of a cluster. The cost of a cluster is the sum of a fixed set-up cost and its diameter (or length). The goal is to minimize the sum of costs of the clusters used by the algorithm. We study several variants, each having the two essential properties that a point which has been assigned to a given cluster must remain assigned to that cluster and no pair of clusters can be merged. In the strict variant, the diameter and the exact location of the cluster must be fixed when it is initialized. In the flexible variant, the algorithm can shift the cluster or expand it, as long as it contains all points assigned to it. In an intermediate model, the diameter is fixed in advance but the exact location can be modified. Here we give tight bounds on the competitive ratio of any online algorithm in each of these variants. In addition, for each model we also consider the semi-online case where points are presented ordered by their location.

Description: We study two-stage robust variants of combinatorial optimization problems on undirected graphs, like Steiner tree, Steiner forest, and uncapacitated facility location. Robust optimization problems, previously studied by Dhamdhere et al. (Proc. of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pp. 367–378, 2005 ), Golovin et al. (Proc. of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2006 ), and Feige et al. (Proc. of the 12th International Integer Programming and Combinatorial Optimization Conference, pp. 439–453, 2007 ), are two-stage planning problems in which the requirements are revealed after some decisions are taken in Stage 1. One has to then complete the solution, at a higher cost, to meet the given requirements. In the robust k -Steiner tree problem, for example, one buys some edges in Stage 1. Then k terminals are revealed in Stage 2 and one has to buy more edges, at a higher cost, to complete the Stage 1 solution to build a Steiner tree on these terminals. The objective is to minimize the total cost under the worst-case scenario. In this paper, we focus on the case of exponentially many scenarios given implicitly. A scenario consists of any subset of k terminals (for k -Steiner tree), or any subset of k terminal-pairs (for k -Steiner forest), or any subset of k clients (for facility location). Feige et al. (Proc. of the 12th International Integer Programming and Combinatorial Optimization Conference, pp. 439–453, 2007 ) give an LP-based general framework for approximation algorithms for a class of two stage robust problems. Their framework cannot be used for network design problems like k -Steiner tree (see later elaboration). Their framework can be used for the robust facility location problem, but gives only a logarithmic approximation. We present the first constant-factor approximation algorithms for the robust k -Steiner tree (with exponential number of scenarios) and robust uncapacitated facility location problems. Our algorithms are combinatorial and are based on guessing the optimum cost and clustering to aggregate nearby vertices. For the robust k -Steiner forest problem on trees and with uniform multiplicative increase factor for Stage 2 (also known as inflation), we present a constant approximation. We show APX-hardness of the robust min-cut problem (even with singleton-set scenarios), resolving an open question of (Dhamdhere et al. in Proc. of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pp. 367–378, 2005 ) and (Golovin et al. in Proc. of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2006 ).

Description: We investigate a special case of the Induced Subgraph Isomorphism problem, where both input graphs are interval graphs. We show the NP-hardness of this problem, and we prove fixed-parameter tractability of the problem with non-standard parameterization, where the parameter is the difference | V ( G )|−| V ( H )|, with G and H being the larger and the smaller input graph, respectively. Intuitively, we can interpret this problem as “cleaning” the graph G , regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We also prove W[1]-hardness for the standard parameterization where the parameter is | V ( H )|.

Description: A recent trend in stringology explores the possibility of utilizing text compression to speed up similarity computation between strings. In this line of investigation, run-length encoding is one of the earliest studied compression schemes. Despite its simple coding nature, the only positive result before this work is the computation of the in-del distance (dual of longest common subsequence), which requires O ( mn log mn ) time, where  m and  n denote the number of runs of the input strings. The worst-case time complexity of computing the edit distance between two run-length encoded strings still depends on the uncompressed string lengths. In this paper, we break the foundational gap by providing its first “fully compressed” algorithm whose running time depends solely on the compressed string lengths. Specifically, given two strings, compressed into m and n runs, m ≤ n , we present an O ( mn 2 )-time algorithm for computing the edit distance of the strings. Our approach also yields the first fully compressed solution to approximate matching of a pattern of m runs in a text of n runs in O ( mn 2 ) time.

Description: Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such annotation models by considering a number of graph streaming problems. Without annotations, streaming algorithms for graph problems generally require significant memory; we show that for many standard problems, including all graph problems that can be expressed with totally unimodular integer programming formulations, only constant space (measured in words) is needed for single-pass algorithms given linear-sized annotations. We also obtain protocols achieving essentially optimal tradeoffs between annotation length and memory usage for several important problems, including integer matrix-vector multiplication, as well as shortest s - t path in small-diameter graphs. We also obtain non-trivial tradeoffs for minimum weight bipartite perfect matching and shortest s - t path in general graphs.

Description: The edit distance problem is a classical fundamental problem in computer science in general, and in combinatorial pattern matching in particular. The standard dynamic programming solution for this problem computes the edit-distance between a pair of strings of total length O ( N ) in O ( N 2 ) time. To this date, this quadratic upper-bound has never been substantially improved for general strings. However, there are known techniques for breaking this bound in case the strings are known to compress well under a particular compression scheme. The basic idea is to first compress the strings, and then to compute the edit distance between the compressed strings. As it turns out, practically all known o ( N 2 ) edit-distance algorithms work, in some sense, under the same paradigm described above. It is therefore natural to ask whether there is a single edit-distance algorithm that works for strings which are compressed under any compression scheme. A rephrasing of this question is to ask whether a single algorithm can exploit the compressibility properties of strings under any compression method, even if each string is compressed using a different compression. In this paper we set out to answer this question by using straight line programs . These provide a generic platform for representing many popular compression schemes including the LZ-family, Run-Length Encoding, Byte-Pair Encoding, and dictionary methods. For two strings of total length N having straight-line program representations of total size n , we present an algorithm running in O ( nN lg( N / n )) time for computing the edit-distance of these two strings under any rational scoring function, and an O ( n 2/3 N 4/3 ) time algorithm for arbitrary scoring functions. Our new result, while providing a speed up for compressible strings, does not surpass the quadratic time bound even in the worst case scenario.

Description: A set S ⊆ V is a power dominating set (PDS) of a graph G =( V , E ) if every vertex and every edge in G can be observed based on the observation rules of power system monitoring. The power domination problem involves minimizing the cardinality of a PDS of a graph. We consider this combinatorial optimization problem and present a linear time algorithm for finding the minimum PDS of an interval graph if the interval ordering of the graph is provided. In addition, we show that the algorithm, which runs in Θ( n log n ) time, where n is the number of intervals, is asymptotically optimal if the interval ordering is not given. We also show that the results hold for the class of circular-arc graphs.

Description: We present an O ( n 2 log n )-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O ( rn 2 log n ) time if the difference between the maximum degree and the minimum degree is less than r . This running time is faster than applying the fastest known general matching algorithm that runs in $O(\sqrt{n}m)$ -time for graphs with m edges, whenever m = ω ( rn 1.5 log n ).

Description: This paper describes a simple greedy Δ -approximation algorithm for any covering problem whose objective function is submodular and non-decreasing, and whose feasible region can be expressed as the intersection of arbitrary (closed upwards) covering constraints, each of which constrains at most Δ variables of the problem. (A simple example is Vertex Cover , with Δ =2.) The algorithm generalizes previous approximation algorithms for fundamental covering problems and online paging and caching problems.

Description: The standard Tile Assembly Model (TAM) of Winfree (Algorithmic self-assembly of DNA, Ph.D. thesis, 1998 ) is a mathematical theory of crystal aggregations via monomer additions with applications to the emerging science of DNA self-assembly. Self-assembly under the rules of this model is programmable and can perform Turing universal computation. Many variations of this model have been proposed and the canonical problem of assembling squares has been studied extensively. We consider the problem of building approximate squares in TAM. Given any $\varepsilon \in (0,\frac{1}{4}]$ we show how to construct squares whose sides are within (1± ε ) N of any given positive integer N using $O( \frac{\log \frac{1}{\varepsilon}}{\log \log\frac{1}{\varepsilon}} + \frac{\log \log \varepsilon N}{\log \log \log \varepsilon N} )$ tile types. We prove a matching lower bound by showing that $\varOmega( \frac{\log \frac{1}{\varepsilon}}{\log \log\frac{1}{\varepsilon}} + \frac{\log \log \varepsilon N}{\log \log \log \varepsilon N} )$ tile types are necessary almost always to build squares of required approximate dimensions. In comparison, the optimal construction for a square of side exactly N in TAM uses $O(\frac{\log N}{\log \log N})$ tile types. The question of constructing approximate squares has been recently studied in a modified tile assembly model involving concentration programming. All our results are trivially translated into the concentration programming model by assuming arbitrary (non-zero) concentrations for our tile types. Indeed, the non-zero concentrations could be chosen by an adversary and our results would still hold. Our construction can get highly accurate squares using very few tile types and are feasible starting from values of N that are orders of magnitude smaller than the best comparable constructions previously suggested. At an accuracy of ε =0.01, the number of tile types used to achieve a square of size 10 7 is just 58 and our constructions are proven to work for all N ≥13130. If the concentrations of the tile types are carefully chosen, we prove that our construction assembles an L × L square in optimal assembly time O ( L ) where (1− ε ) N ≤ L ≤(1+ ε ) N .

Description: Let G =( V , E ) be an undirected unweighted graph. A path between any two vertices u , v ∈ V is said to be t -approximate shortest path if its length is at most t times the length of the shortest path between u and v . We address the problem of building a compact data structure which can efficiently answer the following query for any u , v , x ∈ V and t 〉1: Report t-approximate shortest path between u and v when vertex x fails . We present data structures for the single source as well as all-pairs versions of this problem. The query time guaranteed by our data structures is optimal up to a constant factor. Moreover, the size of each of them nearly matches the size of the corresponding data structure with no failures.

Description: We study the problem of dynamically updating all-pairs shortest paths in a distributed network while edge update operations occur to the network. We consider the practical case of a dynamic network in which an edge update can occur while one or more other edge updates are under processing. A node of the network might be affected by a subset of these changes, thus being involved in the concurrent executions related to such changes. In this paper, we provide a new algorithm for this problem, and experimentally compare its performance with respect to those of the most popular solutions in the literature: the classical distributed Bellman-Ford method, which is still used in real network and implemented in the RIP protocol, and DUAL, the Diffuse Update ALgorithm, which is part of CISCO’s widely used EIGRP protocol. As input to the algorithms, we used both real-world and artificial instances of the problem. The experiments performed show that the space occupancy per node required by the new algorithm is smaller than that required by both Bellman-Ford and DUAL. In terms of messages, the new algorithm outperforms both Bellman-Ford and DUAL on the real-world topologies, while on artificial instances, the new algorithm sends a number of messages that is more than that of DUAL and much smaller than that of Bellman-Ford.

Description: Algorithms are given for determining weighted isotonic regressions satisfying order constraints specified via a directed acyclic graph (DAG). For the L 1 metric a partitioning approach is used which exploits the fact that L 1 regression values can always be chosen to be data values. Extending this approach, algorithms for binary-valued L 1 isotonic regression are used to find L p isotonic regressions for 1〈 p 〈∞. Algorithms are given for trees, 2-dimensional and multidimensional orderings, and arbitrary DAGs. Algorithms are also given for L p isotonic regression with constrained data and weight values, L 1 regression with unweighted data, and L 1 regression for DAGs where there are multiple data values at the vertices.

Description: In this paper, we consider the problem of generating all maximal cliques in a sparse graph in polynomial delay. Given a graph G =( V , E ) with n vertices and m edges, the latest and fastest polynomial delay algorithm for sparse graphs enumerates all maximal cliques in O ( Δ 4 ) time delay, where Δ is the maximum degree of vertices. However, it requires an O ( n ⋅ m ) preprocessing time. We improve it in two aspects. First, our algorithm does not need preprocessing. Therefore, our algorithm is a truly polynomial delay algorithm. Second, our algorithm enumerates all maximal cliques in O ( Δ ⋅ H 3 ) time delay, where H is the so called H-value of a graph or equivalently it is the smallest integer satisfying |{ v ∈ V ∣ δ ( v )≥ H }|≤ H given δ ( v ) as the degree of a vertex. In real-world network data, H usually is a small value and much smaller than Δ .