DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.72

On Tight FPT Time Approximation Algorithms for k-Clustering Problems

Authors: Han Dai, Shi Li, and Sijin Peng

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

Following recent advances in combining approximation algorithms with fixed-parameter tractability (FPT), we study FPT-time approximation algorithms for minimum-norm k-clustering problems, parameterized by the number k of open facilities. For the capacitated setting, we give a tight (3+ε)-approximation for the general-norm capacitated k-clustering problem in FPT-time parameterized by k and ε. Prior to our work, such a result was only known for the capacitated k-median problem [Cohen-Addad and Li, 2019]. As a special case, our result yields an FPT-time 3-approximation for capacitated k-center. The problem has not been studied in the FPT-time setting, with the previous best known polynomial-time approximation ratio being 9 [An et al., 2015]. In the uncapacitated setting, we consider the top-cn norm k-clustering problem, where the goal of the problem is to minimize the top-cn norm of the connection distance vector. Our main result is a tight (1 + 2/(ec) + ε)-approximation algorithm for the problem with c ∈ (1/e, 1]. (For the case c ≤ 1/e, there is a simple tight (3+ε)-approximation.) Our framework can be easily extended to give a tight (3, 1 + 2/e + ε)-bi-criteria approximation for the (k-center, k-median) problem in FPT time, improving the previous best polynomial-time (4, 8) guarantee [Soroush Alamdari and David B. Shmoys, 2017]. All results are based on a unified framework: computing a (1+ε)-approximate solution using O((k log n)/ε) facilities S via LP rounding, sampling a few client representatives R based on the solution S, guessing a few pivots from S ∪ R and some radius information on the pivots, and solving the problem using the guesses. We believe this framework can lead to further results on k-clustering problems.

Cite as

Han Dai, Shi Li, and Sijin Peng. On Tight FPT Time Approximation Algorithms for k-Clustering Problems. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 72:1-72:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dai_et_al:LIPIcs.ICALP.2026.72,
  author =	{Dai, Han and Li, Shi and Peng, Sijin},
  title =	{{On Tight FPT Time Approximation Algorithms for k-Clustering Problems}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{72:1--72:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.72},
  URN =		{urn:nbn:de:0030-drops-264613},
  doi =		{10.4230/LIPIcs.ICALP.2026.72},
  annote =	{Keywords: Approximation algorithms, Monotone symmetric norms, Clustering, Fixed parameter tractability}
}

Document

DOI: 10.4230/LIPIcs.SEA.2026.26

Engineering Algorithms for Dynamic Greedy Set Cover

Authors: Amitai Uzrad

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract

