14 Search Results for "Calinescu, Gruia"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.104
Dimension-Free Correlated Sampling for the Hypersimplex

Authors: Joseph (Seffi) Naor, Nitya Raju, Abhishek Shetty, Aravind Srinivasan, Renata Valieva, and David Wajc

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

Abstract
Sampling from multiple distributions so as to maximize overlap has been studied by statisticians since the 1950s. Since the 2000s, such correlated sampling from the probability simplex has been a powerful building block in disparate areas of theoretical computer science. We study a generalization of this problem to sampling sets from given vectors in the hypersimplex, i.e., outputting sets of size (at most) k ∈ [n], while maximizing the overlap of the sampled sets. Specifically, the expected difference between two output sets should be at most α times their input vectors' 𝓁₁ distance. A value of α = O(log n) is known to be achievable, due to Chen et al. (ICALP'17). We improve this factor to O(log k), independent of the ambient dimension n. Our algorithm satisfies other desirable properties, including (up to a log^* n factor) input-sparsity sampling time, logarithmic parallel depth and dynamic update time, as well as preservation of submodular objectives. Anticipating broader use of correlated sampling algorithms for the hypersimplex, we present applications of our algorithm to online paging, offline approximation of metric multi-labeling, and swift multi-scenario submodular welfare approximating reallocation.
Cite as

