In this paper we provide an
This content will become publicly available on July 23, 2025
We present dynamic algorithms with
Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS’21) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier.
more » « less- Award ID(s):
- 2238138
- PAR ID:
- 10536452
- Publisher / Repository:
- Association for Computing Machinery
- Date Published:
- Journal Name:
- Journal of the ACM
- ISSN:
- 0004-5411
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
O (m loglogO (1)n log (1/ϵ))-expected time algorithm for solving Laplacian systems onn -nodem -edge graphs, improving upon the previous best expected runtime of\(O(m \sqrt {\log n} \mathrm{log log}^{O(1)} n \log (1/\epsilon)) \) \(\mathbb {R}^d \) k > 1 there exist an ultra-sparsifier withd − 1 +O (d /k ) re-weighted vectors of relative condition number at mostk 2. For smallk , this improves upon the previous best known multiplicative factor of\(k \cdot \tilde{O}(\log d) \) n − 1 +O (n /k )-edge ultrasparsifiers of relative condition numberk 1 +o (1)fork =ω (logδ n ) for anyδ > 0: this improves upon the previous work fork =o (exp (log 1/2 −δ n )). -
more » « less
Abstract This paper considers approximation algorithms for generalized
k -median problems. These problems can be informally described ask -median with a constant number of extra constraints, and includesk -median with outliers, and knapsack median. Our first contribution is a pseudo-approximation algorithm for generalizedk -median that outputs a 6.387-approximate solution, with a constant number of fractional variables. The algorithm builds on the iterative rounding framework introduced by Krishnaswamy, Li, and Sandeep fork -median with outliers as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018). The main technical innovation is allowing richer constraint sets in the iterative rounding and using the structure of the resulting extreme points. Using our pseudo-approximation algorithm, we give improved approximation algorithms fork -median with outliers and knapsack median. This involves combining our pseudo-approximation with pre- and post-processing steps to round a constant number of fractional variables at a small increase in cost. Our algorithms achieve approximation ratios$$6.994 + \epsilon $$ $$6.387 + \epsilon $$ k -median with outliers and knapsack median, respectively. These improve on the best-known approximation ratio$$7.081 + \epsilon $$ -
more » « less
Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulation
X on a directed graphG into weighted source-to-sink paths whose weighted sum equalsX . We show that, for acyclic graphs, considering thewidth of the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class ofwidth-stable graphs, for which a popular heuristic is aO (logVal (X ))-approximation (Val (X ) being the total flow ofX ), and strengthen its worst-case approximation ratio from\(\Omega (\sqrt {m})\) m /logm ) for sparse graphs, wherem is the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a (⌈ log ‖ X ‖ ⌉ +1)-approximation (‖X ‖ being the maximum absolute value ofX on any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations (‖X ‖ ≤ 1), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (non-negative) flow decompositions posed by Kloster et al. [2018 ], but show that its useful implication (polynomial-time assignments of weights to a given set of paths to decompose a flow) holds for the negative version. -
We consider the maximum matching problem in the semi-streaming model formalized by Feigenbaum, Kannan, McGregor, Suri, and Zhang that is inspired by giant graphs of today. As our main result, we give a two-pass (1/2 + 1/16)-approximation algorithm for triangle-free graphs and a two-pass (1/2 + 1/32)-approximation algorithm for general graphs; these improve the approximation ratios of 1/2 + 1/52 for bipartite graphs and 1/2 + 1/140 for general graphs by Konrad, Magniez, and Mathieu. In three passes, we are able to achieve approximation ratios of 1/2 + 1/10 for triangle-free graphs and 1/2 + 1/19.753 for general graphs. We also give a multi-pass algorithm where we bound the number of passes precisely—we give a (2/3 − ε)- approximation algorithm that uses 2/(3ε) passes for triangle-free graphs and 4/(3ε) passes for general graphs. Our algorithms are simple and combinatorial, use O(n log n) space, and (can be implemented to) have O(1) update time per edge. For general graphs, our multi-pass algorithm improves the best known deterministic algorithms in terms of the number of passes: * Ahn and Guha give a (2/3−ε)-approximation algorithm that uses O(log(1/ε)/ε2) passes, whereas our (2/3 − ε)-approximation algorithm uses 4/(3ε) passes; * they also give a (1 − ε)-approximation algorithm that uses O(log n · poly(1/ε)) passes, where n is the number of vertices of the input graph; although our algorithm is (2/3−ε)-approximation, our number of passes do not depend on n. Earlier multi-pass algorithms either have a large constant inside big-O notation for the number of passes or the constant cannot be determined due to the involved analysis, so our multi-pass algorithm should use much fewer passes for approximation ratios bounded slightly below 2/3.more » « less
-
more » « less
We study the problem of approximating maximum Nash social welfare (NSW) when allocating
m indivisible items amongn asymmetric agents with submodular valuations. TheNSW is a well-established notion of fairness and efficiency, defined as the weighted geometric mean of agents’ valuations. For special cases of the problem with symmetric agents and additive(-like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with a factor independent ofm was known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(-like) valuations before this work.In this article, we extend our understanding of the
NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations. Both algorithms are simple to understand and involve non-trivial modifications of a greedy repeated matchings approach. Allocations of high-valued items are done separately by un-matching certain items and re-matching them by different processes in both algorithms. We show that these approaches achieve approximation factors ofO (n ) andO (n logn ) for additive and submodular cases, independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envy-free up to one item (EF1 ).Furthermore, we show that the
NSW problem under submodular valuations is strictly harder than all currently known settings with an\(\frac{\mathrm{e}}{\mathrm{e}-1}\) \(\frac{\mathrm{e}}{\mathrm{e}-1}\)
