99 Search Results for "Vempala, Santosh"

Volume

LIPIcs, Volume 81

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA

Editors: Klaus Jansen, José D. P. Rolim, David P. Williamson, and Santosh S. Vempala

Document
DOI: 10.4230/LIPIcs.SEA.2026.14
K-Hole Separation in PEO‑Based ILP Treewidth Formulation

Authors: Andrea D'Ascenzo

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

Abstract
In this paper, we introduce a family of valid inequalities for the strongest currently known integer programming formulation of treewidth based on perfect elimination orderings. These inequalities arise from the structure of induced chordless cycles (holes) and strengthen the canonical linear relaxation by enforcing constraints that every feasible chordal completion must satisfy. To handle the exponentially many such inequalities, we develop a dedicated separation routine capable of detecting violated k-hole constraints within a cutting-plane framework. Our computational results show that incorporating these inequalities substantially improves the quality of the lower bounds across a broad range of graph classes, in some cases nearly closing the integrality gap.
Cite as

Andrea D'Ascenzo. K-Hole Separation in PEO‑Based ILP Treewidth Formulation. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dascenzo:LIPIcs.SEA.2026.14,
  author =	{D'Ascenzo, Andrea},
  title =	{{K-Hole Separation in PEO‑Based ILP Treewidth Formulation}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{14:1--14:14},
  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.14},
  URN =		{urn:nbn:de:0030-drops-260186},
  doi =		{10.4230/LIPIcs.SEA.2026.14},
  annote =	{Keywords: Treewidth, Integer Linear Programming, Polyhedral Combinatorics, Chordal Completion, Induced Cycles}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.31
Linear-Time (1+ε)-Approximation Algorithms for Two-Line-Center Problems

Authors: Chaeyoon Chung, Anil Maheshwari, and Michiel Smid

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

Abstract
Given a set S of n points in the plane, we study the two-line-center problem: finding two lines that minimize the maximum distance from each point in S to its closest line. We present a (1+ε)-approximation algorithm for the two-line-center problem that runs in O((n/ε) log (1/ε)) time, which improves the previously best O(nlog n + (n/ε²) log (1/ε) + (1/ε³)log (1/ε))-time algorithm. We also consider three variants of this problem, in which the orientations of the two lines are restricted: (1) the orientation of one of the two lines is fixed, (2) the orientations of both lines are fixed, and (3) the two lines are required to be parallel. For each of these three variants, we give the first (1+ε)-approximation algorithm that runs in linear time. In particular, for the variant where the orientation of one of the two lines is fixed, we also give an improved exact algorithm that runs in O(n log n) time and show that it is optimal.
Cite as

Chaeyoon Chung, Anil Maheshwari, and Michiel Smid. Linear-Time (1+ε)-Approximation Algorithms for Two-Line-Center Problems. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.SoCG.2026.31,
  author =	{Chung, Chaeyoon and Maheshwari, Anil and Smid, Michiel},
  title =	{{Linear-Time (1+\epsilon)-Approximation Algorithms for Two-Line-Center Problems}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{31:1--31:17},
  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.31},
  URN =		{urn:nbn:de:0030-drops-258374},
  doi =		{10.4230/LIPIcs.SoCG.2026.31},
  annote =	{Keywords: Approximation algorithm, two-line-center problem, k-line-center problem, projective clustering, \epsilon-certificate, \epsilon-coreset, width of a point set}
}
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.56
Optimal Randomized Clustering of Matrices

Authors: Mustafa Alper Gunes and Assaf Naor

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