Joseph (Seffi) Naor, Nitya Raju, Abhishek Shetty, Aravind Srinivasan, Renata Valieva, and David Wajc. Dimension-Free Correlated Sampling for the Hypersimplex. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 104:1-104:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{naor_et_al:LIPIcs.ITCS.2026.104,
  author =	{Naor, Joseph (Seffi) and Raju, Nitya and Shetty, Abhishek and Srinivasan, Aravind and Valieva, Renata and Wajc, David},
  title =	{{Dimension-Free Correlated Sampling for the Hypersimplex}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{104:1--104:20},
  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.104},
  URN =		{urn:nbn:de:0030-drops-253918},
  doi =		{10.4230/LIPIcs.ITCS.2026.104},
  annote =	{Keywords: Correlated Rounding, Dependent Rounding}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.105
Fixed-Parameter Tractable Submodular Maximization over a Matroid

Authors: Shamisa Nematollahi, Adrian Vladu, and Junyao Zhao

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

Abstract
In this paper, we design fixed-parameter tractable (FPT) algorithms for (non-monotone) submodular maximization subject to a matroid constraint, where the matroid rank r is treated as a fixed parameter that is independent of the total number of elements n. We provide two FPT algorithms: one for the offline setting and another for the random-order streaming setting. Our streaming algorithm achieves a 1/2-ε approximation using Õ(r/poly(ε)) memory, while our offline algorithm obtains a 1-(1)/(e)-ε approximation with n⋅ 2^{Õ(r/poly(ε))} runtime and Õ(r/poly(ε)) memory. Both approximation factors are near-optimal in their respective settings, given existing hardness results. In particular, our offline algorithm demonstrates that - unlike in the polynomial-time regime - there is essentially no separation between monotone and non-monotone submodular maximization under a matroid constraint in the FPT framework.
Cite as

Shamisa Nematollahi, Adrian Vladu, and Junyao Zhao. Fixed-Parameter Tractable Submodular Maximization over a Matroid. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 105:1-105:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{nematollahi_et_al:LIPIcs.ITCS.2026.105,
  author =	{Nematollahi, Shamisa and Vladu, Adrian and Zhao, Junyao},
  title =	{{Fixed-Parameter Tractable Submodular Maximization over a Matroid}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{105:1--105: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.105},
  URN =		{urn:nbn:de:0030-drops-253924},
  doi =		{10.4230/LIPIcs.ITCS.2026.105},
  annote =	{Keywords: Submodular maximization, matroids, parameterized complexity, streaming algorithms}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.25
Covering a Few Submodular Constraints and Applications

Authors: Tanvi Bajpai, Chandra Chekuri, and Pooja Kulkarni

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We consider the problem of covering multiple submodular constraints. Given a finite ground set N, a cost function c: N → ℝ_+, r monotone submodular functions f_1,f_2,…,f_r over N and requirements b_1,b_2,…,b_r the goal is to find a minimum cost subset S ⊆ N such that f_i(S) ≥ b_i for 1 ≤ i ≤ r. When r = 1 this is the well-known Submodular Set Cover problem. Previous work [Chekuri et al., 2022] considered the setting when r is large and developed bi-criteria approximation algorithms, and approximation algorithms for the important special case when each f_i is a weighted coverage function. These are fairly general models and capture several concrete and interesting problems as special cases. The approximation ratios for these problem are at least Ω(log r) which is unavoidable when r is part of the input. In this paper, motivated by some recent applications, we consider the problem when r is a fixed constant and obtain two main results. When the f_i are weighted coverage functions from a deletion-closed set system we obtain a (1+ε)(e/(e-1))(1+β)-approximation where β is the approximation ratio for the underlying set cover instances via the natural LP. Second, for covering multiple submodular constraints we obtain a randomized bi-criteria approximation algorithm that for any given integer α ≥ 1 outputs a set S such that f_i(S) ≥ (1-1/e^α-ε)b_i for each i ∈ [r] and 𝔼[c(S)] ≤ (1+ε)α ⋅ OPT. These results show that one can obtain nearly as good an approximation for any fixed r as what one would achieve for r = 1. We also demonstrate applications of our results to implicit covering problems such as fair facility location.
Cite as

Tanvi Bajpai, Chandra Chekuri, and Pooja Kulkarni. Covering a Few Submodular Constraints and Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 25:1-25:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bajpai_et_al:LIPIcs.APPROX/RANDOM.2025.25,
  author =	{Bajpai, Tanvi and Chekuri, Chandra and Kulkarni, Pooja},
  title =	{{Covering a Few Submodular Constraints and Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{25:1--25:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.25},
  URN =		{urn:nbn:de:0030-drops-243917},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.25},
  annote =	{Keywords: covering, linear programming, rounding, fairness}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.2
Covering Simple Orthogonal Polygons with Rectangles

Authors: Aniket Basu Roy

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study the problem of Covering Orthogonal Polygons with Rectangles, focusing on three variants: covering the interior, the boundary, and the corners. While previous work provided constant-factor approximation algorithms for these problems, significant improvements had not been achieved for over two decades. The main contribution of this work is the development of a Polynomial Time Approximation Scheme (PTAS) for both the Boundary Cover and Corner Cover problems on simple polygons, using a local search algorithm. Our work advances the state of the art, improving upon the previous best-known 4-approximation for the Boundary Cover and 2-approximation for the Corner Cover problems. The technical core of our work lies in proving the existence of planar support graphs for certain geometric hypergraphs defined by the polygon and its containment-maximal rectangles. This structural insight enables the application of the local search framework to achieve the PTAS results. We also demonstrate the limitations of this approach by constructing instances where local search fails for the Interior Cover and certain dual problems, such as the Maximum Antirectangle and Hitting Set problems. Additionally, the methods yield a PTAS for a special case of the Discrete Independent Set problem for rectangles. These results not only settle longstanding open questions but also introduce new techniques that may be of independent interest within computational geometry.
Cite as

Aniket Basu Roy. Covering Simple Orthogonal Polygons with Rectangles. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{basuroy:LIPIcs.APPROX/RANDOM.2025.2,
  author =	{Basu Roy, Aniket},
  title =	{{Covering Simple Orthogonal Polygons with Rectangles}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.2},
  URN =		{urn:nbn:de:0030-drops-243686},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.2},
  annote =	{Keywords: Polygon Covering, Approximation Algorithms, Orthogonal Polygons, Rectangles, Local Search, Planar Supports}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.13
Max-Cut with Multiple Cardinality Constraints

Authors: Yury Makarychev, Madhusudhan Reddy Pittu, and Ali Vakilian

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study the classic Max-Cut problem under multiple cardinality constraints, which we refer to as the Constrained Max-Cut problem. Given a graph G = (V, E), a partition of the vertices into c disjoint parts V₁, …, V_c, and cardinality parameters k₁, …, k_c, the goal is to select a set S ⊆ V such that |S ∩ V_i| = k_i for each i ∈ [c], maximizing the total weight of edges crossing S (i.e., edges with exactly one endpoint in S). By designing an approximate kernel for Constrained Max-Cut and building on the correlation rounding technique of Raghavendra and Tan (2012), we present a (0.858 - ε)-approximation algorithm for the problem when c = O(1). The algorithm runs in time O(min{k/ε, n}^poly(c/ε) + poly(n)), where k = ∑_{i∈[c]} k_i and n = |V|. This improves upon the (1/2 + ε₀)-approximation of Feige and Langberg (2001) for Max-Cut_k (the special case when c = 1, k₁ = k), and generalizes the (0.858 - ε)-approximation of Raghavendra and Tan (2012), which only applies when min{k,n-k} = Ω(n) and does not handle multiple constraints. We also establish that, for general values of c, it is NP-hard to determine whether a feasible solution exists that cuts all edges. Finally, we present a 1/2-approximation algorithm for Max-Cut under an arbitrary matroid constraint.
Cite as

Yury Makarychev, Madhusudhan Reddy Pittu, and Ali Vakilian. Max-Cut with Multiple Cardinality Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{makarychev_et_al:LIPIcs.APPROX/RANDOM.2025.13,
  author =	{Makarychev, Yury and Pittu, Madhusudhan Reddy and Vakilian, Ali},
  title =	{{Max-Cut with Multiple Cardinality Constraints}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.13},
  URN =		{urn:nbn:de:0030-drops-243790},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.13},
  annote =	{Keywords: Maxcut, Semi-definite Programming, Sum of Squares Hierarchy}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.19
Dynamic Algorithms for Submodular Matching

Authors: Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh

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

Abstract
The Maximum Submodular Matching (MSM) problem is a generalization of the classical Maximum Weight Matching (MWM) problem. In this problem, given a monotone submodular function f: 2^E → ℝ^{≥ 0} defined over subsets of edges of a graph G(V, E), we are asked to return a matching whose submodular value is maximum among all matchings in graph G(V, E). In this paper, we consider this problem in a fully dynamic setting against an oblivious adversary. In this setting, we are given a sequence 𝒮 of insertions and deletions of edges of the underlying graph G(V, E), along with an oracle access to the monotone submodular function f. The goal is to maintain a matching M such that, at any time t of sequence 𝒮, its submodular value is a good approximation of the value of the optimal submodular matching while keeping the number of operations minimal. We develop the first dynamic algorithm for the submodular matching problem, in which we maintain a matching whose submodular value is within expected (8 + ε)-approximation of the optimal submodular matching at any time t of sequence 𝒮 using expected amortized poly(log n, 1/(ε)) update time. Our approach incorporates a range of novel techniques, notably the concept of Uniform Hierarchical Caches (UHC) data structure along with its invariants, which lead to the first algorithm for fully dynamic submodular matching and may be of independent interest for designing dynamic algorithms for other problems.
Cite as

Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. Dynamic Algorithms for Submodular Matching. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banihashem_et_al:LIPIcs.ICALP.2025.19,
  author =	{Banihashem, Kiarash and Biabani, Leyla and Goudarzi, Samira and Hajiaghayi, MohammadTaghi and Jabbarzade, Peyman and Monemizadeh, Morteza},
  title =	{{Dynamic Algorithms for Submodular Matching}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{19:1--19:21},
  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.19},
  URN =		{urn:nbn:de:0030-drops-233969},
  doi =		{10.4230/LIPIcs.ICALP.2025.19},
  annote =	{Keywords: Matching, Submodular, Dynamic, Polylogarithmic}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.50
New Results on a General Class of Minimum Norm Optimization Problems

Authors: Kuowen Chen, Jian Li, Yuval Rabani, and Yiran Zhang

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

Abstract
We study the general norm optimization for combinatorial problems, initiated by Chakrabarty and Swamy (STOC 2019). We propose a general formulation that captures a large class of combinatorial structures: we are given a set 𝒰 of n weighted elements and a family of feasible subsets ℱ. Each subset S ∈ ℱ is called a feasible solution/set of the problem. We denote the value vector by v = {v_i}_{i ∈ [n]}, where v_i ≥ 0 is the value of element i. For any subset S ⊆ 𝒰, we use v[S] to denote the n-dimensional vector {v_e⋅ 𝟏[e ∈ S]}_{e ∈ 𝒰} (i.e., we zero out all entries that are not in S). Let f: ℝⁿ → ℝ_+ be a symmetric monotone norm function. Our goal is to minimize the norm objective f(v[S]) over feasible subset S ∈ ℱ. The problem significantly generalizes the corresponding min-sum and min-max problems. We present a general equivalent reduction of the norm minimization problem to a multi-criteria optimization problem with logarithmic budget constraints, up to a constant approximation factor. Leveraging this reduction, we obtain constant factor approximation algorithms for the norm minimization versions of several covering problems, such as interval cover, multi-dimensional knapsack cover, and logarithmic factor approximation for set cover. We also study the norm minimization versions for perfect matching, s-t path and s-t cut. We show the natural linear programming relaxations for these problems have a large integrality gap. To complement the negative result, we show that, for perfect matching, it is possible to obtain a bi-criteria result: for any constant ε,δ > 0, we can find in polynomial time a nearly perfect matching (i.e., a matching that matches at least 1-ε proportion of vertices) and its cost is at most (8+δ) times of the optimum for perfect matching. Moreover, we establish the existence of a polynomial-time O(log log n)-approximation algorithm for the norm minimization variant of the s-t path problem. Specifically, our algorithm achieves an α-approximation with a time complexity of n^{O(log log n / α)}, where 9 ≤ α ≤ log log n.
Cite as

Kuowen Chen, Jian Li, Yuval Rabani, and Yiran Zhang. New Results on a General Class of Minimum Norm Optimization Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2025.50,
  author =	{Chen, Kuowen and Li, Jian and Rabani, Yuval and Zhang, Yiran},
  title =	{{New Results on a General Class of Minimum Norm Optimization Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{50:1--50: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.50},
  URN =		{urn:nbn:de:0030-drops-234276},
  doi =		{10.4230/LIPIcs.ICALP.2025.50},
  annote =	{Keywords: Approximation Algorithms, Minimum Norm Optimization, Linear Programming}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.44
A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots

Authors: Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We study a variant of the Coordinated Motion Planning problem on undirected graphs, referred to herein as the Coordinated Sliding-Motion Planning (CSMP) problem. In this variant, we are given an undirected graph G, k robots R₁,… ,R_k positioned on distinct vertices of G, p ≤ k distinct destination vertices for robots R₁,… ,R_p, and 𝓁 ∈ ℕ. The problem is to decide if there is a serial schedule of at most 𝓁 moves (i.e., of makespan 𝓁) such that at the end of the schedule each robot with a destination reaches it, where a robot’s move is a free path (unoccupied by any robots) from its current position to an unoccupied vertex. The problem is known to be NP-hard even on full grids. It has been studied in several contexts, including coin movement and reconfiguration problems, with respect to feasibility, complexity, and approximation. Geometric variants of the problem, in which congruent geometric-shape robots (e.g., unit disk/squares) slide or translate in the Euclidean plane, have also been studied extensively. We investigate the parameterized complexity of CSMP with respect to two parameters: the number k of robots and the makespan 𝓁. As our first result, we present a fixed-parameter algorithm for CSMP parameterized by k. For our second result, we present a fixed-parameter algorithm parameterized by 𝓁 for the special case of CSMP in which only a single robot has a destination and the graph is planar. A crucial new ingredient for both of our results is that the solution admits a succinct representation as a small labeled topological minor of the input graph.
Cite as

Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan. A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.SoCG.2025.44,
  author =	{Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ramanujan, M. S.},
  title =	{{A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.44},
  URN =		{urn:nbn:de:0030-drops-231966},
  doi =		{10.4230/LIPIcs.SoCG.2025.44},
  annote =	{Keywords: coordinated motion planning on graphs, parameterized complexity, topological minor testing, planar graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.18
Online Disjoint Set Covers: Randomization Is Not Necessary

Authors: Marcin Bienkowski, Jarosław Byrka, and Łukasz Jeż

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

Abstract
In the online disjoint set covers problem, the edges of a hypergraph are revealed online, and the goal is to partition them into a maximum number of disjoint set covers. That is, n nodes of a hypergraph are given at the beginning, and then a sequence of hyperedges (subsets of [n]) is presented to an algorithm. For each hyperedge, an online algorithm must assign a color (an integer). Once an input terminates, the gain of the algorithm is the number of colors that correspond to valid set covers (i.e., the union of hyperedges that have that color contains all n nodes). We present a deterministic online algorithm that is O(log² n)-competitive, exponentially improving on the previous bound of O(n) and matching the performance of the best randomized algorithm by Emek et al. [ESA 2019]. For color selection, our algorithm uses a novel potential function, which can be seen as an online counterpart of the derandomization method of conditional probabilities and pessimistic estimators. There are only a few cases where derandomization has been successfully used in the field of online algorithms. In contrast to previous approaches, our result extends to the following new challenges: (i) the potential function derandomizes not only the Chernoff bound, but also the coupon collector’s problem, (ii) the value of Opt of the maximization problem is not bounded a priori, and (iii) we do not produce a fractional solution first, but work directly on the input.
Cite as

Marcin Bienkowski, Jarosław Byrka, and Łukasz Jeż. Online Disjoint Set Covers: Randomization Is Not Necessary. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.STACS.2025.18,
  author =	{Bienkowski, Marcin and Byrka, Jaros{\l}aw and Je\.{z}, {\L}ukasz},
  title =	{{Online Disjoint Set Covers: Randomization Is Not Necessary}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{18:1--18:16},
  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.18},
  URN =		{urn:nbn:de:0030-drops-228433},
  doi =		{10.4230/LIPIcs.STACS.2025.18},
  annote =	{Keywords: Disjoint Set Covers, Derandomization, pessimistic Estimator, potential Function, online Algorithms, competitive Analysis}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.51
Parameterized Geometric Graph Modification with Disk Scaling

Authors: Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi

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

Abstract
The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph G and an integer k ∈ ℕ as input, the goal is to determine whether we can perform at most k operations on G to transform it into a graph belonging to a specified graph class ℱ. Typical operations are combinatorial and include vertex deletions and edge deletions, insertions, and contractions. However, in many real-world scenarios, when the input graph is constrained to be a geometric intersection graph, the modification of the graph is influenced by changes in the geometric properties of the underlying objects themselves, rather than by combinatorial modifications. It raises the question of whether vertex deletions or adjacency modifications are necessarily the most appropriate modification operations for studying modifications of geometric graphs. We propose the study of the disk intersection graph modification through the scaling of disks. This operation is typical in the realm of topology control but has not yet been explored in the context of Parameterized Complexity. We design parameterized algorithms and kernels for modifying to the most basic graph classes: edgeless, connected, and acyclic. Our technical contributions encompass a novel combination of linear programming, branching, and kernelization techniques, along with a fresh application of bidimensionality theory to analyze the area covered by disks, which may have broader applicability.
Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Parameterized Geometric Graph Modification with Disk Scaling. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ITCS.2025.51,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Parameterized Geometric Graph Modification with Disk Scaling}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{51:1--51:17},
  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.51},
  URN =		{urn:nbn:de:0030-drops-226795},
  doi =		{10.4230/LIPIcs.ITCS.2025.51},
  annote =	{Keywords: parameterized algorithms, kernelization, spreading points, distant representatives, unit disk packing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.37
Online Flexible Busy Time Scheduling on Heterogeneous Machines

Authors: Gruia Călinescu, Sami Davies, Samir Khuller, and Shirley Zhang

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We study the online busy time scheduling model on heterogeneous machines. In our setting, jobs with uniform length arrive online with a deadline that becomes known to the algorithm at the job’s arrival time. An algorithm has access to machines, each with different associated capacities and costs. The goal is to schedule jobs on machines by their deadline, so that the total cost incurred by the scheduling algorithm is minimized. While busy time scheduling has been well-studied, relatively little is known when machines are heterogeneous (i.e., have different costs and capacities), despite this natural theoretical generalization being the most practical model for clients using cloud computing services. We make significant progress in understanding this model by designing an 8-competitive algorithm for the problem on unit-length jobs and provide a lower bound of 2 on the competitive ratio. The lower bound is tight in the setting when jobs form non-nested intervals. Our 8-competitive algorithm generalizes to one with competitive ratio 8(2p-1)/p < 16 when all jobs have uniform length p.
Cite as

Gruia Călinescu, Sami Davies, Samir Khuller, and Shirley Zhang. Online Flexible Busy Time Scheduling on Heterogeneous Machines. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{calinescu_et_al:LIPIcs.ESA.2024.37,
  author =	{C\u{a}linescu, Gruia and Davies, Sami and Khuller, Samir and Zhang, Shirley},
  title =	{{Online Flexible Busy Time Scheduling on Heterogeneous Machines}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.37},
  URN =		{urn:nbn:de:0030-drops-211083},
  doi =		{10.4230/LIPIcs.ESA.2024.37},
  annote =	{Keywords: Online algorithms, Scheduling, Competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.38
Local Optimization Algorithms for Maximum Planar Subgraph

Authors: Gruia Călinescu and Sumedha Uniyal

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Consider the NP-hard problem of, given a simple graph G, to find a planar subgraph of G with the maximum number of edges. This is called the Maximum Planar Subgraph problem and the best known approximation is 4/9 and is obtained by sophisticated Graphic Matroid Parity algorithms. Here we show that applying a local optimization phase to the output of this known algorithm improves this approximation ratio by a small {ε} = 1/747 > 0. This is the first improvement in approximation ratio in more than a quarter century. The analysis relies on a more refined extremal bound on the Lovász cactus number in planar graphs, compared to the earlier (tight) bound of [Gruia Călinescu et al., 1998; Chalermsook et al., 2019]. A second local optimization algorithm achieves a tight ratio of 5/12 for Maximum Planar Subgraph without using Graphic Matroid Parity. We also show that applying a greedy algorithm before this second optimization algorithm improves its ratio to at least 91/216 < 4/9. The motivation for not using Graphic Matroid Parity is that it requires sophisticated algorithms that are not considered practical by previous work. The best previously published [Chalermsook and Schmid, 2017] approximation ratio without Graphic Matroid Parity is 13/33 < 5/12.
Cite as

Gruia Călinescu and Sumedha Uniyal. Local Optimization Algorithms for Maximum Planar Subgraph. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{calinescu_et_al:LIPIcs.ESA.2024.38,
  author =	{C\u{a}linescu, Gruia and Uniyal, Sumedha},
  title =	{{Local Optimization Algorithms for Maximum Planar Subgraph}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{38:1--38:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.38},
  URN =		{urn:nbn:de:0030-drops-211090},
  doi =		{10.4230/LIPIcs.ESA.2024.38},
  annote =	{Keywords: planar graph, maximum subgraph, approximation algorithm, matroid parity, local optimization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.42
From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs

Authors: Chandra Chekuri, Rhea Jain, Shubhang Kulkarni, Da Wei Zheng, and Weihao Zhu

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph G = (V,E), a root vertex r and a set S ⊆ V of k terminals. The goal is to find a min-cost subgraph that connects r to each of the terminals. DST admits an O(log² k/log log k)-approximation in quasi-polynomial time [Grandoni et al., 2022; Rohan Ghuge and Viswanath Nagarajan, 2022], and an O(k^{ε})-approximation for any fixed ε > 0 in polynomial-time [Alexander Zelikovsky, 1997; Moses Charikar et al., 1999]. Resolving the existence of a polynomial-time poly-logarithmic approximation is a major open problem in approximation algorithms. In a recent work, Friggstad and Mousavi [Zachary Friggstad and Ramin Mousavi, 2023] obtained a simple and elegant polynomial-time O(log k)-approximation for DST in planar digraphs via Thorup’s shortest path separator theorem [Thorup, 2004]. We build on their work and obtain several new results on DST and related problems. - We develop a tree embedding technique for rooted problems in planar digraphs via an interpretation of the recursion in [Zachary Friggstad and Ramin Mousavi, 2023]. Using this we obtain polynomial-time poly-logarithmic approximations for Group Steiner Tree [Naveen Garg et al., 2000], Covering Steiner Tree [Goran Konjevod et al., 2002] and the Polymatroid Steiner Tree [Gruia Călinescu and Alexander Zelikovsky, 2005] problems in planar digraphs. All these problems are hard to approximate to within a factor of Ω(log² n/log log n) even in trees [Eran Halperin and Robert Krauthgamer, 2003; Grandoni et al., 2022]. - We prove that the natural cut-based LP relaxation for DST has an integrality gap of O(log² k) in planar digraphs. This is in contrast to general graphs where the integrality gap of this LP is known to be Ω(√k) [Leonid Zosin and Samir Khuller, 2002] and Ω(n^{δ}) for some fixed δ > 0 [Shi Li and Bundit Laekhanukit, 2022]. - We combine the preceding results with density based arguments to obtain poly-logarithmic approximations for the multi-rooted versions of the problems in planar digraphs. For DST our result improves the O(R + log k) approximation of [Zachary Friggstad and Ramin Mousavi, 2023] when R = ω(log² k).
Cite as

Chandra Chekuri, Rhea Jain, Shubhang Kulkarni, Da Wei Zheng, and Weihao Zhu. From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:LIPIcs.ESA.2024.42,
  author =	{Chekuri, Chandra and Jain, Rhea and Kulkarni, Shubhang and Zheng, Da Wei and Zhu, Weihao},
  title =	{{From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{42:1--42:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.42},
  URN =		{urn:nbn:de:0030-drops-211134},
  doi =		{10.4230/LIPIcs.ESA.2024.42},
  annote =	{Keywords: Directed Planar Graphs, Submodular Functions, Steiner Tree, Network Design}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.19
An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint

Authors: Gruia Calinescu, Florian Jaehn, Minming Li, and Kai Wang

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
In this paper we study the classical scheduling problem of minimizing the total weighted completion time on a single machine with the constraint that one specific job must be scheduled at a specified position. We give dynamic programs with pseudo-polynomial running time, and a fully polynomial-time approximation scheme (FPTAS).
Cite as

Gruia Calinescu, Florian Jaehn, Minming Li, and Kai Wang. An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{calinescu_et_al:LIPIcs.ISAAC.2017.19,
  author =	{Calinescu, Gruia and Jaehn, Florian and Li, Minming and Wang, Kai},
  title =	{{An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.19},
  URN =		{urn:nbn:de:0030-drops-82335},
  doi =		{10.4230/LIPIcs.ISAAC.2017.19},
  annote =	{Keywords: FPTAS, Scheduling, Approximation Algorithm}
}
  • Refine by Type
  • 14 Document/PDF
  • 10 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 8 2025
  • 3 2024
  • 1 2017

  • Refine by Author
  • 2 Chekuri, Chandra
  • 2 Călinescu, Gruia
  • 1 Bajpai, Tanvi
  • 1 Banihashem, Kiarash
  • 1 Basu Roy, Aniket
  • Show More...

  • Refine by Series/Journal
  • 14 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Online algorithms
  • 2 Theory of computation → Packing and covering problems
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Mathematics of computing → Approximation algorithms
  • Show More...

  • Refine by Keyword
  • 2 Approximation Algorithms
  • 2 Scheduling
  • 2 parameterized complexity
  • 1 Approximation Algorithm
  • 1 Competitive analysis
  • 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