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]

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]

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]