Realworld problems often have parameters that are uncertain during the
optimization phase; stochastic optimization or stochastic programming is a key
approach introduced by Beale and by Dantzig in the 1950s to address such uncertainty. Matching is a classical problem in combinatorial optimization. Modern stochastic versions of this problem model problems in kidney exchange, for instance. We improve upon the currentbest approximation bound of 3.709 for stochastic matching due to Adamczyk et al. (in: AlgorithmsESA 2015, Springer, Berlin, 2015) to 3.224; we also present improvements on Bansal et al. (Algorithmica 63(4):733–762, 2012) for hypergraph matching and for relaxed versions of the problem. These results are obtained by improved analyses and/or algorithms for rounding linearprogramming relaxations of these problems.
more »
« less
Algorithms to Approximate ColumnSparse Packing Problems
Columnsparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (nonuniform) attenuation and multiplechance algorithms, to obtain improved approximation
algorithms for some wellknown families of such problems. As three main examples, we attain the integrality gap, up to lowerorder terms, for known LP relaxations for kcolumn sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic kset packing (Bansal et al., Algorithmica, 2012), and go “half the remaining distance” to optimal for a major integralitygap conjecture of Furedi, Kahn and Seymour on hypergraph matching (Combinatorica, 1993).
more »
« less
 Award ID(s):
 1749864
 NSFPAR ID:
 10065499
 Date Published:
 Journal Name:
 ACMSIAM Symposium on Discrete Algorithms (SODA)
 Page Range / eLocation ID:
 311330
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Chan, Timothy ; Fischer, Johannes ; Iacono, John ; Herman, Grzegorz (Ed.)We consider twocost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hopconstrained oblivious routing to obtain two sets of results. We address multicommodity buyatbulk network design in the nonuniform setting. Existing polylogarithmic approximations are based on the junction tree approach [Chekuri et al., 2010; Guy Kortsarz and Zeev Nutov, 2011]. We obtain a new polylogarithmic approximation via a natural LP relaxation. This establishes an upper bound on its integrality gap and affirmatively answers an open question raised in [Chekuri et al., 2010]. The rounding is based on recent results in hopconstrained oblivious routing [Ghaffari et al., 2021], and this technique yields a polylogarithmic approximation in more general settings such as set connectivity. Our algorithm for buyatbulk network design is based on an LPbased reduction to hhop constrained network design for which we obtain LPbased bicriteria approximation algorithms. We also consider a faulttolerant version of hhop constrained network design where one wants to design a lowcost network to guarantee short paths between a given set of sourcesink pairs even when k1 edges can fail. This model has been considered in network design [Luis Gouveia and Markus Leitner, 2017; Gouveia et al., 2018; Arslan et al., 2020] but no approximation algorithms were known. We obtain polylogarithmic bicriteria approximation algorithms for the singlesource setting for any fixed k. We build upon the singlesource algorithm and the junctiontree approach to obtain an approximation algorithm for the multicommodity setting when at most one edge can fail.more » « less

In the Euclidean kMeans problem we are given a collection of n points D in an Euclidean space and a positive integer k. Our goal is to identify a collection of k points in the same space (centers) so as to minimize the sum of the squared Euclidean distances between each point in D and the closest center. This problem is known to be APXhard and the current best approximation ratio is a primaldual 6.357 approximation based on a standard LP for the problem [Ahmadian et al. FOCS'17, SICOMP'20]. In this note we show how a minor modification of Ahmadian et al.'s analysis leads to a slightly improved 6.12903 approximation. As a related result, we also show that the mentioned LP has integrality gap at least (16+Sqrt(5))/15 > 1.2157. .more » « less

Belkin, Mikhail ; Kpotufe, Samor (Ed.)We present an $e^{O(p)} (\log \ell) / (\log \log \ell)$approximation algorithm for socially fair clustering with the $\ell_p$objective. In this problem, we are given a set of points in a metric space. Each point belongs to one (or several) of $\ell$ groups. The goal is to find a $k$medians, $k$means, or, more generally, $\ell_p$clustering that is simultaneously good for all of the groups. More precisely, we need to find a set of $k$ centers $C$ so as to minimize the maximum over all groups $j$ of $\sum_{u \text{ in group } j} d(u, C)^p$. The socially fair clustering problem was independently proposed by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021). Our algorithm improves and generalizes their $O(\ell)$approximation algorithms for the problem. The natural LP relaxation for the problem has an integrality gap of $\Omega(\ell)$. In order to obtain our result, we introduce a strengthened LP relaxation and show that it has an integrality gap of $\Theta((\log \ell) / (\log \log \ell))$ for a fixed p. Additionally, we present a bicriteria approximation algorithm, which generalizes the bicriteria approximation of Abbasi et al. (2021).more » « less

In an optimal design problem, we are given a set of linear experiments v1,…,vn∈Rd and k≥d, and our goal is to select a set or a multiset S⊆[n] of size k such that Φ((∑i∈Sviv⊤i)−1) is minimized. When Φ(M)=Determinant(M)1/d, the problem is known as the Doptimal design problem, and when Φ(M)=Trace(M), it is known as the Aoptimal design problem. One of the most common heuristics used in practice to solve these problems is the local search heuristic, also known as the Fedorov’s exchange method (Fedorov, 1972). This is due to its simplicity and its empirical performance (Cook and Nachtrheim, 1980; Miller and Nguyen, 1994; Atkinson et al., 2007). However, despite its wide usage no theoretical bound has been proven for this algorithm. In this paper, we bridge this gap and prove approximation guarantees for the local search algorithms for Doptimal design and Aoptimal design problems. We show that the local search algorithms are asymptotically optimal when kd is large. In addition to this, we also prove similar approximation guarantees for the greedy algorithms for Doptimal design and Aoptimal design problems when k/d is large.more » « less