ACM DL

ACM Transactions on

Algorithms (TALG)

Menu
Latest Articles

Online Submodular Maximization with Preemption

Submodular function maximization has been studied extensively in recent years under various constraints and models. The problem plays a major role in various disciplines. We study a natural online variant of this problem in which elements arrive one by one and the algorithm has to maintain a solution obeying certain constraints at all times. Upon... (more)

Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times

We consider two related scheduling problems: single resource-constrained scheduling on identical parallel machines and a generalization with... (more)

Sparse Approximation via Generating Point Sets

For a set P of n points in the unit ball b⊆ Rd, consider the problem of finding a small subset T⊆ P such that its convex-hull ϵ-approximates the convex-hull of the original set. Specifically, the Hausdorff distance between the convex hull of T and the convex hull of P should be at most ϵ. We present an efficient algorithm to... (more)

Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs

Recently, hardness results for problems in P were achieved using reasonable complexity-theoretic assumptions such as the Strong Exponential Time... (more)

Locating Errors in Faulty Formulas

Given a drawing of a read-once formula (called the blueprint), and a blackbox implementation with the same topology as the blueprint that purports to compute the formula, can we tell if it does? Under a fault model, where the only faults in the implementation are gates that complement their outputs, we show that there is an efficient algorithm that... (more)

Bloom Filters in Adversarial Environments

Many efficient data structures use randomness, allowing them to improve upon deterministic ones. Usually, their efficiency and correctness are analyzed using probabilistic tools under the assumption that the inputs and queries are independent of the internal randomness of the data structure. In this work, we consider data structures in a more... (more)

A Lottery Model for Center-Type Problems With Outliers

In this article, we give tight approximation algorithms for the k-center and matroid center problems with outliers. Unfairness arises naturally in... (more)

Ascending-Price Algorithms for Unknown Markets

We design a simple ascending-price algorithm to compute a (1 + ϵ)-approximate equilibrium in Arrow-Debreu markets with weak gross substitute property. It applies to an unknown market setting without exact knowledge about the number of agents, their individual utilities, and endowments. Instead, our algorithm only uses price queries to a... (more)

Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals

We introduce a weighted version of the ranking algorithm by Karp et al. (STOC 1990), and we prove a competitive ratio of 0.6534 for the vertex-weighted online bipartite matching problem when online vertices arrive in random order. Our result shows that random arrivals help beating the 1-1/e barrier even in the vertex-weighted case. We build... (more)

Distributed Dominating Set Approximations beyond Planar Graphs

The Minimum Dominating Set (MDS) problem is a fundamental and challenging problem in distributed computing. While it is well known that minimum... (more)

Faster Pseudopolynomial Time Algorithms for Subset Sum

Given a (multi) set S of n positive integers and a target integer u, the subset sum problem is to decide if there is a subset of S that sums up to u.... (more)

Generalized Center Problems with Outliers

We study the ℱ-center problem with outliers: Given a metric space (X,d), a general down-closed family ℱ of subsets of X, and a parameter m, we need to locate a subset S ∈ ℱ of centers such that the maximum distance among the closest m points in X to S is minimized. Our main result is a dichotomy theorem. Colloquially,... (more)

NEWS

About TALG

The ACM Transactions on Algorithms (TALG) publishes original research of the highest quality dealing with algorithms that are inherently discrete and finite, and having mathematical content in a natural way, either in the objective or in the analysis.

read more
A 4/3 Approximation for the Minimum 2-Edge Connected Subgraph Problem

We present a factor 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based on a simple graph decomposition followed by comparing with the smallest 2-edge cover.

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

We consider integer programming problems in standard form $\max \{c^Tx : Ax = b, \, xe0, \, x  $^n\}$ where $A  $^{m ×n}$, $b  $^m$ and $c  $^n$. We show that such an integer program can be solved in time $(m Å ”)^{O(m)} Å \|b\|_^2$, where $”$ is an upper bound on each absolute value of an entry in $A$. This improves upon the longstanding best bound of Papadimitriou (1981) of $(mŔ)^{O(m^2)}$, where in addition, the absolute values of the entries of $b$ also need to be bounded by $”$. % and addresses an open problem raised by Fomin. Our result relies on a lemma of Steinitz that states that a set of vectors in $^m$ that is contained in the unit ball of a norm and that sum up to zero can be ordered such that all partial sums are of norm bounded by $m$. We also use the Steinitz lemma to show that the $\ell_1$-distance of an optimal integer and fractional solution, %of the integer %program, also under the presence of upper bounds on the variables, is bounded by $m Å (2\,mŔ+1)^m$. Here $”$ is again an upper bound on the absolute values of the entries of $A$. The novel strength of our bound is that it is independent of $n$. We provide evidence for the significance of our bound by applying it to general knapsack problems where we obtain structural and algorithmic results that improve upon the recent literature.

Faster approximation schemes for the two-dimensional knapsack problem

For geometric optimization problems we often understand the computational complexity on a rough scale, but not very well on a finer scale. One such example is the two-dimensional knapsack problem for squares. There is a polynomial time (1+epsilon)-approximation algorithm for it (i.e., a PTAS) but the running time of this algorithm is triple exponential in 1/epsilon, i.e., Omega(n^{2^{2^{1/epsilon}}}). A double or triple exponential dependence on 1/epsilon is inherent in how this and various other algorithms for other geometric problems work. In this paper, we present an EPTAS for knapsack for squares, i.e., a (1+epsilon)-approximation algorithm with a running time of O_{epsilon}(1)*n^{O(1)}. In particular, the exponent of n in the running time does not depend on epsilon at all! Since there can be no FPTAS for the problem (unless P=NP) this is the best kind of approximation scheme we can hope for. To achieve this improvement, we introduce two new key ideas: We present a fast method to guess the Omega(2^{2^{1/epsilon}}) relatively large squares of a suitable near-optimal packing instead of using brute-force enumeration. Secondly, we introduce an indirect guessing framework to define sizes of cells for the remaining squares. In the previous PTAS each of these steps needs a running time of Omega(n^{2^{2^{1/epsilon}}}) and we improve both to O_{epsilon}(1)*n^{O(1)}. We complete our result by giving an algorithm for two-dimensional knapsack for rectangles under (1+epsilon)-resource augmentation. We improve the previous double-exponential PTAS to an EPTAS and compute even a solution with optimal weight, while the previous PTAS computes only an approximation.

Exponential Separations in the Energy Complexity of Leader Election

Energy is often the most constrained resource for battery-powered wireless devices and the lion's share of energy is often spent on transceiver usage (sending/receiving packets), not on computation. In this paper we study the energy complexity of LeaderElection and ApproximateCounting in several models of wireless radio networks. It turns out that energy complexity is very sensitive to whether the devices can generate random bits and their ability to detect collisions. We consider four collision-detection models: Strong-CD (in which transmitters and listeners detect collisions), Sender-CD and Receiver-CD (in which only transmitters or only listeners detect collisions), and No-CD (in which no one detects collisions.) The take-away message of our results is quite surprising. For randomized LeaderElection algorithms, there is an exponential gap between the energy complexity of Sender-CD and Receiver-CD, and for deterministic LeaderElection algorithms there is another exponential gap, but in the reverse direction. In particular, the randomized energy complexity of LeaderElection is $\Theta(\log^* n)$ in Sender-CD but $\Theta(\log(\log^* n))$ in Receiver-CD, where $n$ is the (unknown) number of devices. Its deterministic complexity is $\Theta(\log N)$ in Receiver-CD but $\Theta(\log\log N)$ in Sender-CD, where $N$ is the (known) size of the devices' ID space. There is a tradeoff between time and energy. We give a new upper bound on the time-energy tradeoff curve for randomized LeaderElection and ApproximateCounting. A critical component of this algorithm is a new deterministic LeaderElection algorithm for dense instances, when $n=\Theta(N)$, with inverse-Ackermann-type ($O(\alpha(N))$) energy complexity.

Scheduling When You Don't Know the Number of Machines