Abstract
If X = (𝖬_n(ℝ),‖⋅‖_X) is a unitarily invariant normed space, i.e., ‖𝖴𝖠𝖵‖_X = ‖𝖠‖_X for every matrix 𝖠 ∈ 𝖬_n(ℝ) and every two orthogonal matrices 𝖴,𝖵 ∈ 𝖬_n(ℝ), then we evaluate up to universal constant factors the smallest σ > 0 for which there is a probability distribution over partitions of X into clusters of diameter at most 1 yet for every two matrices 𝖠,𝖡 ∈ 𝖬_n(ℝ) the probability that they fall into distinct clusters is at most σ times the X-distance between 𝖠 and 𝖡. Specifically, we prove that this infimal σ, which is called the separation modulus of X and is denoted SEP(X), satisfies: (1) SEP(X) = Θ(√n⋅ ‖𝖨_n‖_X⋅ diam(B_X)), where 𝖨_n is the n-by-n identity matrix and diam(B_X) is the diameter with respect to the standard Euclidean metric on 𝖬_n(ℝ) of the unit ball B_ X of X. Our proof of (1) proceeds through an asymptotic evaluation of the spectral gap of the Laplacian with Dirichlet boundary conditions on B_ X, which we achieve by exact computations for a Jacobi orthogonal random matrix ensemble. Assuming oracle access to norm evaluations in X, by combining (1) with a new deterministic algorithm for a O(1)-approximation of the diameter of convex bodies in ℝⁿ that are given by a weak membership oracle and are symmetric with respect to coordinate permutations and reflections about the standard axes (this task is famously known to be impossible in the absence of such symmetries), we get an oracle polynomial time algorithm whose output is the separation modulus of X up to universal constant factors. Another example of a consequence of (1) is that for each m ∈ {1,…,n} the separation modulus of the m'th Ky Fan norm on 𝖬_n(ℝ) is bounded from above and from below by universal constant multiples of m√n if m ⩾ √n, and of n if m ⩽ √n. We also deduce from (1) an upper bound on the Lipschitz extension modulus of X that improves over the previously best-known bound even in the special case when X is 𝖬_n(ℝ) equipped with the 𝓁₂ⁿ → 𝓁₂ⁿ operator norm.
Cite as

