34 Search Results for "Inamdar, Tanmay"

Document
DOI: 10.4230/LIPIcs.ESA.2025.46
Max-Distance Sparsification for Diversification and Clustering

Authors: Soh Kumabe

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

Abstract
Let 𝒟 be a set family that is the solution domain of some combinatorial problem. The max-min diversification problem on 𝒟 is the problem to select k sets from 𝒟 such that the Hamming distance between any two selected sets is at least d. FPT algorithms parameterized by k+𝓁, where 𝓁 = max_{D ∈ 𝒟}|D|, and k+d have been actively studied recently for several specific domains. This paper provides unified algorithmic frameworks to solve this problem. Specifically, for each parameterization k+𝓁 and k+d, we provide an FPT oracle algorithm for the max-min diversification problem using oracles related to 𝒟. We then demonstrate that our frameworks provide the first FPT algorithms on several new domains 𝒟, including the domain of t-linear matroid intersection, almost 2-SAT, minimum edge s,t-flows, vertex sets of s,t-mincut, vertex sets of edge bipartization, and Steiner trees. We also demonstrate that our frameworks generalize most of the existing domain-specific tractability results. Our main technical breakthrough is introducing the notion of max-distance sparsifier of 𝒟, a domain on which the max-min diversification problem is equivalent to the same problem on the original domain 𝒟. The core of our framework is to design FPT oracle algorithms that construct a constant-size max-distance sparsifier of 𝒟. Using max-distance sparsifiers, we provide FPT algorithms for the max-min and max-sum diversification problems on 𝒟, as well as k-center and k-sum-of-radii clustering problems on 𝒟, which are also natural problems in the context of diversification and have their own interests.
Cite as

Soh Kumabe. Max-Distance Sparsification for Diversification and Clustering. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kumabe:LIPIcs.ESA.2025.46,
  author =	{Kumabe, Soh},
  title =	{{Max-Distance Sparsification for Diversification and Clustering}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{46:1--46:14},
  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.46},
  URN =		{urn:nbn:de:0030-drops-245146},
  doi =		{10.4230/LIPIcs.ESA.2025.46},
  annote =	{Keywords: Fixed-Parameter Tractability, Diversification, Clustering}
}
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.110
Faster Exponential Algorithms for Cut Problems via Geometric Data Structures

Authors: László Kozma and Junqi Tan

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

Abstract
For many hard computational problems, simple algorithms that run in time 2ⁿ ⋅ n^O(1) arise, say, from enumerating all subsets of a size-n set. Finding (exponentially) faster algorithms is a natural goal that has driven much of the field of exact exponential algorithms (e.g., see Fomin and Kratsch, 2010). In this paper we obtain algorithms with running time O(1.9999977ⁿ) on input graphs with n vertices, for the following well-studied problems: - d-Cut: find a proper cut in which no vertex has more than d neighbors on the other side of the cut; - Internal Partition: find a proper cut in which every vertex has at least as many neighbors on its side of the cut as on the other side; and - (α,β)-Domination: given intervals α,β ⊆ [0,n], find a subset S of the vertices, so that for every vertex v ∈ S the number of neighbors of v in S is from α and for every vertex v ∉ S, the number of neighbors of v in S is from β. Our algorithms are exceedingly simple, combining the split and list technique (Horowitz and Sahni, 1974; Williams, 2005) with a tool from computational geometry: orthogonal range searching in the moderate dimensional regime (Chan, 2017). Our technique is applicable to the decision, optimization and counting versions of these problems and easily extends to various generalizations with more fine-grained, vertex-specific constraints, as well as to directed, balanced, and other variants. Algorithms with running times of the form cⁿ, for c < 2, were known for the first problem only for constant d, and for the third problem for certain special cases of α and β; for the second problem we are not aware of such results.
Cite as

