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]

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family\scrF. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTASs) for planar input graphs G, using a variety of techniques like the shifting technique [B. S. Baker, J. ACM, 41 (1994), pp. 153--180], bidimensionality [F. V. Fomin et al., Bidimensionality and EPTAS, in Proceedings of SODA 2011, ACM, New York, SIAM, Philadelphia, 2011, pp. 748--759], or connectivity domination [V. Cohen-Addad et al., Approximating connectivity domination in weighted bounded-genus graphs, in Proceedings of STOC 2016, ACM, New York, 2016, pp. 584--597]. These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the Even Cycle Transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini, Joret, and Pietropaoli [Hitting diamonds and growing cacti, in Proceedings of IPCO 2010, Lecture Notes in Comput. Sci. 6080, Springer, Berlin, 2010, pp. 191--204] showed that the integrality gap of the standard covering LP relaxation is\Theta (log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7\approx 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap upper bound of the same value for the standard LP relaxation on node-weighted planar graphs. [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 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]

We consider the problem of maximizing welfare when allocating m items to n players with subadditive utility functions. Our main result is a way of rounding any fractional solution to a linear programming relaxation to this problem so as to give a feasible solution of welfare at least 1/2 that of the value of the fractional solution. This approximation ratio of 1/2 is an improvement over an Ω(1/ log m) ratio of Dobzinski, Nisan, and Schapira [Proceedings of the 37th Annual ACM Symposium on Theory of Computing (Baltimore, MD), ACM, New York, 2005, pp. 610-618]. We also show an approximation ratio of 1 - 1/e when utility functions are fractionally subadditive. A result similar to this last result was previously obtained by Dobzinski and Schapira [Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (Miami, FL), SIAM, Philadelphia, 2006, pp. 1064-1073], but via a different rounding technique that requires the use of a so-called "XOS oracle." The randomized rounding techniques that we use are oblivious in the sense that they only use the primal solution to the linear program relaxation, but have no access to the actual utility functions of the players. [ABSTRACT FROM AUTHOR]