Mustafa Alper Gunes and Assaf Naor. Optimal Randomized Clustering of Matrices. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 56:1-56:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gunes_et_al:LIPIcs.SoCG.2026.56,
  author =	{Gunes, Mustafa Alper and Naor, Assaf},
  title =	{{Optimal Randomized Clustering of Matrices}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{56:1--56: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.56},
  URN =		{urn:nbn:de:0030-drops-258624},
  doi =		{10.4230/LIPIcs.SoCG.2026.56},
  annote =	{Keywords: Clustering, Unitarily Invariant Matrix Norms, Oracle Polynomial Time Approximation Algorithms for Radii of Convex Bodies, Extension of Lipschitz Functions, Random Matrices, Spectrum of the Laplacian with Dirichlet Boundary Conditions, Reverse Isoperimetry}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2026.7
The Importance of Parameters in Ranking Functions

Authors: Christoph Standke, Nikolaos Tziavelis, Wolfgang Gatterbauer, and Benny Kimelfeld

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
How important is the weight of a given column in determining the ranking of tuples in a table? To address such an explanation question about a ranking function, we investigate the computation of SHAP scores for column weights, adopting a recent framework by Grohe et al. [ICDT'24]. The exact definition of this score depends on three key components: (1) the ranking function in use, (2) an effect function that quantifies the impact of using alternative weights on the ranking, and (3) an underlying weight distribution. We analyze the computational complexity of different instantiations of this framework for a range of fundamental ranking and effect functions, focusing on probabilistically independent finite distributions for individual columns. For the ranking functions, we examine lexicographic orders and score-based orders defined by the summation, minimum, and maximum functions. For the effect functions, we consider global, top-k, and local perspectives: global measures quantify the divergence between the perturbed and original rankings, top-k measures inspect the change in the set of top-k answers, and local measures capture the impact on an individual tuple of interest. Although all cases admit an additive fully polynomial-time randomized approximation scheme (FPRAS), we establish the complexity of exact computation, identifying which cases are solvable in polynomial time and which are #P-hard. We further show that all complexity results, lower bounds and upper bounds, extend to a related task of computing the Shapley value of whole columns (regardless of their weight).
Cite as

Christoph Standke, Nikolaos Tziavelis, Wolfgang Gatterbauer, and Benny Kimelfeld. The Importance of Parameters in Ranking Functions. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{standke_et_al:LIPIcs.ICDT.2026.7,
  author =	{Standke, Christoph and Tziavelis, Nikolaos and Gatterbauer, Wolfgang and Kimelfeld, Benny},
  title =	{{The Importance of Parameters in Ranking Functions}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.7},
  URN =		{urn:nbn:de:0030-drops-256217},
  doi =		{10.4230/LIPIcs.ICDT.2026.7},
  annote =	{Keywords: Ranking, Explanation, Shapley value, SHAP scores}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.13
Line Cover and Related Problems

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana

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

Abstract
We study several extensions of the classic Line Cover problem of covering a set of n points in the plane with k lines. Line Cover is known to be NP-hard and our focus is on two natural generalizations: (1) Line Clustering, where the objective is to find k lines in the plane that minimize the sum of squares of distances of a given set of input points to the closest line, and (2) Hyperplane Cover, where the goal is to cover n points in ℝ^d by k hyperplanes. We also consider the more general Projective Clustering problem, which unifies both of these and has numerous applications in machine learning, data mining, and computational geometry. In this problem one seeks k affine subspaces of dimension r minimizing the sum of squares of distances of a given set of n points in ℝ^d to the closest point within one of the k affine subspaces. Our main contributions reveal interesting differences in the parameterized complexity of these problems. While Line Cover is fixed-parameter tractable parameterized by the number k of lines in the solution, we show that Line Clustering is W[1]-hard when parameterized by k and rule out algorithms of running time n^{o(k)} under the Exponential Time Hypothesis. Hyperplane Cover is known to be NP-hard even when d = 2 and by the work of Langerman and Morin [Discrete & Computational Geometry, 2005], it is FPT parameterized by k and d. We complement this result by establishing that Hyperplane Cover is W[2]-hard when parameterized by only k. We complement our hardness results by presenting an algorithm for Projective Clustering. We show that this problem is solvable in n^{𝒪(dk(r+1))} time. Not only does this yield an upper bound for Line Clustering that asymptotically matches our lower bound, but it also significantly extends the seminal work on k-Means Clustering (the special case r = 0) by Inaba, Katoh, and Imai [SoCG 1994].
Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana. Line Cover and Related Problems. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2026.13,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Saha, Souvik and Seetharaman, Sanjay and Upasana, Anannya},
  title =	{{Line Cover and Related Problems}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{13:1--13:18},
  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.13},
  URN =		{urn:nbn:de:0030-drops-255023},
  doi =		{10.4230/LIPIcs.STACS.2026.13},
  annote =	{Keywords: Point Line Cover, Projective Clustering, W-hardness, XP algorithm}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.67
Query Lower Bounds for Correlation Clustering Under Memory Constraints

Authors: Sumegha Garg, Songhua He, and Periklis A. Papakonstantinou

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

Abstract
This work initiates the study of memory–query tradeoffs for graph problems, with a focus on correlation clustering. Correlation clustering asks for a partition of the vertices that minimizes disagreements: non‑edges inside clusters plus edges across clusters. Our first result is a tight query lower bound: to output a partition whose cost approximates the optimum up to an additive error of ε n², any algorithm requires Ω(n/ε²) adjacency-matrix queries. Under memory constraints, we show that even for the seemingly easier task of approximating the optimal clustering cost (without producing a partition), any algorithm in the random query model must make ≫ n/ε² adjacency-matrix queries. Finally, we prove the first general graph model query lower bound for correlation clustering, where algorithms are allowed adjacency-matrix, neighbor, and degree queries. The latter two bounds are not yet tight, leaving room for sharper results.
Cite as

Sumegha Garg, Songhua He, and Periklis A. Papakonstantinou. Query Lower Bounds for Correlation Clustering Under Memory Constraints. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 67:1-67:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.ITCS.2026.67,
  author =	{Garg, Sumegha and He, Songhua and Papakonstantinou, Periklis A.},
  title =	{{Query Lower Bounds for Correlation Clustering Under Memory Constraints}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{67:1--67:24},
  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.67},
  URN =		{urn:nbn:de:0030-drops-253542},
  doi =		{10.4230/LIPIcs.ITCS.2026.67},
  annote =	{Keywords: correlation clustering, query-space complexity, information theory}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.65
Brief Announcement: Congested Clique Counting for Local Gibbs Distributions

Authors: Joshua Z. Sobel

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
There are well established reductions between combinatorial sampling and counting problems (Jerrum, Valiant, Vazirani TCS 1986). Building off of a very recent parallel algorithm utilizing this connection (Liu, Yin, Zhang arxiv 2024), we demonstrate the first approximate counting algorithm in the CongestedClique for a wide range of problems. Most interestingly, we present an algorithm for approximating the number of q-colorings of a graph within ε-multiplicative error, when q > αΔ for any constant α > 2, in Õ((n^{1/3})/ε²) rounds. More generally, we achieve a runtime of Õ((n^{1/3})/ε²) rounds for approximating the partition function of Gibbs distributions defined over graphs when simple locality and fast mixing conditions hold. Gibbs distributions are widely used in fields such as machine learning and statistical physics. We obtain our result by providing an algorithm to draw n random samples from a distributed Markov chain in parallel, using similar ideas to triangle counting (Dolev, Lenzen, Peled DISC 2012) and semiring matrix multiplication (Censor-Hillel, Kaski, Korhonen, Lenzen, Paz, Suomela PODC 2015). Aside from counting problems, this result may be interesting for other applications requiring a large number of samples.
Cite as

Joshua Z. Sobel. Brief Announcement: Congested Clique Counting for Local Gibbs Distributions. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 65:1-65:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sobel:LIPIcs.DISC.2025.65,
  author =	{Sobel, Joshua Z.},
  title =	{{Brief Announcement: Congested Clique Counting for Local Gibbs Distributions}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{65:1--65:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.65},
  URN =		{urn:nbn:de:0030-drops-248811},
  doi =		{10.4230/LIPIcs.DISC.2025.65},
  annote =	{Keywords: Distributed Sampling, Approximate Counting, Markov Chains, Gibbs Distributions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.69
Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing

Authors: David Eppstein, Michael T. Goodrich, and Songyu (Alfred) Liu

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

Abstract
We provide the first approximation quality guarantees for the Cuthull-McKee heuristic for reordering symmetric matrices to have low bandwidth, and we provide an algorithm for reconstructing bounded-bandwidth graphs from distance oracles with near-linear query complexity. To prove these results we introduce a new width parameter, BFS width, and we prove polylogarithmic upper and lower bounds on the BFS width of graphs of bounded bandwidth. Unlike other width parameters, such as bandwidth, pathwidth, and treewidth, BFS width can easily be computed in polynomial time. Bounded BFS width implies bounded bandwidth, pathwidth, and treewidth, which in turn imply fixed-parameter tractable algorithms for many problems that are NP-hard for general graphs. In addition to their applications to matrix ordering, we also provide applications of BFS width to graph reconstruction, to reconstruct graphs from distance queries, and graph drawing, to construct arc diagrams of small height.
Cite as

David Eppstein, Michael T. Goodrich, and Songyu (Alfred) Liu. Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 69:1-69:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.ESA.2025.69,
  author =	{Eppstein, David and Goodrich, Michael T. and Liu, Songyu (Alfred)},
  title =	{{Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{69:1--69:17},
  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.69},
  URN =		{urn:nbn:de:0030-drops-245373},
  doi =		{10.4230/LIPIcs.ESA.2025.69},
  annote =	{Keywords: Graph algorithms, graph theory, graph width, bandwidth, treewidth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.62
Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering

Authors: Sina Bagheri Nezhad, Sayan Bandyapadhyay, and Tianzhi Chen

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

Abstract
In a seminal work, Chierichetti et al. [Chierichetti et al., 2017] introduced the (t,k)-fair clustering problem: Given a set of red points and a set of blue points in a metric space, a clustering is called fair if the number of red points in each cluster is at most t times and at least 1/t times the number of blue points in that cluster. The goal is to compute a fair clustering with at most k clusters that optimizes certain objective function. Considering this problem, they designed a polynomial-time O(1)- and O(t)-approximation for the k-center and the k-median objective, respectively. Recently, Carta et al. [Carta et al., 2024] studied this problem with the sum-of-radii objective and obtained a (6+ε)-approximation with running time O((k log_{1+ε}(k/ε))^k n^O(1)), i.e., fixed-parameter tractable in k. Here n is the input size. In this work, we design the first polynomial-time O(1)-approximation for (t,k)-fair clustering with the sum-of-radii objective, improving the result of Carta et al. Our result places sum-of-radii in the same group of objectives as k-center, that admit polynomial-time O(1)-approximations. This result also implies a polynomial-time O(1)-approximation for the Euclidean version of the problem, for which an f(k)⋅n^O(1)-time (1+ε)-approximation was known due to Drexler et al. [Drexler et al., 2023]. Here f is an exponential function of k. We are also able to extend our result to any arbitrary 𝓁 ≥ 2 number of colors when t = 1. This matches known results for the k-center and k-median objectives in this case. The significant disparity of sum-of-radii compared to k-center and k-median presents several complex challenges, all of which we successfully overcome in our work. Our main contribution is a novel cluster-merging-based analysis technique for sum-of-radii that helps us achieve the constant-approximation bounds.
Cite as

Sina Bagheri Nezhad, Sayan Bandyapadhyay, and Tianzhi Chen. Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bagherinezhad_et_al:LIPIcs.ESA.2025.62,
  author =	{Bagheri Nezhad, Sina and Bandyapadhyay, Sayan and Chen, Tianzhi},
  title =	{{Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{62:1--62: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.62},
  URN =		{urn:nbn:de:0030-drops-245309},
  doi =		{10.4230/LIPIcs.ESA.2025.62},
  annote =	{Keywords: fair clustering, sum-of-radii clustering, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.107
Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts

Authors: Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak, and Shengzhe Wang

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

Abstract
We show the existence of length-constrained expander decomposition in directed graphs and undirected vertex-capacitated graphs. Previously, its existence was shown only in undirected edge-capacitated graphs [Bernhard Haeupler et al., 2022; Haeupler et al., 2024]. Along the way, we prove the multi-commodity maxflow-mincut theorems for length-constrained expansion in both directed and undirected vertex-capacitated graphs. Based on our decomposition, we build a length-constrained flow shortcut for undirected vertex-capacitated graphs, which roughly speaking is a set of edges and vertices added to the graph so that every multi-commodity flow demand can be routed with approximately the same vertex-congestion and length, but all flow paths only contain few edges. This generalizes the shortcut for undirected edge-capacitated graphs from [Bernhard Haeupler et al., 2024]. Length-constrained expander decomposition and flow shortcuts have been crucial in the recent algorithms in undirected edge-capacitated graphs [Bernhard Haeupler et al., 2024; Haeupler et al., 2024]. Our work thus serves as a foundation to generalize these concepts to directed and vertex-capacitated graphs.
Cite as

Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak, and Shengzhe Wang. Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 107:1-107:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{haeupler_et_al:LIPIcs.ESA.2025.107,
  author =	{Haeupler, Bernhard and Long, Yaowei and Saranurak, Thatchaphol and Wang, Shengzhe},
  title =	{{Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{107:1--107:17},
  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.107},
  URN =		{urn:nbn:de:0030-drops-245765},
  doi =		{10.4230/LIPIcs.ESA.2025.107},
  annote =	{Keywords: Length-Constrained Expander, Expander Decomposition, Shortcut}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.116
Fast Gaussian Elimination for Low Treewidth Matrices

Authors: Martin Fürer, Carlos Hoppen, and Vilmar Trevisan

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

Abstract
Let A = (a_{ij}) be an m× n matrix whose elements lie in an arbitrary field 𝔽, and let G be the bipartite graph with vertex set {v_1,…,v_m} ∪ {w_1,…,w_n} such that vertices v_i and w_j are adjacent if and only if a_{ij} ≠ 0. We introduce an algorithm that finds an m× n matrix U in row echelon form and a permutation matrix Q of order n, such that AQ is row equivalent to U. If a tree decomposition 𝒯 of G of width k and size O(k(m+n)) is part of the input, then Q and the columns of U that contain a pivot can be computed in time O(k²(m+n)). Among other things, this allows us to compute the rank and the determinant of A in time O(k²(m+n)). It also allows us to decide in time O(k²(m+n)) whether the linear system Ax = b has a solution and to compute a solution of the linear system in case it exists.
Cite as

Martin Fürer, Carlos Hoppen, and Vilmar Trevisan. Fast Gaussian Elimination for Low Treewidth Matrices. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 116:1-116:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{furer_et_al:LIPIcs.ESA.2025.116,
  author =	{F\"{u}rer, Martin and Hoppen, Carlos and Trevisan, Vilmar},
  title =	{{Fast Gaussian Elimination for Low Treewidth Matrices}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{116:1--116:15},
  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.116},
  URN =		{urn:nbn:de:0030-drops-245855},
  doi =		{10.4230/LIPIcs.ESA.2025.116},
  annote =	{Keywords: Gaussian elimination, FPT algorithms, treewidth}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.42
On the Spectral Expansion of Monotone Subsets of the Hypercube

Authors: Yumou Fei and Renato Ferreira Pinto Jr.

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

Abstract
We study the spectral gap of subgraphs of the hypercube induced by monotone subsets of vertices. For a monotone subset A ⊆ {0,1}ⁿ of density μ(A), the previous best lower bound on the spectral gap, due to Cohen [Cohen, 2016], was γ ≳ μ(A)/n², improving upon the earlier bound γ ≳ μ(A)²/n² established by Ding and Mossel [Ding and Mossel, 2014]. In this paper, we prove the optimal lower bound γ ≳ μ(A)/n. As a corollary, we improve the mixing time upper bound of the random walk on constant-density monotone sets from O(n³), as shown by Ding and Mossel, to O(n²). Along the way, we develop two new inequalities that may be of independent interest: (1) a directed L²-Poincaré inequality on the hypercube, and (2) an "approximate" FKG inequality for monotone sets.
Cite as

Yumou Fei and Renato Ferreira Pinto Jr.. On the Spectral Expansion of Monotone Subsets of the Hypercube. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 42:1-42:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fei_et_al:LIPIcs.APPROX/RANDOM.2025.42,
  author =	{Fei, Yumou and Ferreira Pinto Jr., Renato},
  title =	{{On the Spectral Expansion of Monotone Subsets of the Hypercube}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{42:1--42:24},
  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.42},
  URN =		{urn:nbn:de:0030-drops-244081},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.42},
  annote =	{Keywords: Random walks, mixing time, FKG inequality, Poincar\'{e} inequality, directed isoperimetry}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.30
Algorithmic Contiguity from Low-Degree Conjecture and Applications in Correlated Random Graphs

Authors: Zhangsong Li

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

Abstract
In this paper, assuming a natural strengthening of the low-degree conjecture, we provide evidence of computational hardness for two problems: (1) the (partial) matching recovery problem in the sparse correlated Erdős-Rényi graphs G(n,q;ρ) when the edge-density q = n^{-1+o(1)} and the correlation ρ < √{α} lies below the Otter’s threshold, this resolves a remaining problem in [Jian Ding et al., 2023]; (2) the detection problem between a pair of correlated sparse stochastic block model S(n,λ/n;k,ε;s) and a pair of independent stochastic block models S(n,λs/n;k,ε) when ε² λ s < 1 lies below the Kesten-Stigum (KS) threshold and s < √α lies below the Otter’s threshold, this resolves a remaining problem in [Guanyi Chen et al., 2024]. One of the main ingredient in our proof is to derive certain forms of algorithmic contiguity between two probability measures based on bounds on their low-degree advantage. To be more precise, consider the high-dimensional hypothesis testing problem between two probability measures ℙ and ℚ based on the sample Y. We show that if the low-degree advantage Adv_{≤D}(dℙ/dℚ) = O(1), then (assuming the low-degree conjecture) there is no efficient algorithm A such that ℚ(A(Y) = 0) = 1-o(1) and ℙ(A(Y) = 1) = Ω(1). This framework provides a useful tool for performing reductions between different inference tasks.
Cite as

Zhangsong Li. Algorithmic Contiguity from Low-Degree Conjecture and Applications in Correlated Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{li:LIPIcs.APPROX/RANDOM.2025.30,
  author =	{Li, Zhangsong},
  title =	{{Algorithmic Contiguity from Low-Degree Conjecture and Applications in Correlated Random Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{30:1--30:18},
  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.30},
  URN =		{urn:nbn:de:0030-drops-243965},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.30},
  annote =	{Keywords: Algorithmic Contiguity, Low-degree Conjecture, Correlated Random Graphs}
}
  • Refine by Type
  • 98 Document/PDF
  • 35 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 7 2026
  • 28 2025
  • 1 2023
  • 2 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 9 Vempala, Santosh S.
  • 5 Guruswami, Venkatesan
  • 3 Jansen, Klaus
  • 3 Lee, Euiwoong
  • 3 Mahabadi, Sepideh
  • Show More...

  • Refine by Series/Journal
  • 98 LIPIcs

  • Refine by Classification
  • 10 Theory of computation → Design and analysis of algorithms
  • 5 Theory of computation → Approximation algorithms analysis
  • 4 Theory of computation → Computational geometry
  • 4 Theory of computation → Randomness, geometry and discrete structures
  • 3 Mathematics of computing → Approximation algorithms
  • Show More...

  • Refine by Keyword
  • 8 Approximation Algorithms
  • 4 approximation algorithms
  • 3 Linear Programming
  • 2 Approximation algorithm
  • 2 Brain computation
  • 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