In the dynamic set cover problem, the input is a dynamic universe of elements and a fixed collection of sets. As elements are inserted or deleted, the goal is to efficiently maintain an approximate minimum set cover. While the past decade has seen significant theoretical breakthroughs for this problem, a notable gap remains between theoretical design and practical performance, as no comprehensive experimental study currently exists to validate these results. In this paper, we bridge this gap by implementing and evaluating four greedy-based dynamic algorithms across a diverse range of real-world instances. We derive our implementations from state-of-the-art frameworks - such as [GKKP(STOC'17); SU(STOC'23); SUZ(FOCS'24)] - which we simplify by identifying and modifying intricate subroutines that optimize asymptotic bounds but hinder practical performance. We evaluate these algorithms based on solution quality (set cover size) and efficiency, which comprises update time - the time required to update the solution following each insertion/deletion - and recourse - the number of changes made to the solution per update. Each algorithm uses a parameter β to balance quality against efficiency; we investigate the influence of this tradeoff parameter on each algorithm and then perform a comparative analysis to evaluate the algorithms against each other. Our results provide the first practical insights into which algorithmic strategies provide the most value in realistic scenarios.

Cite as

Amitai Uzrad. Engineering Algorithms for Dynamic Greedy Set Cover. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{uzrad:LIPIcs.SEA.2026.26,
  author =	{Uzrad, Amitai},
  title =	{{Engineering Algorithms for Dynamic Greedy Set Cover}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.26},
  URN =		{urn:nbn:de:0030-drops-260308},
  doi =		{10.4230/LIPIcs.SEA.2026.26},
  annote =	{Keywords: Dynamic graphs, set cover, recourse}
}

Document

DOI: 10.4230/LIPIcs.SEA.2026.21

An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem

Authors: Luke Hawranick, Matthew Williamson, Jacob Restanio, K. Subramani, and Cody Klingler

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract

In this paper, we perform an experimental study of approximation algorithms for the unweighted tree augmentation problem (UTAP). Our goal is to establish a baseline performance for several existing approximation algorithms on actual instances rather than worst-case instances. In particular, we are interested in whether the algorithms' performance in practical instances is consistent with their worst-case guarantee rankings. We are also interested in whether preprocessing times, implementation difficulties, and running times justify the use of an algorithm in practice. We profile and analyze three approximation algorithms from the literature against a simple randomized algorithm. The performance of each algorithm was evaluated using metrics for space usage, running time, and solution quality. We found that the simple randomized algorithm is very competitive with the approximation algorithms and that the algorithms do not necessarily rank according to their theoretical guarantees. The randomized algorithm is easier to implement and understand, using less space than any of the more sophisticated approximation algorithms.

Cite as

Luke Hawranick, Matthew Williamson, Jacob Restanio, K. Subramani, and Cody Klingler. An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hawranick_et_al:LIPIcs.SEA.2026.21,
  author =	{Hawranick, Luke and Williamson, Matthew and Restanio, Jacob and Subramani, K. and Klingler, Cody},
  title =	{{An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.21},
  URN =		{urn:nbn:de:0030-drops-260259},
  doi =		{10.4230/LIPIcs.SEA.2026.21},
  annote =	{Keywords: Graphs, Networks, Tree Augmentation, Approximation Algorithms, Empirical}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.8

Submodular Max-Min Allocation Under Identical Valuations

Authors: Kimon Boehmer

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

In the problem of Submodular Max-Min Allocation, we are given a set of items, a set of players, and monotone submodular valuation functions that represent the satisfaction of a player with a certain subset of items. The goal is to find an allocation of the items to the players that maximizes the lowest satisfaction among all players. We study this problem in the special case where all players have the same valuation function. We devise a greedy algorithm which gives a 0.4-approximation, improving the previously best factor of 10/27 ≈ 0.37 by Uziahu and Feige. Furthermore, we study the integrality gap of the configuration LP when players have identical valuations. By constructing a variable assignment to the dual from a primal integral solution, we give the first constant upper bound on the integrality gap for submodular valuations. Generalizing the result to the case where players' allocations must be independent in k given matroids, we derive a 𝒪(k)-estimation algorithm for max-min allocation subject to k matroid constraints under identical valuations.

Cite as

Kimon Boehmer. Submodular Max-Min Allocation Under Identical Valuations. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{boehmer:LIPIcs.SWAT.2026.8,
  author =	{Boehmer, Kimon},
  title =	{{Submodular Max-Min Allocation Under Identical Valuations}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.8},
  URN =		{urn:nbn:de:0030-drops-260446},
  doi =		{10.4230/LIPIcs.SWAT.2026.8},
  annote =	{Keywords: Submodularity, Approximation algorithms, Allocation, Configuration LP}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.19

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means

Authors: Nicole Funk, Annika Hennes, Johanna Hillebrand, and Sarah Sturm

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

We study discrete k-clustering problems in general metric spaces that are constrained by a combination of two different fairness conditions within the demographic fairness model. Given a metric space (P,d), where every point in P is equipped with a protected attribute, and a number k, the goal is to partition P into k clusters with a designated center each, such that a center-based objective function is minimized and the attributes are fairly distributed with respect to the following two fairness concepts: 1) group fairness: We aim for clusters with balanced numbers of attributes by specifying lower and upper bounds for the desired attribute proportions. 2) diverse center selection: Clusters have natural representatives, i.e., their centers. We ask for a balanced set of representatives by specifying the desired number of centers to choose from each attribute. Dickerson, Esmaeili, Morgenstern, and Pena [John P. Dickerson et al., 2023] denote the combination of these two constraints as doubly constrained fair clustering. They present algorithms whose guarantees depend on the best known approximation factors for either of these problems. Currently, this implies an 8-approximation with a small additive violation on the group fairness constraint. For k-center, we improve this approximation factor to 4 with a small additive violation. This guarantee also depends on the currently best algorithm for DS-fair k-center given by Jones, Nguyen and Nguyen [Matthew Jones et al., 2020]. For k-median and k-means, we propose the first constant-factor approximation algorithms. Our algorithms transform a solution that satisfies diverse center selection into a doubly constrained fair clustering using an LP-based approach. Furthermore, our results are generalizable to other center-selection constraints, such as matroid k-clustering and knapsack constraints.

Cite as

Nicole Funk, Annika Hennes, Johanna Hillebrand, and Sarah Sturm. Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{funk_et_al:LIPIcs.SWAT.2026.19,
  author =	{Funk, Nicole and Hennes, Annika and Hillebrand, Johanna and Sturm, Sarah},
  title =	{{Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.19},
  URN =		{urn:nbn:de:0030-drops-260551},
  doi =		{10.4230/LIPIcs.SWAT.2026.19},
  annote =	{Keywords: Clustering, Fairness, Approximation Algorithms, k-center, k-median, k-means}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.31

Improved and Parameterized Algorithms for Online Multi-Level Aggregation

Authors: Young-San Lin and Alex Turoczy

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

We study the online multi-level aggregation problem with deadlines (MLAP-D) introduced by Bienkowski, Böhm, Byrka, Chrobak, Dürr, Folwarczný, Jeż, Sgall, Thang, and Veselý (ESA 2016, OR 2020). In this problem, requests arrive over time at the vertices of a given vertex-weighted tree, and each request has a deadline that it must be served by. The cost of serving a request equals the cost of a path from the root to the vertex where the request resides. Instead of serving each request individually, requests can be aggregated and served by transmitting a subtree from the root that spans the vertices on which the requests reside, to potentially be more cost-effective. The aggregated cost is the weight of the transmission subtree. The goal of MLAP-D is to find an aggregation solution that minimizes the total cost while serving all requests. MLAP-D generalizes some well-studied problems including the TCP acknowledgment problem and the joint replenishment problem, and arises in natural scenarios such as multi-casting, sensor networks, and supply chain management. We present improved and parameterized algorithms for MLAP-D. Our result is twofold. First, we present an e(D+1)-competitive algorithm where D is the depth of the tree. Second, we present an e(4H+2)-competitive algorithm where H is the caterpillar dimension of the tree. Here, H ≤ D and H ≤ log₂ |V| where |V| is the number of vertices in the given tree. The caterpillar dimension remains constant for rich but simple classes of trees, such as line graphs (H = 1), caterpillar graphs (H = 2), and lobster graphs (H = 3). To the best of our knowledge, this is the first online algorithm parameterized on a measure better than depth. The state-of-the-art online algorithms are 6(D+1)-competitive by Buchbinder, Feldman, Naor, and Talmon (SODA 2017) and O(log |V|)-competitive by Azar and Touitou (FOCS 2020). Our framework outperforms the state-of-the-art ratios when H = o(min{D,log₂ |V|}). Our memory-based algorithms extend transmission subtrees with a cost comparable to transmission subtrees used to serve previous requests. Our simple framework directly applies to trees with any structure and differs from the previous frameworks that reduce the problem to trees with specific structures.

Cite as

Young-San Lin and Alex Turoczy. Improved and Parameterized Algorithms for Online Multi-Level Aggregation. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.SWAT.2026.31,
  author =	{Lin, Young-San and Turoczy, Alex},
  title =	{{Improved and Parameterized Algorithms for Online Multi-Level Aggregation}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.31},
  URN =		{urn:nbn:de:0030-drops-260673},
  doi =		{10.4230/LIPIcs.SWAT.2026.31},
  annote =	{Keywords: Online Algorithms, Approximation Algorithms, Graph Problems}
}

Document

DOI: 10.4230/LIPIcs.FORC.2026.9

Serving Clients Fairly: On Facility Location and k-Median with Fair Outliers

Authors: Rajni Dabas, Samir Khuller, and Emilie Rivkin

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract

Classical clustering problems such as Facility Location and k-Median aim to efficiently serve a set of clients from a subset of facilities - minimizing the total cost of facility openings and client assignments in Facility Location, and minimizing assignment (service) cost under a facility count constraint in k-Median. These problems are highly sensitive to outliers, and therefore researchers have studied variants that allow excluding a small number of clients as outliers to reduce cost. However, in many real-world settings, clients belong to different demographic or functional groups, and unconstrained outlier removal can disproportionately exclude certain groups, raising fairness concerns, especially when the facilities correspond to critically needed facilities for emergencies such as fire stations, hospitals and other emergency services. We study Facility Location with Fair Outliers, where each group is allowed a specified number of outliers, and the objective is to minimize total cost while respecting group-wise fairness constraints. We present a bicriteria approximation with a O(1/ε) approximation factor and (1+ 2ε) factor violation in outliers per group. For k-Median with Fair Outliers, we design a bicriteria approximation with a 4(1+ω/ε) approximation factor and (ω + ε) violation in outliers per group improving on prior work by avoiding dependence on k in outlier violations. We also prove that the problems are W[1]-hard parameterized by ω. We complement our algorithmic contributions with a detailed empirical analysis, demonstrating that fairness can be achieved with negligible increase in cost and that the integrality gap of the standard LP is small in practice.

Cite as

Rajni Dabas, Samir Khuller, and Emilie Rivkin. Serving Clients Fairly: On Facility Location and k-Median with Fair Outliers. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dabas_et_al:LIPIcs.FORC.2026.9,
  author =	{Dabas, Rajni and Khuller, Samir and Rivkin, Emilie},
  title =	{{Serving Clients Fairly: On Facility Location and k-Median with Fair Outliers}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.9},
  URN =		{urn:nbn:de:0030-drops-259812},
  doi =		{10.4230/LIPIcs.FORC.2026.9},
  annote =	{Keywords: Approximation algorithms, fairness}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.48

FPT Approximations for Capacitated Sum of Radii and Diameters

Authors: Arnold Filtser and Ameet Gadekar

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

The Capacitated Sum of Radii problem involves partitioning a set of points P, where each point p ∈ P has capacity U_p, into k clusters that minimize the sum of cluster radii, such that the number of points in the cluster centered at point p is at most U_p. We begin by showing that the problem is APX-hard, and that under gap-ETH there is no parameterized approximation scheme (FPT-AS). We then construct a ≈5.83-approximation algorithm in FPT time (improving a previous ≈7.61 approximation in FPT time). Our results also hold when the objective is a general monotone symmetric norm of radii. We also improve the approximation factors for the uniform capacity case, and for the closely related problem of Capacitated Sum of Diameters.

Cite as

Arnold Filtser and Ameet Gadekar. FPT Approximations for Capacitated Sum of Radii and Diameters. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{filtser_et_al:LIPIcs.SoCG.2026.48,
  author =	{Filtser, Arnold and Gadekar, Ameet},
  title =	{{FPT Approximations for Capacitated Sum of Radii and Diameters}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.48},
  URN =		{urn:nbn:de:0030-drops-258545},
  doi =		{10.4230/LIPIcs.SoCG.2026.48},
  annote =	{Keywords: clustering, sum of radii, sum of diameter, capacitated clustering, fpt}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.14

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems

Authors: Sujoy Bhore, Anupam Gupta, and Amit Kumar

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

In the online hitting set problem, sets arrive over time, and the algorithm has to maintain a subset of elements that hit all the sets seen so far. Alon, Awerbuch, Azar, Buchbinder, and Naor (SICOMP 2009) gave an algorithm with competitive ratio O(log n log m) for the (general) online hitting set and set cover problems for m sets and n elements; this is known to be tight for efficient online algorithms. Given this barrier for general set systems, we ask: can we break this double-logarithmic phenomenon for online hitting set/set cover on structured and geometric set systems? We provide an O(log n log log n)-competitive algorithm for the weighted online hitting set problem on set systems with linear shallow-cell complexity, replacing the double-logarithmic factor in the general result by effectively a single logarithmic term. As a consequence of our results we obtain the first bounds for weighted online hitting set for natural geometric set families, thereby answering open questions regarding the gap between general and geometric weighted online hitting set problems.

Cite as

Sujoy Bhore, Anupam Gupta, and Amit Kumar. Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.14,
  author =	{Bhore, Sujoy and Gupta, Anupam and Kumar, Amit},
  title =	{{Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.14},
  URN =		{urn:nbn:de:0030-drops-258206},
  doi =		{10.4230/LIPIcs.SoCG.2026.14},
  annote =	{Keywords: Hitting Set, Online Algorithms, Shallow-Cell Complexity, VC-Dimension}
}

Document

DOI: 10.4230/OASIcs.NINeS.2026.19

Simulate Before Sending: Rethinking Transport in Datacenter Networks

Authors: Dan Straussman, Isaac Keslassy, Alexander Shpiner, and Liran Liss

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract

Existing transport protocols in commodity datacenter networks struggle to provide low collective completion times (CCTs) to AI training collectives, as packet losses and retransmissions significantly degrade performance. We propose dcSim, an efficient transport that achieves low CCTs and practically lossless performance with commodity switches. In dcSim, each packet first employs a small simulation probe to traverse the network and explore congestion along a candidate path. Only packets whose simulation probes succeed are then transmitted, expecting to succeed as well. Evaluations confirm that dcSim achieves faster CCTs than existing schemes, with small queues and virtually zero packet loss. Finally, dcSim also excels in adverse conditions, including oversubscribed topologies.

Cite as

Dan Straussman, Isaac Keslassy, Alexander Shpiner, and Liran Liss. Simulate Before Sending: Rethinking Transport in Datacenter Networks. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{straussman_et_al:OASIcs.NINeS.2026.19,
  author =	{Straussman, Dan and Keslassy, Isaac and Shpiner, Alexander and Liss, Liran},
  title =	{{Simulate Before Sending: Rethinking Transport in Datacenter Networks}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{19:1--19:22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.19},
  URN =		{urn:nbn:de:0030-drops-256044},
  doi =		{10.4230/OASIcs.NINeS.2026.19},
  annote =	{Keywords: Datacenter networks, transport protocols, AI training, lossless networks}
}

Document

DOI: 10.4230/LIPIcs.STACS.2026.56

A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling

Authors: Klaus Jansen and Felix Ohnesorge

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

In moldable job scheduling, we are provided m identical machines and n jobs that can be executed on a variable number of machines. The execution time of each job depends on the number of machines assigned to execute that job. For the specific problem of monotone moldable job scheduling, jobs are assumed to have a processing time that is non-increasing in the number of machines. The previous best-known algorithms are: (1) a Polynomial Time Approximation Scheme (PTAS) with time complexity Ω(n^{g(1/ε)}), where g(⋅) is a super-exponential function [Jansen and Thöle '08; Jansen and Land '18], (2) a Fully Polynomial Time Approximation Scheme (FPTAS) for the case of m ≥ 8n/(ε) [Jansen and Land '18], and (3) a 3/2 approximation with time complexity O(nmlog(mn)) [Wu, Zhang, and Chen '23]. We present a new practically efficient algorithm with an approximation ratio of ≈ (1.4593 + ε) and a time complexity of O(nm log 1/(ε)). Our result also applies to the contiguous variant of the problem. In addition to our theoretical results, we implement the presented algorithm and show that the practical performance is significantly better than the theoretical worst-case approximation ratio.

Cite as

Klaus Jansen and Felix Ohnesorge. A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 56:1-56:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.STACS.2026.56,
  author =	{Jansen, Klaus and Ohnesorge, Felix},
  title =	{{A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{56:1--56:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.56},
  URN =		{urn:nbn:de:0030-drops-255453},
  doi =		{10.4230/LIPIcs.STACS.2026.56},
  annote =	{Keywords: computing, machine scheduling, moldable, polynomial approximation}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.50

On the PTAS Complexity of Multidimensional Knapsack

Authors: Ilan Doron-Arad, Ariel Kulik, and Pasin Manurangsi

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We study the d-dimensional knapsack problem. We are given a set of items, each with a d-dimensional cost vector and a profit, along with a d-dimensional budget vector. The goal is to select a set of items that do not exceed the budget in all dimensions and maximize the total profit. A polynomial-time approximation scheme (PTAS) with running time n^{Θ(d/{ε})} has long been known for this problem, where {ε} is the error parameter and n is the encoding size. Despite decades of active research, the best running time of a PTAS has remained O(n^{⌈ d/{ε} ⌉ - d}). Unfortunately, existing lower bounds only cover the special case with two dimensions d = 2, and do not answer whether there is a n^{o(d/({ε)})}-time PTAS for larger values of d. In this work, we show that the running times of the best-known PTAS cannot be improved up to a polylogarithmic factor assuming the Exponential Time Hypothesis (ETH). Our techniques are based on a robust reduction from 2-CSP, which embeds 2-CSP constraints into a desired number of dimensions. Then, using a recent result of [Bafna Karthik and Minzer, STOC'25], we succeed in exhibiting tight trade-off between d and {ε} for all regimes of the parameters assuming d is sufficiently large. Informally, our result also shows that under ETH, for any function f there is no f(d/({ε)}) ⋅ n^{õ(d/({ε)})}-time (1-{ε})-approximation for d-dimensional knapsack, where n is the number of items and õ hides polylogarithmic factors in d/({ε)}.

Cite as

Ilan Doron-Arad, Ariel Kulik, and Pasin Manurangsi. On the PTAS Complexity of Multidimensional Knapsack. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 50:1-50:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{doronarad_et_al:LIPIcs.ITCS.2026.50,
  author =	{Doron-Arad, Ilan and Kulik, Ariel and Manurangsi, Pasin},
  title =	{{On the PTAS Complexity of Multidimensional Knapsack}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{50:1--50:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.50},
  URN =		{urn:nbn:de:0030-drops-253377},
  doi =		{10.4230/LIPIcs.ITCS.2026.50},
  annote =	{Keywords: d-dimensional Knapsack, Multidimensional Knapsack, PTAS, CSP}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.51

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems

Authors: Shaddin Dughmi, Yusuf Hakan Kalayci, and Xinyu Liu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

When uncertainty meets costly information gathering, a fundamental question emerges: which data points should we probe to unlock near-optimal solutions? Sparsification of stochastic packing problems addresses this trade-off. The existing notions of sparsification measure the level of sparsity, called degree, as the ratio of queried items to the optimal solution size. While effective for matching and matroid-type problems with uniform structures, this cardinality-based approach fails for knapsack-type constraints where feasible sets exhibit dramatic structural variation. We introduce a polyhedral sparsification framework that measures the degree as the smallest scalar needed to embed the query set within a scaled feasibility polytope, naturally capturing redundancy without relying on cardinality. Our main contribution establishes that knapsack, multiple knapsack, and generalized assignment problems admit (1-ε)-approximate sparsifiers with degree polynomial in 1/p and 1/ε - where p denotes the independent activation probability of each element - remarkably independent of problem dimensions. The key insight involves grouping items with similar weights and deploying a charging argument: when our query set misses an optimal item, we either substitute it directly with a queried item from the same group or leverage that group’s excess contribution to compensate for the loss. This reveals an intriguing complexity-theoretic separation - while the multiple knapsack problem lacks an FPTAS and generalized assignment is APX-hard, their sparsification counterparts admit efficient (1-ε)-approximation algorithms that identify polynomial degree query sets. Finally, we raise an open question: can such sparsification extend to general integer linear programs with degree independent of problem dimensions?

Cite as

Shaddin Dughmi, Yusuf Hakan Kalayci, and Xinyu Liu. Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 51:1-51:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dughmi_et_al:LIPIcs.ITCS.2026.51,
  author =	{Dughmi, Shaddin and Kalayci, Yusuf Hakan and Liu, Xinyu},
  title =	{{Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{51:1--51:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.51},
  URN =		{urn:nbn:de:0030-drops-253386},
  doi =		{10.4230/LIPIcs.ITCS.2026.51},
  annote =	{Keywords: Packing Problems, Assignment Problems, Stochastic Selection, Sparsification}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.98

Weighted Chairman Assignment and Flow-Time Scheduling

Authors: Siyue Liu and Victor Reis

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Given positive integers m, n, a fractional assignment x ∈ [0,1]^{m × n} and weights d ∈ ℝⁿ_{> 0}, we show that there exists an assignment y ∈ {0,1}^{m × n} so that for every i ∈ [m] and t ∈ [n], |∑_{j ∈ [t]} d_j (x_{ij} - y_{ij})| < max_{j ∈ [n]} d_j. This generalizes a result of Tijdeman (1973) on the unweighted version, known as the chairman assignment problem. This also confirms a special case of the single-source unsplittable flow conjecture with arc-wise lower and upper bounds due to Morell and Skutella (IPCO 2020). As an application, we consider a scheduling problem where jobs have release times and machines have closing times, and a job can only be scheduled on a machine if it is released before the machine closes. We give a 3-approximation algorithm for maximum flow-time minimization.

Cite as

Siyue Liu and Victor Reis. Weighted Chairman Assignment and Flow-Time Scheduling. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 98:1-98:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ITCS.2026.98,
  author =	{Liu, Siyue and Reis, Victor},
  title =	{{Weighted Chairman Assignment and Flow-Time Scheduling}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{98:1--98:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.98},
  URN =		{urn:nbn:de:0030-drops-253858},
  doi =		{10.4230/LIPIcs.ITCS.2026.98},
  annote =	{Keywords: prefix discrepancy, flow-time scheduling, unsplittable flow}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.3

Linear Matroid Intersection Is in Catalytic Logspace

Authors: Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks you to find a common independent set of maximum size. The deep interest in linear matroid intersection is due to the fact that it generalises many classical problems in theoretical computer science, such as bipartite matching, edge disjoint spanning trees, rainbow spanning tree, and many more. We study this problem in the model of catalytic computation: space-bounded machines are granted access to catalytic space, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Although linear matroid intersection has had a polynomial time algorithm for over 50 years, it remains an important open problem to show that linear matroid intersection belongs to any well studied subclass of {P}. We address this problem for the class catalytic logspace (CL) with a polynomial time bound (CLP). Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class CLP ⊆ {P}. This was the first subclass of {P} shown to contain bipartite matching, and additionally the first problem outside TC¹ shown to be contained in CL. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in CLP.

Cite as

Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra. Linear Matroid Intersection Is in Catalytic Logspace. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwala_et_al:LIPIcs.ITCS.2026.3,
  author =	{Agarwala, Aryan and Alekseev, Yaroslav and Vinciguerra, Antoine},
  title =	{{Linear Matroid Intersection Is in Catalytic Logspace}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{3:1--3:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.3},
  URN =		{urn:nbn:de:0030-drops-252908},
  doi =		{10.4230/LIPIcs.ITCS.2026.3},
  annote =	{Keywords: Catalytic Computing, Computational Complexity, Matroid Theory, Algorithms}
}

75 Search Results for "Shmoys, David"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message