László Kozma and Junqi Tan. Faster Exponential Algorithms for Cut Problems via Geometric Data Structures. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 110:1-110:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kozma_et_al:LIPIcs.ESA.2025.110,
  author =	{Kozma, L\'{a}szl\'{o} and Tan, Junqi},
  title =	{{Faster Exponential Algorithms for Cut Problems via Geometric Data Structures}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{110:1--110:12},
  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.110},
  URN =		{urn:nbn:de:0030-drops-245796},
  doi =		{10.4230/LIPIcs.ESA.2025.110},
  annote =	{Keywords: graph algorithms, cuts, exponential time, data structures}
}
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.23
Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints

Authors: Sayan Bandyapadhyay and Tianzhi Chen

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

Abstract
In this work, we study k-min-sum-of-radii (k-MSR) clustering under mergeable constraints. k-MSR seeks to group data points using a set of up to k balls, such that the sum of the radii of the balls is minimized. A clustering constraint is called mergeable if merging two clusters satisfying the constraint, results in a cluster that also satisfies the constraint. Many popularly studied constraints are mergeable, including fairness constraints and lower bound constraints. In our work, we design a (4+ε)-approximation for k-MSR under any given mergeable constraint with runtime 2^{O(k/(ε)⋅log²k/ε)} n⁴, i.e., fixed-parameter tractable in k for constant ε. Our result directly improves upon the FPT (6+ε)-approximation by Carta et al. [Carta et al., 2024]. We also provide a hardness result that excludes the exact solvability of k-MSR under any given mergeable constraint in time f(k)n^o(k), assuming ETH is true.
Cite as

