Search

We abstract and study reachability preservers, a graph-theoretic primitive that has been implicit in prior work on network design. Given a directed graph G=(V,E) and a set of demand pairs P⊆VxV, a reachability preserver is a sparse subgraph H that preserves reachability between all demand pairs. Our first contribution is a series of extremal bounds on the size of reachability preservers. Our main result states that, for an n-node graph and demand pairs of the form P⊆SxV for a small node subset S, there is always a reachability preserver on O(n+√n/P//S/) edges. We additionally give a lower bound construction demonstrating that this upper bound characterizes the settings in which O(n) size reachability preservers are generally possible, in a large range of parameters. The second contribution of this paper is a new connection between extremal graph sparsification results and classical Steiner Network Design problems. Surprisingly, prior to this work, the osmosis of techniques between these two fields had been superficial. This allows us to improve the state of the art approximation algorithms for the most basic Steiner-type problem in directed graphs from the O(n0.6+ε) of Chlamatac, et al. [Approximating spanners and directed steiner forest: Upper and lower bounds, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 534-443] (n4/7+ε). [ABSTRACT FROM AUTHOR]

In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min\{ O(log n), f\} approximation factor. (Throughout, n, m, f, and C are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when f = \Omega (log n), this was achieved by a deterministic O(log n)-approximation algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537--550]. In this paper we consider the low-frequency range, when f =O(log n), and obtain deterministic algorithms with a (1 + \epsilon)f-approximation ratio and the following guarantees on the update time. (1) O((f/\epsilon) \cdot log(Cn)) amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was O(f2) of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206--218]. In contrast, the only result with O(f)-approximation was that of Abboud et al. [Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114--125], who designed a randomized (1+\epsilon)f-approximation algorithm with O((f2/\epsilon) \cdot log n) amortized update time. (2) O \bigl(f2/\epsilon 3 + (f/\epsilon 2) \cdot logC \bigr) amortized update time: This result improves the above update time bound for most values of f in the low-frequency range, i.e., f =o(log n). It is also the first result that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically maintaining a (2 + \epsilon)-approximate minimum vertex cover in O(1/\epsilon 2) amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872--1885] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). (3) O((f/\epsilon 3) \cdot log2(Cn)) worst-case update time: No nontrivial worst-case update time was previously known for the dynamic set cover problem. Our bound subsumes and improves by a logarithmic factor the O(log3 n/\sansp \sanso \sansl \sansy (\epsilon)) worst-case update time for the unweighted dynamic vertex cover problem (i.e., when f = 2 and C = 1) of Bhattacharya, Henzinger, and Nanongkai [Fully dynamic approximate maximum matching and minimum vertex cover in O(log3)n worst case update time, in Proceedings SODA 2017, SIAM, pp. 470--489]. We achieve our results via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual approach uses a local update scheme that maintains relaxed complementary slackness conditions for every set. For our first result we use instead a global update scheme that does not always maintain complementary slackness conditions. For our second result we combine the global and the local update schema. To achieve our third result we use a hierarchy of background schedulers. It is an interesting open question whether this background scheduler technique can also be used to transform algorithms with amortized running time bounds into algorithms with worst-case running time bounds. [ABSTRACT FROM AUTHOR]

We investigate offline and online algorithms for Round - UFPP , the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform size on a given path with heterogeneous edge capacities. Round - UFPP is known to be NP-hard and there are constant-factor approximation algorithms under the no bottleneck assumption (NBA), which stipulates that maximum size of any flow is at most the minimum global edge capacity. In this work, we present improved online and offline algorithms for Round - UFPP without the NBA. We first study offline Round - UFPP for a restricted class of instances, called α -small, where the size of each flow is at most α times the capacity of its bottleneck edge, and present an O (log (1 / (1 - α))) -approximation algorithm. Next, our main result is an online O (log log c max) -competitive algorithm for Round - UFPP where c max is the largest edge capacity, improving upon the previous best bound of O (log c max) due to Epstein et al. (SIAM J Discrete Math 23(2):822–841, 2009). These new results lead to an offline O (min (log n , log m , log log c max)) -approximation algorithm and an online O (min (log m , log log c max)) -competitive algorithm for Round - UFPP , where n is the number of flows and m is the number of edges. [ABSTRACT FROM AUTHOR]

The terminal backup problems ([E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678--708]) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum-cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga [SIAM J. Discrete Math., 30 (2016), pp. 777--800] gave a 4/3-approximation algorithm based on an LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in O(mlog(n-A · MF(/cn,m T/c2n)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, A is the maximum edge-cost, U is the maximum edge-capacity, and MF(nz,mz) is the time complexity of a max-flow algorithm in a network with nz nodes and m' edges. The algorithm implies that the 4/3-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, which is called a separately capacitated multiflow. We show a min-max theorem which extends the Lovasz-Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem. [ABSTRACT FROM AUTHOR]

In this paper, we derive a new recovery procedure for the reconstruction of extended exponential sums of the form y (t) = ∑ j = 1 M (∑ m = 0 n j γ j , m t m) e 2 π λ j t , where the frequency parameters λ j ∈ ℂ are pairwise distinct. In order to reconstruct y(t) we employ a finite set of classical Fourier coefficients of y with regard to a finite interval (0 , P) ⊂ ℝ with P > 0. For our method, 2N + 2 Fourier coefficients c k (y) are sufficient to recover all parameters of y, where N : = ∑ j = 1 M (1 + n j) denotes the order of y(t). The recovery is based on the observation that for λ j ∉ i P ℤ the terms of y(t) possess Fourier coefficients with rational structure. We employ a recently proposed stable iterative rational approximation algorithm in [Y. Nakatsukasa, O. Sète and L. N. Trefethen, The AAA Algorithm for rational approximation, SIAM J. Sci. Comput.40(3) (2018) A1494A1522]. If a sufficiently large set of L Fourier coefficients of y is available (i.e. L ≥ 2 N + 2), then our recovery method automatically detects the number M of terms of y, the multiplicities n j for j = 1 , ... , M , as well as all parameters λ j , j = 1 , ... , M , and γ j , m , j = 1 , ... , M , m = 0 , ... , n j , determining y(t). Therefore, our method provides a new stable alternative to the known numerical approaches for the recovery of exponential sums that are based on Prony's method. [ABSTRACT FROM AUTHOR]

Inspired by the seminal works of Khuller et al. (SIAM J. Comput. 25(2), 355–368 (1996)) and Chan (Discrete Comput. Geom. 32(2), 177–194 (2004)) we study the bottleneck version of the Euclidean bounded-degree spanning tree problem. A bottleneck spanning tree is a spanning tree whose largest edge-length is minimum, and a bottleneck degree-K spanning tree is a degree-K spanning tree whose largest edge-length is minimum. Let β K be the supremum ratio of the largest edge-length of the bottleneck degree-K spanning tree to the largest edge-length of the bottleneck spanning tree, over all finite point sets in the Euclidean plane. It is known that β 5 = 1 , and it is easy to verify that β 2 ⩾ 2 , β 3 ⩾ 2 , and β 4 > 1.175 . It is implied by the Hamiltonicity of the cube of the bottleneck spanning tree that β 2 ⩽ 3 . The degree-3 spanning tree algorithm of Ravi et al. (25th Annual ACM Symposium on Theory of Computing, pp. 438–447. ACM, New York (1993)) implies that β 3 ⩽ 2 . Andersen and Ras (Networks 68(4), 302–314 (2016)) showed that β 4 ⩽ 3 . We present the following improved bounds: β 2 ⩾ 7 , β 3 ⩽ 3 , and β 4 ⩽ 2 . As a result, we obtain better approximation algorithms for Euclidean bottleneck degree-3 and degree-4 spanning trees. As parts of our proofs of these bounds we present some structural properties of the Euclidean minimum spanning tree which are of independent interest. [ABSTRACT FROM AUTHOR]

The characterization of all the constraint satisfaction problems solvable by local consistency checking (also known as CSPs of bounded width) was proposed by Feder and Vardi [SIAM J. Comput., 28 (1998), pp. 57104]. It was confirmed by two independent proofs by Bulatov [Bounded Relational Width, manuscript, 2009] and Barto and Kozik [L. Barto and M. Kozik, 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 595 603], [L. Barto and M. Kozik, J. ACM, 61 (2014), 3]. Later Barto [J. Logic Comput., 26 (2014), pp. 923 943] proved a collapse of the hierarchy of local consistency notions by showing that (2; 3) minimality solves all the CSPs of bounded width. In this paper we present a new consistency notion, jpq consistency, which also solves all the CSPs of bounded width. Our notion is strictly weaker than (2; 3) consistency, (2; 3) minimality, path consistency, and singleton arc consistency (SAC). This last fact allows us to answer the question of Chen, Dalmau, and Gruien [J. Logic Comput., 23 (2013), pp. 87 108] by confirming that SAC solves all the CSPs of bounded width. Moreover, as known algorithms work faster for SAC, the result implies that CSPs of bounded width can be, in practice, solved more efficiently. The definition of jpq consistency is closely related to a consistency condition obtained from the rounding of an SDP relaxation of a CSP instance. In fact, the main result of this paper is used by Dalmau et al. [Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, ACM, New York, 2017, pp. 340{357] to show that CSPs with near unanimity polymorphisms admit robust approximation algorithms with polynomial loss. Finally, an algebraic characterization of some term conditions satisfied in algebras associated with templates of bounded width, first proved by Brady, is a direct consequence of our result. [ABSTRACT FROM AUTHOR]

The Prize-collecting Steiner tree (PCST) problem is a generalization of the Steiner tree problem that finds applications in network design, content distribution networks, and many more. There are a few centralized approximation algorithms [D. Bienstock, M. X. Goemans, D. Simchi-Levi and D. Williamson, A note on the prize collecting traveling salesman problem. Math. Program.59 (1993) 413–420; M. X. Goemans and D. E. Williamson, A general approximation technique for constrained forest problems, SIAM J. Appl. Math.24(2) (1995) 296–317; D. S. Johnson, M. Minkoff and S. Phillips, The prize collecting Steiner tree problem: Theory and practice, in Proc. Eleventh Annual ACM-SIAM Symp. Discrete Algorithms, SODA '00 (2000), pp. 760–769; A. Archer, M. Hossein Bateni and M. Taghi Hajiaghayi, Improved approximation algorithms for prize-collecting Steiner tree and TSP, SIAM J. Comput.40(2) (2011) 309–332] for solving the PCST problem. However, the problem has seen very little progress in the distributed setting; to the best of our knowledge, the only distributed algorithms proposed so far are due to Rossetti [N. G. Rossetti, A first attempt on the distributed prize-collecting Steiner tree problem, M.Sc. thesis, University of Iceland, Reykjavik (2015)]: one of them fails to guarantee a constant approximation factor while the other one is essentially centralized. In this work, first, we present a deterministic 2 − 1 n − 1 factor distributed approximation algorithm (D-PCST algorithm) that constructs a PCST for a given connected undirected graph of n nodes with non-negative edge weights and non-negative prize value for each node. The D-PCST algorithm is based on the primal-dual method and uses a technique of preserving dual constraints in a distributed manner, without relying on knowledge of the global structure of the network. For an input graph G = (V , E) , the round and message complexities of the D-PCST algorithm in the CONGEST model are O (n 2) and O (m n) , respectively, where n = | V | and m = | E |. Furthermore, we modify the D-PCST algorithm and show that a (2 − 1 n − 1) -approximate PCST can be deterministically computed using O (D n) rounds and O (m n) messages in the CONGEST model, where D is the unweighted diameter of G. For networks with D = o (n) , the modified D-PCST algorithm performs better than the original one in terms of the round complexity. Both the algorithms require O (Δ log n) bits of memory in each node, where Δ is the maximum degree of a node in the graph. [ABSTRACT FROM AUTHOR]

Submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained k-submodular maximization, Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404-413] gave a randomized k/(2k 1)-approximation algorithm for monotone functions and a randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives a k2+1 2k2+1 -approximation for k geq 3. We also give a randomized surd 17 3 2 -approximation algorithm for k = 3. We use the same framework used in Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404--413] and Ward and v Zivn'y [ACM Trans. Algorithms, 12 (2016), pp. 46:1--47:26] with different probabilities. [ABSTRACT FROM AUTHOR]

We consider approximation algorithms for packing integer programs (PIPs) of the form max { ⟨ c , x ⟩ : A x ≤ b , x ∈ { 0 , 1 } n } where A, b and c are nonnegative. We let W = min i , j b i / A i , j denote the width of A which is at least 1. Previous work by Bansal et al. (Theory Comput 8(24):533–565, 2012) obtained an Ω (1 Δ 0 1 / ⌊ W ⌋ ) -approximation ratio where Δ 0 is the maximum number of nonzeroes in any column of A (in other words the ℓ 0 -column sparsity of A). They raised the question of obtaining approximation ratios based on the ℓ 1 -column sparsity of A (denoted by Δ 1 ) which can be much smaller than Δ 0 . Motivated by recent work on covering integer programs (Chekuri and Quanrud, in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1596–1615. SIAM, 2019; Chen et al., in: Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1984–2003. SIAM, 2016) we show that simple algorithms based on randomized rounding followed by alteration, similar to those of Bansal et al. (Theory Comput 8(24):533–565, 2012) (but with a twist), yield approximation ratios for PIPs based on Δ 1 . First, following an integrality gap example from (Theory Comput 8(24):533–565, 2012), we observe that the case of W = 1 is as hard as maximum independent set even when Δ 1 ≤ 2 . In sharp contrast to this negative result, as soon as width is strictly larger than one, we obtain positive results via the natural LP relaxation. For PIPs with width W = 1 + ϵ where ϵ ∈ (0 , 1 ] , we obtain an Ω (ϵ 2 / Δ 1) -approximation. In the large width regime, when W ≥ 2 , we obtain an Ω ((1 1 + Δ 1 / W) 1 / (W - 1)) -approximation. We also obtain a (1 - ϵ) -approximation when W = Ω (log (Δ 1 / ϵ) ϵ 2) . Viewing the rounding algorithms as contention resolution schemes, we obtain approximation algorithms in the more general setting when the objective is a non-negative submodular function. [ABSTRACT FROM AUTHOR]

We revisit the classic problem of estimating the moments of the degree distribution of an undirected simple graph. Consider an undirected simple graph G = (V,E) with n (nonisolated) vertices, and define (for s > 0) Ms =\sum v\in V ds v. Our aim is to estimate Ms within a multiplicative error of (1 +\varepsilon) (for a given approximation parameter\varepsilon > 0) in sublinear time. We consider the sparse-graph model that allows access to uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of s = 1 (the average degree), O\ast (\surd n) queries suffice for any constant\varepsilon [U. Feige, SIAM J. Comput., 35 (2006), pp. 964--984], [O. Goldreich and D. Ron, Random Structures Algorithms, 32 (2008), pp. 473--493]. (We use the O\ast notation to suppress dependencies in log n and 1/\varepsilon.) Gonen, Ron, and Shavitt [SIAM J. Discrete Math., 25 (2011), pp. 1365--1411] extended this result to all integral s > 0 by designing an algorithm that performs O\ast (n1 1/(s+1)) queries. (Strictly speaking, their algorithm approximates the number of star-subgraphs of a given size, but a slight modification gives an algorithm for moments.) We design a new, significantly simpler algorithm for this problem. In the worst case, it exactly matches the bounds of Gonen, Ron, and Shavitt and has a much simpler proof. More importantly, the running time of this algorithm is connected to the arboricity of G. This is (essentially) the maximum density of an induced subgraph. For the family of graphs with arboricity at most\alpha, it has a query complexity of O\ast\bigl(n\cdot\alpha 1/s M 1/s s + min\bigl\{ m M 1/s s, m\cdot ns 1 Ms\bigr\}\bigr) which is always upper bounded by O\ast\bigl(n\alpha M 1/s s\bigr). Thus, for the class of constant-arboricity graphs (which includes, among others, all minor-closed families and preferential attachment graphs), we can estimate the average degree in O\ast (1) queries, and we can estimate the variance of the degree distribution in O\ast (\surd n) queries. This is a major improvement over the previous worst-case bounds. [ABSTRACT FROM AUTHOR]

We study the restricted case of Scheduling on Unrelated Parallel Machines. In this problem, we are given a set of jobs J with processing times pj and each job may be scheduled only on some subset of machines Sj⊆ M. The goal is to find an assignment of jobs to machines to minimize the time within which all jobs can be processed. In a seminal paper, Lenstra, Shmoys, and Tardos [Proceedings of the 28th Annual IEEE Conference on Foundations of Computer Science, 1987, pp. 217--224] designed an elegant 2-approximation for the problem. The question of whether approximation algorithms with better guarantees exist for this classic scheduling problem has since remained a source of mystery. In recent years, with the improvement of our understanding of configuration linear programs, it now appears an attainable goal to design such an algorithm. Our main contribution in this paper is to make progress towards this goal. For the so-called (1, ε)-case, when the processing times of jobs are either 1 or ε ∊ (0, 1), we design an approximation algorithm whose guarantee tends to 1+√3/2 ≈ 1.866025 as ε tends to zero. This improves on the 2 ε0 guarantee recently obtained by Chakrabarty, Khanna, and Li [Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2015, pp. 1087--1101] for some constant ε0 > 0. Further, the ideas presented in this paper do not crucially depend on the fact that the instances contain exactly two different job sizes; i.e., they extend also to families of instances more general than the (1, ε)-case. In a certain precise sense, we fall slightly short of improving on the 30-year-old classic algorithm of Lenstra, Shmoys, and Tardos [Proceedings of the 28th Annual IEEE Conference on Foundations of Computer Science, 1987, pp. 217--224] for the restricted case. [ABSTRACT FROM AUTHOR]