Often in a scheduling problem, there is uncertainty about the jobs to be processed. The issue of uncertainty regarding the machines has been much less studied. In this paper, we study a scheduling environment in which jobs first need to be grouped into some sets before the number of machines is known, and then the sets need to be scheduled on machines without being separated. In order to evaluate algorithms in such an environment, we introduce the idea of an ±-robust algorithm, one which is guaranteed to return a schedule on any number m of machines that is within an ± factor of the optimal schedule on m machine, where the optimum is not subject to the restriction that the sets cannot be separated. Under such environment, we give a 5/3-robust algorithm for scheduling on parallel machines to minimize makespan, and show a lower bound 4/3. For the special case when the jobs are infinitesimal, we give a 1.233-robust algorithm with an asymptotic lower bound of 1.207. We also study a case of fair allocation, where the objective is to minimize the difference between the maximum and minimum machine load.

Dynamic Beats Fixed: On Phase-based Algorithms for File Migration

We construct a deterministic 4-competitive algorithm for the online file migration problem, beating the currently best 20-year-old, 4.086-competitive MTLM algorithm by Bartal et al. (SODA 1997). Like MTLM, our algorithm also operates in phases, but it adapts their lengths dynamically depending on the geometry of requests seen so far. The improvement was obtained by carefully analyzing a linear model (factor-revealing LP) of a single phase of the algorithm. We also show that if an online algorithm operates in phases of fixed length and the adversary is able to modify the graph between phases, then the competitive ratio is at least 4.086.

Tight Analysis of Parallel Randomized Greedy MIS

We provide a tight analysis which settles the round complexity of the well-studied \emph{parallel randomized greedy MIS} algorithm, thus answering the main open question of Blelloch, Fineman, and Shun [SPAA'12]. The parallel/distributed randomized greedy Maximal Independent Set (MIS) algorithm works as follows. An order of the vertices is chosen uniformly at random. Then, in each round, all vertices that appear before their neighbors in the order are added to the independent set and removed from the graph along with their neighbors. The main question of interest is the number of rounds it takes until the graph is empty. This algorithm has been studied since 1987, initiated by Coppersmith, Raghavan, and Tompa [FOCS'87], and the previously best known bounds were $O(\log n)$ rounds in expectation for Erd\H{o}s-R\'{e}nyi random graphs by Calkin and Frieze [Random Struc. \& Alg. '90] and $O(\log^2 n)$ rounds with high probability for general graphs by Blelloch, Fineman, and Shun [SPAA'12]. We prove a high probability upper bound of $O(\log n)$ on the round complexity of this algorithm in general graphs, and that this bound is tight. This also shows that parallel randomized greedy MIS is as fast as the celebrated algorithm of Luby [STOC'85, JALG'86].

Heavy Hitters and the Structure of Local Privacy

We present a new locally differentially private algorithm for the heavy hitters problem which achieves optimal worst-case error as a function of all standardly considered parameters. Prior work obtained error rates which depend optimally on the number of users, the size of the domain, and the privacy parameter, but depend sub-optimally on the failure probability. We strengthen existing lower bounds on the error to incorporate the failure probability, and show that our new upper bound is tight with respect to this parameter as well. Our lower bound is based on a new understanding of the structure of locally private protocols. We further develop these ideas to obtain the following general results beyond heavy hitters. 1. Advanced Grouposition: In the local model, group privacy for k users degrades proportionally to root k, instead of linearly in k as in the central model. Stronger group privacy yields improved max-information guarantees, as well as stronger lower bounds (via "packing arguments"), over the central model. 2. Building on a transformation of Bassily and Smith (STOC 2015), we give a generic transformation from any non-interactive approximate-private local protocol into a pure-private local protocol. Again in contrast with the central model, this shows that we cannot obtain more accurate algorithms by moving from pure to approximate local privacy.

Faster Carry Bit Computation for Adder Circuits with Prescribed Arrival Times

We consider the fundamental problem of constructing fast circuits for the carry bit computation in binary addition. Up to a small additive constant, the carry bit computation reduces to computing an And-Or path, i.e., a formula of type t0 ? (t1 ? (t2 ? ( ... tm-1) ... ) or t0 ? (t1 ? (t2 ? ( ... tm-1) ... ). We present an algorithm that computes the fastest known Boolean circuit for an And-Or path with given arrival times a(t0), ..., a(tm-1) for the input signals. Our objective function is delay, a natural generalization of depth with respect to arrival times. The maximum delay of the circuit we compute is log2 W + log2 log2 m + log2 log2 log2 m + 4.3, where W := ?i = 0m-1 2a(ti). Note that ?log2 W? is a lower bound on the delay of any circuit depending on inputs t0, ..., tm-1 with prescribed arrival times. Our method yields the fastest circuits for And-Or paths, carry bit computation and adders in terms of delay known so far.

Improving TSP tours using dynamic programming over tree decompositions

Given a traveling salesman problem (TSP) tour $H$ in graph $G$ a $k$-move is an operation which removes $k$ edges from $H$, and adds $k$ edges of $G$ so that a new tour $H'$ is formed. The popular $k$-OPT heuristic for TSP finds a local optimum by starting from an arbitrary tour $H$ and then improving it by a sequence of $k$-moves. Until 2016, the only known algorithm to find an improving $k$-move for a given tour was the naive solution in time $O(n^k)$. At ICALP'16 de~Berg, Buchin, Jansen and Woeginger showed an $O(n^{\floor{2/3k}+1})$-time algorithm. We show an algorithm which runs in $O(n^{(1/4+\epsilon_k)k})$ time, where $\lim_{k\rightarrow\infty} \epsilon_k = 0$. It improves over the state of the art for every $k\ge 5$. For the most practically relevant case $k=5$ we provide a slightly refined algorithm running in $O(n^{3.4})$ time. We also show that for the $k=4$ case, improving over the $O(n^3)$-time algorithm of de~Berg et al. would be a major breakthrough: an $O(n^{3-\epsilon})$-time algorithm for any $\epsilon>0$ would imply an $O(n^{3-\delta})$-time algorithm for the \probAPSP problem, for some $\delta>0$.

Recognizing Weak Embeddings of Graphs

We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An \textbf{embedding} $\varphi:G\rightarrow M$ of a graph $G$ into a 2-manifold $M$ maps the vertices in $V(G)$ to distinct points and the edges in $E(G)$ to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to the same point or overlapping arcs, due to data compression or low resolution. This raises the computational problem of deciding whether a given map $\varphi:G\rightarrow M$ comes from an embedding. A map $\varphi:G\rightarrow M$ is a \textbf{weak embedding} if it can be perturbed into an embedding $\psi_\eps:G\rightarrow M$ with $\|\varphi-\psi_\eps\|<\eps$ for every $\eps>0$. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kyn\v{c}l~\cite{FK18_ht}, which reduces to solving a system of linear equations over $\mathbb{Z}_2$. It runs in $O(n^{2\omega})\leq O(n^{4.75})$ time, where $\omega\in [2,2.373)$ is the matrix multiplication exponent and $n$ is the number of vertices and edges of $G$. We improve the running time to $O(n\log n)$. Our algorithm is also conceptually simpler than~\cite{FK18_ht}: We perform a sequence of \emph{local operations} that gradually ``untangles'' the image $\varphi(G)$ into an embedding $\psi(G)$, or reports that $\varphi$ is not a weak embedding. It generalizes a recent technique developed for the case that $G$ is a cycle and the embedding is a simple polygon~\cite{AAET17}, and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.

An optimal O(nm) algorithm enumerating all walks common to all closed edge-covering walks of a graph

In this paper we consider the following problem. Given a directed graph G, output all walks of G that are sub-walks of all closed edge-covering walks of G. This problem was first considered by Tomescu and Medvedev (RECOMB 2016), who characterized these walks through the notion of omnitig. Omnitigs were shown to be relevant for the genome assembly problem from bioinformatics, where a genome sequence must be assembled from a set of reads from a sequencing experiment. Tomescu and Medvedev (RECOMB 2016) also proposed an algorithm for listing all maximal omnitigs, by launching an exhaustive visit from every edge. In this paper, we prove new insights about the structure of omnitigs and solve several open questions about them. We combine these to achieve an O(nm)-time algorithm for outputting all the maximal omnitigs of a graph (with n nodes and m edges). This is also optimal, as we show families of graphs whose total omnitig length is ?(nm). We implement this algorithm and show that it is 9-12 times faster in practice than the one of Tomescu and Medvedev (RECOMB 2016).

All ACM Journals | See Full Journal Index

Search TALG
enter search term and/or author name