Sayan Bandyapadhyay and Tianzhi Chen. Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.APPROX/RANDOM.2025.23,
  author =	{Bandyapadhyay, Sayan and Chen, Tianzhi},
  title =	{{Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{23:1--23:17},
  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.23},
  URN =		{urn:nbn:de:0030-drops-243894},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.23},
  annote =	{Keywords: sum-of-radii clustering, mergeable constraints, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.36
On the Complexity of Minimising the Moving Distance for Dispersing Objects

Authors: Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka, and Hirotaka Ono

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

Abstract
We study Geometric Graph Edit Distance (GGED), a graph-editing model to compute the minimum edit distance of intersection graphs that uses moving objects as an edit operation. We first show an O(n log n)-time algorithm that minimises the total moving distance to disperse unit intervals. This algorithm is applied to render a given unit interval graph (i) edgeless, (ii) acyclic and (iii) k-clique-free. We next show that GGED becomes strongly NP-hard when rendering a weighted interval graph (i) edgeless, (ii) acyclic and (iii) k-clique-free. Lastly, we prove that minimising the maximum moving distance for rendering a unit disk graph edgeless is strongly NP-hard over the L₁ and L₂ distances.
Cite as

Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka, and Hirotaka Ono. On the Complexity of Minimising the Moving Distance for Dispersing Objects. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{honoratodroguett_et_al:LIPIcs.WADS.2025.36,
  author =	{Honorato-Droguett, Nicol\'{a}s and Kurita, Kazuhiro and Hanaka, Tesshu and Ono, Hirotaka},
  title =	{{On the Complexity of Minimising the Moving Distance for Dispersing Objects}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{36:1--36:14},
  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.36},
  URN =		{urn:nbn:de:0030-drops-242673},
  doi =		{10.4230/LIPIcs.WADS.2025.36},
  annote =	{Keywords: Intersection graphs, Optimisation, Graph modification}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.13
Solving Partial Dominating Set and Related Problems Using Twin-Width

Authors: Jakub Balabán, Daniel Mock, and Peter Rossmanith

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are W[1]-hard on general graphs, they have been shown to be fixed-parameter tractable on many sparse graph classes, including nowhere-dense classes. In this paper, we demonstrate that these problems are also fixed-parameter tractable with respect to the twin-width of a graph. Indeed, we establish a more general result: every graph property that can be expressed by a logical formula of the form ϕ≡∃ x₁⋯ ∃ x_k ∑_{α ∈ I} #y ψ_α(x₁,…,x_k,y) ≥ t, where ψ_α is a quantifier-free formula for each α ∈ I, t is an arbitrary number, and #y is a counting quantifier, can be evaluated in time f(d,k)n, where n is the number of vertices and d is the width of a contraction sequence that is part of the input. In addition to the aforementioned problems, this includes also connected partial dominating set and independent partial dominating set.
Cite as

Jakub Balabán, Daniel Mock, and Peter Rossmanith. Solving Partial Dominating Set and Related Problems Using Twin-Width. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.MFCS.2025.13,
  author =	{Balab\'{a}n, Jakub and Mock, Daniel and Rossmanith, Peter},
  title =	{{Solving Partial Dominating Set and Related Problems Using Twin-Width}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.13},
  URN =		{urn:nbn:de:0030-drops-241203},
  doi =		{10.4230/LIPIcs.MFCS.2025.13},
  annote =	{Keywords: Partial Dominating Set, Partial Vertex Cover, meta-algorithm, counting logic, twin-width}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.39
Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems

Authors: Barış Can Esmer and Ariel Kulik

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

Abstract
In this paper, we present Sampling with a Black Box, a unified framework for the design of parameterized approximation algorithms for vertex deletion problems (e.g., Vertex Cover, Feedback Vertex Set, etc.). The framework relies on two components: - A Sampling Step. A polynomial-time randomized algorithm that, given a graph G, returns a random vertex v such that the optimum of G⧵ {v} is smaller by 1 than the optimum of G, with some prescribed probability q. We show that such algorithms exist for multiple vertex deletion problems. - A Black Box algorithm which is either an exact parameterized algorithm, a polynomial-time approximation algorithm, or a parameterized-approximation algorithm. The framework combines these two components together. The sampling step is applied iteratively to remove vertices from the input graph, and then the solution is extended using the black box algorithm. The process is repeated sufficiently many times so that the target approximation ratio is attained with a constant probability. We use the technique to derive parameterized approximation algorithms for several vertex deletion problems, including Feedback Vertex Set, d-Hitting Set and 𝓁-Path Vertex Cover. In particular, for every approximation ratio 1 < β < 2, we attain a parameterized β-approximation for Feedback Vertex Set, which is faster than the parameterized β-approximation of [Jana, Lokshtanov, Mandal, Rai and Saurabh, MFCS 23']. Furthermore, our algorithms are always faster than the algorithms attained using Fidelity Preserving Transformations [Fellows, Kulik, Rosamond, and Shachnai, JCSS 18'].
Cite as

Barış Can Esmer and Ariel Kulik. Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{canesmer_et_al:LIPIcs.ICALP.2025.39,
  author =	{Can Esmer, Bar{\i}\c{s} and Kulik, Ariel},
  title =	{{Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{39:1--39: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.39},
  URN =		{urn:nbn:de:0030-drops-234165},
  doi =		{10.4230/LIPIcs.ICALP.2025.39},
  annote =	{Keywords: Parameterized Approximation Algorithms, Random Sampling}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.14
Multivariate Exploration of Metric Dilation

Authors: Aritra Banik, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Satyabrata Jana, and Saket Saurabh

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

Abstract
Let G be a weighted graph embedded in a metric space (M, d_M). The vertices of G correspond to the points in M, with the weight of each edge uv being the distance d_M(u,v) between their respective points in M. The dilation (or stretch) of G is defined as the minimum factor t such that, for any pair of vertices u,v, the distance between u and v - represented by the weight of a shortest u,v-path - is at most t⋅ d_M(u,v). We study Dilation t-Augmentation, where the objective is, given a metric M, a graph G, and numerical values k and t, to determine whether G can be transformed into a graph with dilation t by adding at most k edges. Our primary focus is on the scenario where the metric M is the shortest path metric of an unweighted graph Γ. Even in this specific case, Dilation t-Augmentation remains computationally challenging. In particular, the problem is W[2]-hard parameterized by k when Γ is a complete graph, already for t = 2. Our main contribution lies in providing new insights into the impact of combinations of various parameters on the computational complexity of the problem. We establish the following. - The parameterized dichotomy of the problem with respect to dilation t, when the graph G is sparse: Parameterized by k, the problem is FPT for graphs excluding a biclique K_{d,d} as a subgraph for t ≤ 2 and the problem is W[1]-hard for t ≥ 3 even if G is a forest consisting of disjoint stars. - The problem is FPT parameterized by the combined parameter k+t+Δ, where Δ is the maximum degree of the graph G or Γ.
Cite as

Aritra Banik, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Satyabrata Jana, and Saket Saurabh. Multivariate Exploration of Metric Dilation. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banik_et_al:LIPIcs.STACS.2025.14,
  author =	{Banik, Aritra and Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Jana, Satyabrata and Saurabh, Saket},
  title =	{{Multivariate Exploration of Metric Dilation}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{14:1--14:17},
  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.14},
  URN =		{urn:nbn:de:0030-drops-228395},
  doi =		{10.4230/LIPIcs.STACS.2025.14},
  annote =	{Keywords: Metric dilation, geometric spanner, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.35
Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering

Authors: Ameet Gadekar and Tanmay Inamdar

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

Abstract
Hybrid k-Clustering is a model of clustering that generalizes two of the most widely studied clustering objectives: k-Center and k-Median. In this model, given a set of n points P, the goal is to find k centers such that the sum of the r-distances of each point to its nearest center is minimized. The r-distance between two points p and q is defined as max{dist(p, q)-r, 0} - this represents the distance of p to the boundary of the r-radius ball around q if p is outside the ball, and 0 otherwise. This problem was recently introduced by Fomin et al. [APPROX 2024], who designed a (1+ε, 1+ε)-bicrtieria approximation that runs in time 2^{(kd/ε)^{O(1)}} ⋅ n^{O(1)} for inputs in ℝ^d; such a bicriteria solution uses balls of radius (1+ε)r instead of r, and has a cost at most 1+ε times the cost of an optimal solution using balls of radius r. In this paper we significantly improve upon this result by designing an approximation algorithm with the same bicriteria guarantee, but with running time that is FPT only in k and ε - crucially, removing the exponential dependence on the dimension d. This resolves an open question posed in their paper. Our results extend further in several directions. First, our approximation scheme works in a broader class of metric spaces, including doubling spaces, minor-free, and bounded treewidth metrics. Secondly, our techniques yield a similar bicriteria FPT-approximation schemes for other variants of Hybrid k-Clustering, e.g., when the objective features the sum of z-th power of the r-distances. Finally, we also design a coreset for Hybrid k-Clustering in doubling spaces, answering another open question from the work of Fomin et al.
Cite as

Ameet Gadekar and Tanmay Inamdar. Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gadekar_et_al:LIPIcs.STACS.2025.35,
  author =	{Gadekar, Ameet and Inamdar, Tanmay},
  title =	{{Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{35:1--35:20},
  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.35},
  URN =		{urn:nbn:de:0030-drops-228615},
  doi =		{10.4230/LIPIcs.STACS.2025.35},
  annote =	{Keywords: Clustering, Parameterized algorithms, FPT approximation, k-Median, k-Center}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.15
Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems

Authors: Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar, and Saket Saurabh

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

Abstract
In this paper, we begin the exploration of vertex-ordering problems through the lens of exponential-time approximation algorithms. In particular, we ask the following question: Can we simultaneously beat the running times of the fastest known (exponential-time) exact algorithms and the best known approximation factors that can be achieved in polynomial time? Following the recent research initiated by Esmer et al. (ESA 2022, IPEC 2023, SODA 2024) on vertex-subset problems, and by Inamdar et al. (ITCS 2024) on graph-partitioning problems, we focus on vertex-ordering problems. In particular, we give positive results for Feedback Arc Set, Optimal Linear Arrangement, Cutwidth, and Pathwidth. Most of our algorithms build upon a novel "balanced-cut" approach - which is our main conceptual contribution. This allows us to solve various problems in very general settings allowing for directed and arc-weighted input graphs. Our main technical contribution is a (1+ε)-approximation for any ε > 0 for (weighted) Feedback Arc Set in O^*((2-δ_ε)^n) time, where δ_ε > 0 is a constant only depending on ε.
Cite as

Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar, and Saket Saurabh. Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ITCS.2025.15,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Inamdar, Tanmay and Saurabh, Saket},
  title =	{{Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{15:1--15: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.15},
  URN =		{urn:nbn:de:0030-drops-226431},
  doi =		{10.4230/LIPIcs.ITCS.2025.15},
  annote =	{Keywords: Feedback Arc Set, Cutwidth, Optimal Linear Arrangement, Pathwidth}
}
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.FSTTCS.2024.24
When Far Is Better: The Chamberlin-Courant Approach to Obnoxious Committee Selection

Authors: Sushmita Gupta, Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract
Classical work on metric space based committee selection problem interprets distance as "near is better". In this work, motivated by real-life situations, we interpret distance as "far is better". Formally stated, we initiate the study of "obnoxious" committee scoring rules when the voters' preferences are expressed via a metric space. To accomplish this, we propose a model where large distances imply high satisfaction (in contrast to the classical setting where shorter distances imply high satisfaction) and study the egalitarian avatar of the well-known Chamberlin-Courant voting rule and some of its generalizations. For a given integer value λ between 1 and k, the committee size, a voter derives satisfaction from only the λth favorite committee member; the goal is to maximize the satisfaction of the least satisfied voter. For the special case of λ = 1, this yields the egalitarian Chamberlin-Courant rule. In this paper, we consider general metric space and the special case of a d-dimensional Euclidean space. We show that when λ is 1 and k, the problem is polynomial-time solvable in ℝ² and general metric space, respectively. However, for λ = k-1, it is NP-hard even in ℝ². Thus, we have "double-dichotomy" in ℝ² with respect to the value of λ, where the extreme cases are solvable in polynomial time but an intermediate case is NP-hard. Furthermore, this phenomenon appears to be "tight" for ℝ² because the problem is NP-hard for general metric space, even for λ = 1. Consequently, we are motivated to explore the problem in the realm of (parameterized) approximation algorithms and obtain positive results. Interestingly, we note that this generalization of Chamberlin-Courant rules encodes practical constraints that are relevant to solutions for certain facility locations.
Cite as

Sushmita Gupta, Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. When Far Is Better: The Chamberlin-Courant Approach to Obnoxious Committee Selection. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 24:1-24:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.FSTTCS.2024.24,
  author =	{Gupta, Sushmita and Inamdar, Tanmay and Jain, Pallavi and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket},
  title =	{{When Far Is Better: The Chamberlin-Courant Approach to Obnoxious Committee Selection}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{24:1--24:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.24},
  URN =		{urn:nbn:de:0030-drops-222135},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.24},
  annote =	{Keywords: Metric Space, Parameterized Complexity, Approximation, Obnoxious Facility Location}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.17
Cuts in Graphs with Matroid Constraints

Authors: Aritra Banik, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Satyabrata Jana, and Saket Saurabh

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

Abstract
Vertex (s, t)-Cut and Vertex Multiway Cut are two fundamental graph separation problems in algorithmic graph theory. We study matroidal generalizations of these problems, where in addition to the usual input, we are given a representation R ∈ 𝔽^{r × n} of a linear matroid ℳ = (V(G), ℐ) of rank r in the input, and the goal is to determine whether there exists a vertex subset S ⊆ V(G) that has the required cut properties, as well as is independent in the matroid ℳ. We refer to these problems as Independent Vertex (s, t){-cut}, and Independent Multiway Cut, respectively. We show that these problems are fixed-parameter tractable (FPT) when parameterized by the solution size (which can be assumed to be equal to the rank of the matroid ℳ). These results are obtained by exploiting the recent technique of flow augmentation [Kim et al. STOC '22], combined with a dynamic programming algorithm on flow-paths á la [Feige and Mahdian, STOC '06] that maintains a representative family of solutions w.r.t. the given matroid [Marx, TCS '06; Fomin et al., JACM]. As a corollary, we also obtain FPT algorithms for the independent version of Odd Cycle Transversal. Further, our results can be generalized to other variants of the problems, e.g., weighted versions, or edge-deletion versions.
Cite as

Aritra Banik, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Satyabrata Jana, and Saket Saurabh. Cuts in Graphs with Matroid Constraints. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{banik_et_al:LIPIcs.ESA.2024.17,
  author =	{Banik, Aritra and Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Jana, Satyabrata and Saurabh, Saket},
  title =	{{Cuts in Graphs with Matroid Constraints}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{17:1--17:15},
  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.17},
  URN =		{urn:nbn:de:0030-drops-210887},
  doi =		{10.4230/LIPIcs.ESA.2024.17},
  annote =	{Keywords: s-t-cut, multiway Cut, matroid, odd cycle transversal, feedback vertex set, fixed-parameter tractability}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.4
Hybrid k-Clustering: Blending k-Median and k-Center

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

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

Abstract
We propose a novel clustering model encompassing two well-known clustering models: k-center clustering and k-median clustering. In the Hybrid k-Clustering problem, given a set P of points in ℝ^d, an integer k, and a non-negative real r, our objective is to position k closed balls of radius r to minimize the sum of distances from points not covered by the balls to their closest balls. Equivalently, we seek an optimal L₁-fitting of a union of k balls of radius r to a set of points in the Euclidean space. When r = 0, this corresponds to k-median; when the minimum sum is zero, indicating complete coverage of all points, it is k-center. Our primary result is a bicriteria approximation algorithm that, for a given ε > 0, produces a hybrid k-clustering with balls of radius (1+ε)r. This algorithm achieves a cost at most 1+ε of the optimum, and it operates in time 2^{(kd/ε)^𝒪(1)} ⋅ n^𝒪(1). Notably, considering the established lower bounds on k-center and k-median, our bicriteria approximation stands as the best possible result for Hybrid k-Clustering.
Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Hybrid k-Clustering: Blending k-Median and k-Center. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.APPROX/RANDOM.2024.4,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Hybrid k-Clustering: Blending k-Median and k-Center}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.4},
  URN =		{urn:nbn:de:0030-drops-209975},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.4},
  annote =	{Keywords: clustering, k-center, k-median, Euclidean space, fpt approximation}
}
  • Refine by Type
  • 34 Document/PDF
  • 12 Document/HTML

  • Refine by Publication Year
  • 12 2025
  • 5 2024
  • 6 2023
  • 3 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 24 Inamdar, Tanmay
  • 14 Saurabh, Saket
  • 11 Fomin, Fedor V.
  • 9 Golovach, Petr A.
  • 7 Bandyapadhyay, Sayan
  • Show More...

  • Refine by Series/Journal
  • 34 LIPIcs

  • Refine by Classification
  • 12 Theory of computation → Parameterized complexity and exact algorithms
  • 10 Theory of computation → Facility location and clustering
  • 7 Theory of computation → Approximation algorithms analysis
  • 6 Theory of computation → Fixed parameter tractability
  • 4 Theory of computation → Computational geometry
  • Show More...

  • Refine by Keyword
  • 5 clustering
  • 3 Partial Vertex Cover
  • 3 approximation algorithms
  • 3 fixed-parameter tractability
  • 3 k-median
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact