21 Search Results for "Verschae, José"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.142
Combinatorial Perpetual Scheduling: Existence and Computation of Low-Height Schedules

Authors: Mirabel Mendoza-Cadena, Arturo Merino, Mads Anker Nielsen, and Kevin Schewior

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

Abstract
This paper considers a framework for combinatorial variants of perpetual-scheduling problems. Given an independence system (E,ℐ), a schedule consists of an independent set I_t ∈ ℐ for every time step t ∈ ℕ, with the objective of fulfilling frequency requirements on the occurrence of elements in E. We focus specifically on combinatorial bamboo garden trimming, where elements accumulate height at growth rates g(e) for e ∈ E and are reset to zero when scheduled, with the goal of minimizing the maximum height attained by any element. We assume that g is normalized so that it is a convex combination of the incidence vectors of ℐ. Using the integrality of the matroid-intersection polytope, we prove that, when (E,ℐ) is a matroid, it is possible to guarantee a maximum height of at most 2, which is optimal. We complement this existential result with efficient algorithms for specific matroid classes, achieving a maximum height of 2 for uniform and partition matroids, and 4 for graphic and laminar matroids. In contrast, we show that for general independence systems, the optimal guaranteed height is Θ(log |E|) and can be achieved by an efficient algorithm. For combinatorial pinwheel scheduling, where each element e ∈ E needs to occur in the schedule at least every a_e ∈ ℕ time steps, our results imply bounds on the density sufficient for schedulability.
Cite as

Mirabel Mendoza-Cadena, Arturo Merino, Mads Anker Nielsen, and Kevin Schewior. Combinatorial Perpetual Scheduling: Existence and Computation of Low-Height Schedules. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 142:1-142:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mendozacadena_et_al:LIPIcs.ICALP.2026.142,
  author =	{Mendoza-Cadena, Mirabel and Merino, Arturo and Nielsen, Mads Anker and Schewior, Kevin},
  title =	{{Combinatorial Perpetual Scheduling: Existence and Computation of Low-Height Schedules}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{142:1--142: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.142},
  URN =		{urn:nbn:de:0030-drops-265319},
  doi =		{10.4230/LIPIcs.ICALP.2026.142},
  annote =	{Keywords: Perpetual Scheduling, Matroids, Bamboo Garden Trimming, Pinwheel}
}
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.STACS.2026.27
The Communication Complexity of Combinatorial Auctions in Graphs

Authors: George Christodoulou, Elias Koutsoupias, Annamária Kovács, and Ioannis Vlachos

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

Abstract
We study truthful and non-truthful protocols for combinatorial auctions in which every item can be allocated to one of two agents (multigraphs), or more generally to a fixed number of agents (hypergraphs). We show some tight - both positive and impossibility - results for the communication complexity of approximating the optimal social welfare for general monotone, subadditive, or XOS valuations.
Cite as

George Christodoulou, Elias Koutsoupias, Annamária Kovács, and Ioannis Vlachos. The Communication Complexity of Combinatorial Auctions in Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.STACS.2026.27,
  author =	{Christodoulou, George and Koutsoupias, Elias and Kov\'{a}cs, Annam\'{a}ria and Vlachos, Ioannis},
  title =	{{The Communication Complexity of Combinatorial Auctions in Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{27:1--27: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.27},
  URN =		{urn:nbn:de:0030-drops-255163},
  doi =		{10.4230/LIPIcs.STACS.2026.27},
  annote =	{Keywords: Auctions, Communication Complexity, Mechanism Design, Graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.48
The Support of Bin Packing Is Exponential

Authors: Klaus Jansen, Lis Pirotton, and Malte Tutas

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Consider the classical Bin Packing problem with d different item sizes s_i and amounts of items a_i. The support of a Bin Packing solution is the number of differently filled bins. In this work, we show that the lower bound on the support of this problem is 2^Ω(d). Our lower bound matches the upper bound of 2^d given by Eisenbrand and Shmonin [Oper.Research Letters '06] up to a constant factor. This result has direct implications for the time complexity of several Bin Packing algorithms, such as Goemans and Rothvoss [SODA '14], Jansen and Klein [SODA '17] and Jansen and Solis-Oba [IPCO '10]. To achieve our main result, we develop a technique to aggregate equality constrained ILPs with many constraints into an equivalent ILP with one constraint. Our technique contrasts existing aggregation techniques as we manage to integrate upper bounds on variables into the resulting constraint. We believe this technique can be useful for solving general ILPs or the d-dimensional knapsack problem.
Cite as

Klaus Jansen, Lis Pirotton, and Malte Tutas. The Support of Bin Packing Is Exponential. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ESA.2025.48,
  author =	{Jansen, Klaus and Pirotton, Lis and Tutas, Malte},
  title =	{{The Support of Bin Packing Is Exponential}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.48},
  URN =		{urn:nbn:de:0030-drops-245167},
  doi =		{10.4230/LIPIcs.ESA.2025.48},
  annote =	{Keywords: Bin Packing, Integer Programming, Support}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.25
An Efficient Polynomial Time Approximation Scheme for Minimizing the Total Weighted Completion Time on Uniformly Related Machines

Authors: Leah Epstein and Asaf Levin

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We study a classic scheduling problem on uniformly related machines for which we show an efficient polynomial time approximation scheme (EPTAS), where an EPTAS is a fast and practical approximation scheme. For a desired approximation ratio of 1+ε for ε > 0, the running time of an EPTAS is a function of ε multiplied by a polynomial function of the input length. New methods and techniques are essential in developing such improved approximation schemes, and their design is a primary goal of this research agenda. We present an EPTAS for the scheduling problem of a set of jobs on uniformly related machines so as to minimize the total weighted completion time. The problem is NP-hard in the strong sense, and therefore an EPTAS is the best possible approximation scheme for the problem, unless P=NP. Prior to our work, only a PTAS was known for the problem, while an EPTAS was known only for the special case of identical machines.
Cite as

Leah Epstein and Asaf Levin. An Efficient Polynomial Time Approximation Scheme for Minimizing the Total Weighted Completion Time on Uniformly Related Machines. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 25:1-25:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{epstein_et_al:LIPIcs.WADS.2025.25,
  author =	{Epstein, Leah and Levin, Asaf},
  title =	{{An Efficient Polynomial Time Approximation Scheme for Minimizing the Total Weighted Completion Time on Uniformly Related Machines}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{25:1--25:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.25},
  URN =		{urn:nbn:de:0030-drops-242564},
  doi =		{10.4230/LIPIcs.WADS.2025.25},
  annote =	{Keywords: Scheduling algorithms, Approximation schemes, Min-sum objective}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.41
Randomized Binary and Tree Search Under Pressure

Authors: Agustín Caracci, Christoph Dürr, and José Verschae

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study a generalized binary search problem on the line and general trees. On the line (e.g., a sorted array), binary search finds a target node in O(log n) queries in the worst case, where n is the number of nodes. In time-constrained applications, we might only have time to perform a sub-logarithmic number of queries. In this case, it is impossible to guarantee that the target will be found regardless of its position. Our main result is the construction of a randomized strategy that maximizes the minimum (over the target’s position) probability of finding the target. Such a strategy provides a natural solution when there is no a priori (stochastic) information about the target’s position. As with regular binary search, we can find and run the strategy in O(log n) time (and using only O(log n) random bits). Our construction is obtained by reinterpreting the problem as a two-player zero-sum game and exploiting an underlying number theoretical structure. For the more general case on trees, querying an edge returns the edge’s endpoint closest to the target. Given a bound k on the number of queries, we quantify a the-less-queries-the-better approach by defining a seeker’s profit p depending on the number of queries needed to locate the hider. For the linear programming formulation of the corresponding zero-sum game, we show that computing the best response for the hider (that is, the separation problem of the underlying dual LP) can be done in time O(n² 2^{2k}), where n is the size of the tree. This result allows us to compute a Nash equilibrium in polynomial time whenever k = O(log n). In contrast, computing the best response for the hider is NP-hard in general.
Cite as

Agustín Caracci, Christoph Dürr, and José Verschae. Randomized Binary and Tree Search Under Pressure. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{caracci_et_al:LIPIcs.ICALP.2025.41,
  author =	{Caracci, Agust{\'\i}n and D\"{u}rr, Christoph and Verschae, Jos\'{e}},
  title =	{{Randomized Binary and Tree Search Under Pressure}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{41:1--41:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.41},
  URN =		{urn:nbn:de:0030-drops-234181},
  doi =		{10.4230/LIPIcs.ICALP.2025.41},
  annote =	{Keywords: Binary Search, Search Trees on Trees, Nash Equilibrium}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.127
Cost Preserving Dependent Rounding for Allocation Problems

Authors: Lars Rohwedder, Arman Rouhani, and Leo Wennmann

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We present a dependent randomized rounding scheme, which rounds fractional solutions to integral solutions satisfying certain hard constraints on the output while preserving Chernoff-like concentration properties. In contrast to previous dependent rounding schemes, our algorithm guarantees that the cost of the rounded integral solution does not exceed that of the fractional solution. Our algorithm works for a class of assignment problems with restrictions similar to those of prior works. In a non-trivial combination of our general result with a classical approach from Shmoys and Tardos [Math. Programm.'93] and more recent linear programming techniques developed for the restricted assignment variant by Bansal, Sviridenko [STOC'06] and Davies, Rothvoss, Zhang [SODA'20], we derive a O(log n)-approximation algorithm for the Budgeted Santa Claus Problem. In this new variant, the goal is to allocate resources with different values to players, maximizing the minimum value a player receives, and satisfying a budget constraint on player-resource allocation costs.
Cite as

Lars Rohwedder, Arman Rouhani, and Leo Wennmann. Cost Preserving Dependent Rounding for Allocation Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 127:1-127:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rohwedder_et_al:LIPIcs.ICALP.2025.127,
  author =	{Rohwedder, Lars and Rouhani, Arman and Wennmann, Leo},
  title =	{{Cost Preserving Dependent Rounding for Allocation Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{127:1--127:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.127},
  URN =		{urn:nbn:de:0030-drops-235049},
  doi =		{10.4230/LIPIcs.ICALP.2025.127},
  annote =	{Keywords: Matching, Randomized Rounding, Santa Claus, Approximation Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.126
ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines

Authors: Lars Rohwedder

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Given n jobs with processing times p₁,...,p_n ∈ ℕ and m ≤ n machines with speeds s₁,...,s_m ∈ ℕ our goal is to allocate the jobs to machines minimizing the makespan. We present an algorithm that solves the problem in time p_{max}^{O(d)} ⋅ n, where p_{max} is the maximum processing time and d ≤ p_{max} is the number of distinct processing times. This is essentially the best possible due to a lower bound based on the exponential time hypothesis (ETH). Our result improves over prior works that had a quadratic term in d in the exponent and answers an open question by Koutecký and Zink. The algorithm is based on integer programming techniques combined with novel ideas from modular arithmetic. It can also be implemented efficiently for the more compact high-multiplicity instance encoding.
Cite as

Lars Rohwedder. ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 126:1-126:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rohwedder:LIPIcs.ICALP.2025.126,
  author =	{Rohwedder, Lars},
  title =	{{ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{126:1--126:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.126},
  URN =		{urn:nbn:de:0030-drops-235037},
  doi =		{10.4230/LIPIcs.ICALP.2025.126},
  annote =	{Keywords: Scheduling, Integer Programming}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.59
Online Matching with Delays and Size-Based Costs

Authors: Yasushi Kawase and Tomohiro Nakayoshi

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In this paper, we introduce the problem of Online Matching with Delays and Size-based Costs (OMDSC). The OMDSC problem involves m requests arriving online. At any time, a group can be formed by matching any number of requests that have been received but remain unmatched. The cost associated with each group is determined by the waiting time for each request within the group and size-dependent cost. The size-dependent cost is specified by a penalty function. Our goal is to partition all the incoming requests into multiple groups while minimizing the total associated cost. This problem is an extension of the TCP acknowledgment problem proposed by Dooly et al. (J. ACM, 2001). It generalizes the cost model for sending acknowledgments. This study reveals the competitive ratios for a fundamental case, in which the penalty function takes only values of either 0 or 1. We classify such penalty functions into three distinct cases: (i) a fixed penalty of 1 regardless of the group size, (ii) a penalty of 0 if and only if the group size is a multiple of a specific integer k, and (iii) other situations. The problem in case (i) is equivalent to the TCP acknowledgment problem, for which Dooly et al. proposed a 2-competitive algorithm. For case (ii), we first show that natural algorithms that match all remaining requests are Ω(√k)-competitive. We then propose an O(log k / log log k)-competitive deterministic algorithm by carefully managing the match size and timing, and prove its optimality. For any penalty function in case (iii), we demonstrate the non-existence of a competitive online algorithm. Additionally, we discuss competitive ratios for other typical penalty functions that are not restricted to take values of 0 or 1.
Cite as

Yasushi Kawase and Tomohiro Nakayoshi. Online Matching with Delays and Size-Based Costs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.STACS.2025.59,
  author =	{Kawase, Yasushi and Nakayoshi, Tomohiro},
  title =	{{Online Matching with Delays and Size-Based Costs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{59:1--59:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.59},
  URN =		{urn:nbn:de:0030-drops-228846},
  doi =		{10.4230/LIPIcs.STACS.2025.59},
  annote =	{Keywords: Online matching, competitive analysis, delayed service}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.83
Fine-Grained Equivalence for Problems Related to Integer Linear Programming

Authors: Lars Rohwedder and Karol Węgrzycki

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
Integer Linear Programming with n binary variables and m many 0/1-constraints can be solved in time 2^Õ(m²) poly(n) and it is open whether the dependence on m is optimal. Several seemingly unrelated problems, which include variants of Closest String, Discrepancy Minimization, Set Cover, and Set Packing, can be modelled as Integer Linear Programming with 0/1 constraints to obtain algorithms with the same running time for a natural parameter m in each of the problems. Our main result establishes through fine-grained reductions that these problems are equivalent, meaning that a 2^O(m^{2-ε}) poly(n) algorithm with ε > 0 for one of them implies such an algorithm for all of them. In the setting above, one can alternatively obtain an n^O(m) time algorithm for Integer Linear Programming using a straightforward dynamic programming approach, which can be more efficient if n is relatively small (e.g., subexponential in m). We show that this can be improved to {n'}^O(m) + O(nm), where n' is the number of distinct (i.e., non-symmetric) variables. This dominates both of the aforementioned running times.
Cite as

Lars Rohwedder and Karol Węgrzycki. Fine-Grained Equivalence for Problems Related to Integer Linear Programming. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 83:1-83:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rohwedder_et_al:LIPIcs.ITCS.2025.83,
  author =	{Rohwedder, Lars and W\k{e}grzycki, Karol},
  title =	{{Fine-Grained Equivalence for Problems Related to Integer Linear Programming}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{83:1--83:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.83},
  URN =		{urn:nbn:de:0030-drops-227114},
  doi =		{10.4230/LIPIcs.ITCS.2025.83},
  annote =	{Keywords: Integer Programming, Fine-Grained Complexity, Fixed-Parameter Tractable Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.74
Sublinear Metric Steiner Tree via Improved Bounds for Set Cover

Authors: Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, and Ali Vakilian

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study the metric Steiner tree problem in the sublinear query model. In this problem, for a set of n points V in a metric space given to us by means of query access to an n× n matrix w, and a set of terminals T ⊆ V, the goal is to find the minimum-weight subset of the edges that connects all the terminal vertices. Recently, Chen, Khanna and Tan [SODA'23] gave an algorithm that uses Õ(n^{13/7}) queries and outputs a (2-η)-estimate of the metric Steiner tree weight, where η > 0 is a universal constant. A key component in their algorithm is a sublinear algorithm for a particular set cover problem where, given a set system (𝒰, ℱ), the goal is to provide a multiplicative-additive estimate for |𝒰|-SC(𝒰, ℱ). Here 𝒰 is the set of elements, ℱ is the collection of sets, and SC(𝒰, ℱ) denotes the optimal set cover size of (𝒰, ℱ). In particular, their algorithm returns a (1/4, ε⋅|𝒰|)-multiplicative-additive estimate for this set cover problem using Õ(|ℱ|^{7/4}) membership oracle queries (querying whether a set S ∈ 𝒮 contains an element e ∈ 𝒰), where ε is a fixed constant. In this work, we improve the query complexity of (2-η)-estimating the metric Steiner tree weight to Õ(n^{5/3}) by showing a (1/2, ε⋅|𝒰|)-estimate for the above set cover problem using Õ(|ℱ|^{5/3}) membership queries. To design our set cover algorithm, we estimate the size of a random greedy maximal matching for an auxiliary multigraph that the algorithm constructs implicitly, without access to its adjacency list or matrix. Previous analyses of random greedy maximal matching have focused on simple graphs, assuming access to their adjacency list or matrix. To address this, we extend the analysis of Behnezhad [FOCS'21] of random greedy maximal matching on simple graphs to multigraphs, and prove additional properties that may be of independent interest.
Cite as

Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, and Ali Vakilian. Sublinear Metric Steiner Tree via Improved Bounds for Set Cover. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 74:1-74:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mahabadi_et_al:LIPIcs.ITCS.2025.74,
  author =	{Mahabadi, Sepideh and Roghani, Mohammad and Tarnawski, Jakub and Vakilian, Ali},
  title =	{{Sublinear Metric Steiner Tree via Improved Bounds for Set Cover}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{74:1--74:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.74},
  URN =		{urn:nbn:de:0030-drops-227029},
  doi =		{10.4230/LIPIcs.ITCS.2025.74},
  annote =	{Keywords: Sublinear Algorithms, Steiner Tree, Set Cover, Maximum Matching, Approximation Algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.42
Additive Approximation Schemes for Load Balancing Problems

Authors: Moritz Buchem, Lars Rohwedder, Tjark Vredeveld, and Andreas Wiese

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines. Additive approximation schemes compute a solution with an absolute error in the objective of at most ε h for some suitable parameter h and any given ε > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For these settings we present additive approximation schemes for h = p_{max}, the maximum processing time of the jobs. Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slot-MILP. While it has a linear number of integral variables, we identify structural properties of (near-)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a local-search algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most ε⋅ p_{max}.
Cite as

Moritz Buchem, Lars Rohwedder, Tjark Vredeveld, and Andreas Wiese. Additive Approximation Schemes for Load Balancing Problems. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{buchem_et_al:LIPIcs.ICALP.2021.42,
  author =	{Buchem, Moritz and Rohwedder, Lars and Vredeveld, Tjark and Wiese, Andreas},
  title =	{{Additive Approximation Schemes for Load Balancing Problems}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{42:1--42:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.42},
  URN =		{urn:nbn:de:0030-drops-141116},
  doi =		{10.4230/LIPIcs.ICALP.2021.42},
  annote =	{Keywords: Load balancing, Approximation schemes, Parallel machine scheduling}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.46
A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems

Authors: Andrés Fielbaum, Ignacio Morales, and José Verschae

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Obtaining strong linear relaxations of capacitated covering problems constitute a significant technical challenge even for simple settings. For one of the most basic cases, the Knapsack-Cover (Min-Knapsack) problem, the relaxation based on knapsack-cover inequalities has an integrality gap of 2. These inequalities are exploited in more general problems, many of which admit primal-dual approximation algorithms. Inspired by problems from power and transport systems, we introduce a general setting in which items can be taken fractionally to cover a given demand. The cost incurred by an item is given by an arbitrary non-decreasing function of the chosen fraction. We generalize the knapsack-cover inequalities to this setting an use them to obtain a (2+ε)-approximate primal-dual algorithm. Our procedure has a natural interpretation as a bucket-filling algorithm which effectively overcomes the difficulties implied by having different slopes in the cost functions. More precisely, when some superior segment of an item presents a low slope, it helps to increase the priority of inferior segments. We also present a rounding algorithm with an approximation guarantee of 2. We generalize our algorithm to the Unsplittable Flow-Cover problem on a line, also for the setting of fractional items with non-linear costs. For this problem we obtain a (4+ε)-approximation algorithm in polynomial time, almost matching the 4-approximation algorithm known for the classical setting.
Cite as

Andrés Fielbaum, Ignacio Morales, and José Verschae. A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fielbaum_et_al:LIPIcs.ICALP.2020.46,
  author =	{Fielbaum, Andr\'{e}s and Morales, Ignacio and Verschae, Jos\'{e}},
  title =	{{A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.46},
  URN =		{urn:nbn:de:0030-drops-124531},
  doi =		{10.4230/LIPIcs.ICALP.2020.46},
  annote =	{Keywords: Knapsack-Cover Inequalities, Non-Linear Knapsack-Cover, Primal-Dual, Water-Filling Algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.82
Maintaining Perfect Matchings at Low Cost

Authors: Jannik Matuschke, Ulrike Schmidt-Kraepelin, and José Verschae

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
The min-cost matching problem suffers from being very sensitive to small changes of the input. Even in a simple setting, e.g., when the costs come from the metric on the line, adding two nodes to the input might change the optimal solution completely. On the other hand, one expects that small changes in the input should incur only small changes on the constructed solutions, measured as the number of modified edges. We introduce a two-stage model where we study the trade-off between quality and robustness of solutions. In the first stage we are given a set of nodes in a metric space and we must compute a perfect matching. In the second stage 2k new nodes appear and we must adapt the solution to a perfect matching for the new instance. We say that an algorithm is (alpha,beta)-robust if the solutions constructed in both stages are alpha-approximate with respect to min-cost perfect matchings, and if the number of edges deleted from the first stage matching is at most beta k. Hence, alpha measures the quality of the algorithm and beta its robustness. In this setting we aim to balance both measures by deriving algorithms for constant alpha and beta. We show that there exists an algorithm that is (3,1)-robust for any metric if one knows the number 2k of arriving nodes in advance. For the case that k is unknown the situation is significantly more involved. We study this setting under the metric on the line and devise a (10,2)-robust algorithm that constructs a solution with a recursive structure that carefully balances cost and redundancy.
Cite as

Jannik Matuschke, Ulrike Schmidt-Kraepelin, and José Verschae. Maintaining Perfect Matchings at Low Cost. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 82:1-82:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{matuschke_et_al:LIPIcs.ICALP.2019.82,
  author =	{Matuschke, Jannik and Schmidt-Kraepelin, Ulrike and Verschae, Jos\'{e}},
  title =	{{Maintaining Perfect Matchings at Low Cost}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{82:1--82:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.82},
  URN =		{urn:nbn:de:0030-drops-106582},
  doi =		{10.4230/LIPIcs.ICALP.2019.82},
  annote =	{Keywords: matchings, robust optimization, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.32
Symmetry Exploitation for Online Machine Covering with Bounded Migration

Authors: Waldo Gálvez, José A. Soto, and José Verschae

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Online models that allow recourse are highly effective in situations where classical models are too pessimistic. One such problem is the online machine covering problem on identical machines. In this setting, jobs arrive one by one and must be assigned to machines with the objective of maximizing the minimum machine load. When a job arrives, we are allowed to reassign some jobs as long as their total size is (at most) proportional to the processing time of the arriving job. The proportionality constant is called the migration factor of the algorithm. By rounding the processing times, which yields useful structural properties for online packing and covering problems, we design first a simple (1.7 + epsilon)-competitive algorithm using a migration factor of O(1/epsilon) which maintains at every arrival a locally optimal solution with respect to the Jump neighborhood. After that, we present as our main contribution a more involved (4/3+epsilon)-competitive algorithm using a migration factor of O~(1/epsilon^3). At every arrival, we run an adaptation of the Largest Processing Time first (LPT) algorithm. Since the new job can cause a complete change of the assignment of smaller jobs in both cases, a low migration factor is achieved by carefully exploiting the highly symmetric structure obtained by the rounding procedure.
Cite as

Waldo Gálvez, José A. Soto, and José Verschae. Symmetry Exploitation for Online Machine Covering with Bounded Migration. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{galvez_et_al:LIPIcs.ESA.2018.32,
  author =	{G\'{a}lvez, Waldo and Soto, Jos\'{e} A. and Verschae, Jos\'{e}},
  title =	{{Symmetry Exploitation for Online Machine Covering with Bounded Migration}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.32},
  URN =		{urn:nbn:de:0030-drops-94959},
  doi =		{10.4230/LIPIcs.ESA.2018.32},
  annote =	{Keywords: Machine Covering, Bounded Migration, Online, Scheduling, LPT}
}
  • Refine by Type
  • 21 Document/PDF
  • 10 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 8 2025
  • 1 2021
  • 1 2020
  • 1 2019
  • Show More...

  • Refine by Author
  • 8 Verschae, José
  • 4 Rohwedder, Lars
  • 3 Wiese, Andreas
  • 2 Jansen, Klaus
  • 2 Matuschke, Jannik
  • Show More...

  • Refine by Series/Journal
  • 19 LIPIcs
  • 2 DagSemProc

  • Refine by Classification
  • 4 Theory of computation → Scheduling algorithms
  • 2 Theory of computation → Online algorithms
  • 2 Theory of computation → Packing and covering problems
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Discrete optimization
  • Show More...

  • Refine by Keyword
  • 3 Integer Programming
  • 2 Approximation Algorithms
  • 2 Approximation schemes
  • 2 Scheduling
  • 2 approximation algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact