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.

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.

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.

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.

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.

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.

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

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.

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 t_{0} ? (t_{1} ? (t_{2} ? ( ... t_{m-1}) ... ) or t_{0} ? (t_{1} ? (t_{2} ? ( ... t_{m-1}) ... ). We present an algorithm that computes the fastest known Boolean circuit for an And-Or path with given arrival times a(t_{0}), ..., a(t_{m-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 log_{2} W + log_{2} log_{2} m + log_{2} log_{2} log_{2} m + 4.3, where W := ?_{i = 0}^{m-1} 2^{a(ti)}. Note that ?log_{2} W? is a lower bound on the delay of any circuit depending on inputs t_{0}, ..., t_{m-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.

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

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.

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