28 Search Results for "Suri, Subhash"

Document
DOI: 10.4230/LIPIcs.GD.2024.26
Storylines with a Protagonist

Authors: Tim Hegemann and Alexander Wolff

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Storyline visualizations show interactions between a given set of characters over time. Each character is represented by an x-monotone curve. A meeting is represented by a vertical bar that is crossed by the curves of exactly those characters that participate in the meeting. Therefore, character curves may have to cross each other. In the context of publication networks, we consider storylines where the characters are authors and the meetings are joint publications. We are especially interested in visualizing a group of colleagues centered around an author, the protagonist, who participates in all selected publications. For such instances, we propose a drawing style where the protagonist’s curve is drawn at a prominent position and never crossed by any other author’s curve. We consider two variants of storylines with a protagonist. In the one-sided variant, the protagonist is required to be drawn at the top position. In this restricted setting, we can efficiently compute a drawing with the minimum number of pairwise crossings, whereas we show that it is NP-hard to minimize the number of block crossings (i.e., pairs of blocks of parallel curves that intersect each other). In the two-sided variant, the task is to split the set of co-authors of the protagonist into two groups, and to place the curves of one group above and the curves of the other group below the protagonist’s curve such that the total number of (block) crossings is minimized. As our main result, we present an algorithm for bundling a sequence of pairwise crossings into a sequence of few block crossings (in the absence of meetings). It exploits a connection to a rectangle dissection problem. In the presence of meetings, it yields results that are very close to a lower bound. Based on this bundling algorithm and our exact algorithm for the one-sided variant, we present a new heuristic for computing two-sided storylines with few block crossings. We perform an extensive experimental study using publication data of 81 protagonists from GD 2023 and their most frequent collaborators over the last ten years. Our study shows that, for two-sided storylines with a protagonist, our new heuristic uses fewer block crossings (and fewer pairwise crossings) than two heuristics for block crossing minimization in general storylines.
Cite as

Tim Hegemann and Alexander Wolff. Storylines with a Protagonist. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hegemann_et_al:LIPIcs.GD.2024.26,
  author =	{Hegemann, Tim and Wolff, Alexander},
  title =	{{Storylines with a Protagonist}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.26},
  URN =		{urn:nbn:de:0030-drops-213109},
  doi =		{10.4230/LIPIcs.GD.2024.26},
  annote =	{Keywords: Storyline visualization, storyline with a protagonist, crossing minimization, block crossings}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.95
Fault Tolerance in Euclidean Committee Selection

Authors: Chinmay Sonar, Subhash Suri, and Jie Xue

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
In the committee selection problem, the goal is to choose a subset of size k from a set of candidates C that collectively gives the best representation to a set of voters. We consider this problem in Euclidean d-space where each voter/candidate is a point and voters' preferences are implicitly represented by Euclidean distances to candidates. We explore fault-tolerance in committee selection and study the following three variants: (1) given a committee and a set of f failing candidates, find their optimal replacement; (2) compute the worst-case replacement score for a given committee under failure of f candidates; and (3) design a committee with the best replacement score under worst-case failures. The score of a committee is determined using the well-known (min-max) Chamberlin-Courant rule: minimize the maximum distance between any voter and its closest candidate in the committee. Our main results include the following: (1) in one dimension, all three problems can be solved in polynomial time; (2) in dimension d ≥ 2, all three problems are NP-hard; and (3) all three problems admit a constant-factor approximation in any fixed dimension, and the optimal committee problem has an FPT bicriterion approximation.
Cite as

Chinmay Sonar, Subhash Suri, and Jie Xue. Fault Tolerance in Euclidean Committee Selection. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 95:1-95:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{sonar_et_al:LIPIcs.ESA.2023.95,
  author =	{Sonar, Chinmay and Suri, Subhash and Xue, Jie},
  title =	{{Fault Tolerance in Euclidean Committee Selection}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{95:1--95:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.95},
  URN =		{urn:nbn:de:0030-drops-187489},
  doi =		{10.4230/LIPIcs.ESA.2023.95},
  annote =	{Keywords: Multiwinner elections, Fault tolerance, Geometric Hitting Set, EPTAS}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.11
Minimum-Membership Geometric Set Cover, Revisited

Authors: Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We revisit a natural variant of the geometric set cover problem, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set S of points and a set ℛ of geometric objects, and the goal is to find a subset ℛ^* ⊆ ℛ to cover all points in S such that the membership of S with respect to ℛ^*, denoted by memb(S,ℛ^*), is minimized, where memb(S,ℛ^*) = max_{p ∈ S} |{R ∈ ℛ^*: p ∈ R}|. We give the first polynomial-time approximation algorithms for MMGSC in ℝ². Specifically, we achieve the following two main results. - We give the first polynomial-time constant-approximation algorithm for MMGSC with unit squares. This answers a question left open since the work of Erlebach and Leeuwen [SODA'08], who gave a constant-approximation algorithm with running time n^{O(opt)} where opt is the optimum of the problem (i.e., the minimum membership). - We give the first polynomial-time approximation scheme (PTAS) for MMGSC with halfplanes. Prior to this work, it was even unknown whether the problem can be approximated with a factor of o(log n) in polynomial time, while it is well-known that the minimum-size set cover problem with halfplanes can be solved in polynomial time. We also consider a problem closely related to MMGSC, called minimum-ply geometric set cover (MPGSC), in which the goal is to find ℛ^* ⊆ ℛ to cover S such that the ply of ℛ^* is minimized, where the ply is defined as the maximum number of objects in ℛ^* which have a nonempty common intersection. Very recently, Durocher et al. gave the first constant-approximation algorithm for MPGSC with unit squares which runs in O(n^{12}) time. We give a significantly simpler constant-approximation algorithm with near-linear running time.
Cite as

Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue. Minimum-Membership Geometric Set Cover, Revisited. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.11,
  author =	{Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket and Xue, Jie},
  title =	{{Minimum-Membership Geometric Set Cover, Revisited}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.11},
  URN =		{urn:nbn:de:0030-drops-178610},
  doi =		{10.4230/LIPIcs.SoCG.2023.11},
  annote =	{Keywords: geometric set cover, geometric optimization, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.52
Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles

Authors: Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh, Subhash Suri, and Jie Xue

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Suppose we are given a pair of points s, t and a set 𝒮 of n geometric objects in the plane, called obstacles. We show that in polynomial time one can construct an auxiliary (multi-)graph G with vertex set 𝒮 and every edge labeled from {0, 1}, such that a set 𝒮_d ⊆ 𝒮 of obstacles separates s from t if and only if G[𝒮_d] contains a cycle whose sum of labels is odd. Using this structural characterization of separating sets of obstacles we obtain the following algorithmic results. In the Obstacle-removal problem the task is to find a curve in the plane connecting s to t intersecting at most q obstacles. We give a 2.3146^q n^{O(1)} algorithm for Obstacle-removal, significantly improving upon the previously best known q^{O(q³)} n^{O(1)} algorithm of Eiben and Lokshtanov (SoCG'20). We also obtain an alternative proof of a constant factor approximation algorithm for Obstacle-removal, substantially simplifying the arguments of Kumar et al. (SODA'21). In the Generalized Points-separation problem input consists of the set 𝒮 of obstacles, a point set A of k points and p pairs (s₁, t₁), … (s_p, t_p) of points from A. The task is to find a minimum subset 𝒮_r ⊆ 𝒮 such that for every i, every curve from s_i to t_i intersects at least one obstacle in 𝒮_r. We obtain 2^{O(p)} n^{O(k)}-time algorithm for Generalized Points-separation. This resolves an open problem of Cabello and Giannopoulos (SoCG'13), who asked about the existence of such an algorithm for the special case where (s₁, t₁), … (s_p, t_p) contains all the pairs of points in A. Finally, we improve the running time of our algorithm to f(p,k) ⋅ n^{O(√k)} when the obstacles are unit disks, where f(p,k) = 2^{O(p)} k^{O(k)}, and show that, assuming the Exponential Time Hypothesis (ETH), the running time dependence on k of our algorithms is essentially optimal.
Cite as

Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh, Subhash Suri, and Jie Xue. Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.SoCG.2022.52,
  author =	{Kumar, Neeraj and Lokshtanov, Daniel and Saurabh, Saket and Suri, Subhash and Xue, Jie},
  title =	{{Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.52},
  URN =		{urn:nbn:de:0030-drops-160609},
  doi =		{10.4230/LIPIcs.SoCG.2022.52},
  annote =	{Keywords: points-separation, min color path, constraint removal, barrier resillience}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.32
Anonymity-Preserving Space Partitions

Authors: Úrsula Hébert-Johnson, Chinmay Sonar, Subhash Suri, and Vaishali Surianarayanan

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We consider a multidimensional space partitioning problem, which we call Anonymity-Preserving Partition. Given a set P of n points in ℝ^d and a collection H of m axis-parallel hyperplanes, the hyperplanes of H partition the space into an arrangement A(H) of rectangular cells. Given an integer parameter t > 0, we call a cell C in this arrangement deficient if 0 < |C ∩ P| < t; that is, the cell contains at least one but fewer than t data points of P. Our problem is to remove the minimum number of hyperplanes from H so that there are no deficient cells. We show that the problem is NP-complete for all dimensions d ≥ 2. We present a polynomial-time d-approximation algorithm, for any fixed d, and we also show that the problem can be solved exactly in time (2d-0.924)^k m^O(1) + O(n), where k is the solution size. The one-dimensional case of the problem, where all hyperplanes are parallel, can be solved optimally in polynomial time, but we show that a related Interval Anonymity problem is NP-complete even in one dimension.
Cite as

Úrsula Hébert-Johnson, Chinmay Sonar, Subhash Suri, and Vaishali Surianarayanan. Anonymity-Preserving Space Partitions. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hebertjohnson_et_al:LIPIcs.ISAAC.2021.32,
  author =	{H\'{e}bert-Johnson, \'{U}rsula and Sonar, Chinmay and Suri, Subhash and Surianarayanan, Vaishali},
  title =	{{Anonymity-Preserving Space Partitions}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.32},
  URN =		{urn:nbn:de:0030-drops-154654},
  doi =		{10.4230/LIPIcs.ISAAC.2021.32},
  annote =	{Keywords: Anonymity, Hitting Set, LP, Constant Approximation, Fixed-Parameter Tractable, Space Partitions, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.28
An ETH-Tight Algorithm for Multi-Team Formation

Authors: Daniel Lokshtanov, Saket Saurabh, Subhash Suri, and Jie Xue

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
In the Multi-Team Formation problem, we are given a ground set C of n candidates, each of which is characterized by a d-dimensional attribute vector in ℝ^d, and two positive integers α and β satisfying α β ≤ n. The goal is to form α disjoint teams T₁,...,T_α ⊆ C, each of which consists of β candidates in C, such that the total score of the teams is maximized, where the score of a team T is the sum of the h_j maximum values of the j-th attributes of the candidates in T, for all j ∈ {1,...,d}. Our main result is an 2^{2^O(d)} n^O(1)-time algorithm for Multi-Team Formation. This bound is ETH-tight since a 2^{2^{d/c}} n^O(1)-time algorithm for any constant c > 12 can be shown to violate the Exponential Time Hypothesis (ETH). Our algorithm runs in polynomial time for all dimensions up to d = clog log n for a sufficiently small constant c > 0. Prior to our work, the existence of a polynomial time algorithm was an open problem even for d = 3.
Cite as

Daniel Lokshtanov, Saket Saurabh, Subhash Suri, and Jie Xue. An ETH-Tight Algorithm for Multi-Team Formation. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 28:1-28:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.FSTTCS.2021.28,
  author =	{Lokshtanov, Daniel and Saurabh, Saket and Suri, Subhash and Xue, Jie},
  title =	{{An ETH-Tight Algorithm for Multi-Team Formation}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{28:1--28:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.28},
  URN =		{urn:nbn:de:0030-drops-155391},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.28},
  annote =	{Keywords: Team formation, Parameterized algorithms, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.63
Efficient Algorithms for Least Square Piecewise Polynomial Regression

Authors: Daniel Lokshtanov, Subhash Suri, and Jie Xue

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We present approximation and exact algorithms for piecewise regression of univariate and bivariate data using fixed-degree polynomials. Specifically, given a set S of n data points (𝐱₁, y₁),… , (𝐱_n, y_n) ∈ ℝ^d × ℝ where d ∈ {1,2}, the goal is to segment 𝐱_i’s into some (arbitrary) number of disjoint pieces P₁, … , P_k, where each piece P_j is associated with a fixed-degree polynomial f_j: ℝ^d → ℝ, to minimize the total loss function λ k + ∑_{i = 1}ⁿ (y_i - f(𝐱_i))², where λ ≥ 0 is a regularization term that penalizes model complexity (number of pieces) and f: ⨆_{j = 1}^k P_j → ℝ is the piecewise polynomial function defined as f|_{P_j} = f_j. The pieces P₁, … , P_k are disjoint intervals of ℝ in the case of univariate data and disjoint axis-aligned rectangles in the case of bivariate data. Our error approximation allows use of any fixed-degree polynomial, not just linear functions. Our main results are the following. For univariate data, we present a (1 + ε)-approximation algorithm with time complexity O(n/(ε) log 1/(ε)), assuming that data is presented in sorted order of x_i’s. For bivariate data, we present three results: a sub-exponential exact algorithm with running time n^{O(√n)}; a polynomial-time constant-approximation algorithm; and a quasi-polynomial time approximation scheme (QPTAS). The bivariate case is believed to be NP-hard in the folklore but we could not find a published record in the literature, so in this paper we also present a hardness proof for completeness.
Cite as

Daniel Lokshtanov, Subhash Suri, and Jie Xue. Efficient Algorithms for Least Square Piecewise Polynomial Regression. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.ESA.2021.63,
  author =	{Lokshtanov, Daniel and Suri, Subhash and Xue, Jie},
  title =	{{Efficient Algorithms for Least Square Piecewise Polynomial Regression}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{63:1--63:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.63},
  URN =		{urn:nbn:de:0030-drops-146443},
  doi =		{10.4230/LIPIcs.ESA.2021.63},
  annote =	{Keywords: regression analysis, piecewise polynomial, least square error}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.2
Dynamic Geometric Set Cover and Hitting Set

Authors: Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our paper are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in ℝ¹ and ℝ². The first framework uses bootstrapping and gives a (1+ε)-approximate data structure for dynamic interval set cover in ℝ¹ with O(n^α/ε) amortized update time for any constant α > 0; in ℝ², this method gives O(1)-approximate data structures for unit-square (and quadrant) set cover and hitting set with O(n^(1/2+α)) amortized update time. The second framework uses local modification, and leads to a (1+ε)-approximate data structure for dynamic interval hitting set in ℝ¹ with Õ(1/ε) amortized update time; in ℝ², it gives O(1)-approximate data structures for unit-square (and quadrant) set cover and hitting set in the partially dynamic settings with Õ(1) amortized update time.
Cite as

Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue. Dynamic Geometric Set Cover and Hitting Set. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2020.2,
  author =	{Agarwal, Pankaj K. and Chang, Hsien-Chih and Suri, Subhash and Xiao, Allen and Xue, Jie},
  title =	{{Dynamic Geometric Set Cover and Hitting Set}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{2:1--2:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.2},
  URN =		{urn:nbn:de:0030-drops-121604},
  doi =		{10.4230/LIPIcs.SoCG.2020.2},
  annote =	{Keywords: Geometric set cover, Geometric hitting set, Dynamic data structures}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.19
The Maximum Exposure Problem

Authors: Neeraj Kumar, Stavros Sintos, and Subhash Suri

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

Abstract
Given a set of points P and axis-aligned rectangles R in the plane, a point p in P is called exposed if it lies outside all rectangles in R. In the max-exposure problem, given an integer parameter k, we want to delete k rectangles from R so as to maximize the number of exposed points. We show that the problem is NP-hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in R are translates of two fixed rectangles. However, if R only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For general rectangle range space, we present a simple O(k) bicriteria approximation algorithm; that is by deleting O(k^2) rectangles, we can expose at least Omega(1/k) of the optimal number of points.
Cite as

Neeraj Kumar, Stavros Sintos, and Subhash Suri. The Maximum Exposure Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.APPROX-RANDOM.2019.19,
  author =	{Kumar, Neeraj and Sintos, Stavros and Suri, Subhash},
  title =	{{The Maximum Exposure Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{19:1--19:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.19},
  URN =		{urn:nbn:de:0030-drops-112344},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.19},
  annote =	{Keywords: max-exposure, PTAS, densest k-subgraphs, geometric constraint removal, Network resilience}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.37
Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames

Authors: Sayan Bandyapadhyay, Anil Maheshwari, Saeed Mehrabi, and Subhash Suri

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We consider the Minimum Dominating Set (MDS) problem on the intersection graphs of geometric objects. Even for simple and widely-used geometric objects such as rectangles, no sub-logarithmic approximation is known for the problem and (perhaps surprisingly) the problem is NP-hard even when all the rectangles are "anchored" at a diagonal line with slope -1 (Pandit, CCCG 2017). In this paper, we first show that for any epsilon>0, there exists a (2+epsilon)-approximation algorithm for the MDS problem on "diagonal-anchored" rectangles, providing the first O(1)-approximation for the problem on a non-trivial subclass of rectangles. It is not hard to see that the MDS problem on "diagonal-anchored" rectangles is the same as the MDS problem on "diagonal-anchored" L-frames: the union of a vertical and a horizontal line segment that share an endpoint. As such, we also obtain a (2+epsilon)-approximation for the problem with "diagonal-anchored" L-frames. On the other hand, we show that the problem is APX-hard in case the input L-frames intersect the diagonal, or the horizontal segments of the L-frames intersect a vertical line. However, as we show, the problem is linear-time solvable in case the L-frames intersect a vertical as well as a horizontal line. Finally, we consider the MDS problem in the so-called "edge intersection model" and obtain a number of results, answering two questions posed by Mehrabi (WAOA 2017).
Cite as

Sayan Bandyapadhyay, Anil Maheshwari, Saeed Mehrabi, and Subhash Suri. Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.MFCS.2018.37,
  author =	{Bandyapadhyay, Sayan and Maheshwari, Anil and Mehrabi, Saeed and Suri, Subhash},
  title =	{{Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.37},
  URN =		{urn:nbn:de:0030-drops-96198},
  doi =		{10.4230/LIPIcs.MFCS.2018.37},
  annote =	{Keywords: Minimum dominating set, Rectangles and L-frames, Approximation schemes, Local search, APX-hardness}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.2
Improved Approximation Bounds for the Minimum Constraint Removal Problem

Authors: Sayan Bandyapadhyay, Neeraj Kumar, Subhash Suri, and Kasturi Varadarajan

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

Abstract
In the minimum constraint removal problem, we are given a set of geometric objects as obstacles in the plane, and we want to find the minimum number of obstacles that must be removed to reach a target point t from the source point s by an obstacle-free path. The problem is known to be intractable, and (perhaps surprisingly) no sub-linear approximations are known even for simple obstacles such as rectangles and disks. The main result of our paper is a new approximation technique that gives O(sqrt{n})-approximation for rectangles, disks as well as rectilinear polygons. The technique also gives O(sqrt{n})-approximation for the minimum color path problem in graphs. We also present some inapproximability results for the geometric constraint removal problem.
Cite as

Sayan Bandyapadhyay, Neeraj Kumar, Subhash Suri, and Kasturi Varadarajan. Improved Approximation Bounds for the Minimum Constraint Removal Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.APPROX-RANDOM.2018.2,
  author =	{Bandyapadhyay, Sayan and Kumar, Neeraj and Suri, Subhash and Varadarajan, Kasturi},
  title =	{{Improved Approximation Bounds for the Minimum Constraint Removal Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{2:1--2:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.2},
  URN =		{urn:nbn:de:0030-drops-94066},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.2},
  annote =	{Keywords: Minimum Constraint Removal, Minimum Color Path, Barrier Resilience, Obstacle Removal, Obstacle Free Path, Approximation}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.5
Computing Shortest Paths in the Plane with Removable Obstacles

Authors: Pankaj K. Agarwal, Neeraj Kumar, Stavros Sintos, and Subhash Suri

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
We consider the problem of computing a Euclidean shortest path in the presence of removable obstacles in the plane. In particular, we have a collection of pairwise-disjoint polygonal obstacles, each of which may be removed at some cost c_i > 0. Given a cost budget C > 0, and a pair of points s, t, which obstacles should be removed to minimize the path length from s to t in the remaining workspace? We show that this problem is NP-hard even if the obstacles are vertical line segments. Our main result is a fully-polynomial time approximation scheme (FPTAS) for the case of convex polygons. Specifically, we compute an (1 + epsilon)-approximate shortest path in time O({nh}/{epsilon^2} log n log n/epsilon) with removal cost at most (1+epsilon)C, where h is the number of obstacles, n is the total number of obstacle vertices, and epsilon in (0, 1) is a user-specified parameter. Our approximation scheme also solves a shortest path problem for a stochastic model of obstacles, where each obstacle's presence is an independent event with a known probability. Finally, we also present a data structure that can answer s-t path queries in polylogarithmic time, for any pair of points s, t in the plane.
Cite as

Pankaj K. Agarwal, Neeraj Kumar, Stavros Sintos, and Subhash Suri. Computing Shortest Paths in the Plane with Removable Obstacles. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SWAT.2018.5,
  author =	{Agarwal, Pankaj K. and Kumar, Neeraj and Sintos, Stavros and Suri, Subhash},
  title =	{{Computing Shortest Paths in the Plane with Removable Obstacles}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.5},
  URN =		{urn:nbn:de:0030-drops-88312},
  doi =		{10.4230/LIPIcs.SWAT.2018.5},
  annote =	{Keywords: Euclidean shortest paths, Removable polygonal obstacles, Stochastic shortest paths, L\underline1 shortest paths}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.49
Shortest Paths in the Plane with Obstacle Violations

Authors: John Hershberger, Neeraj Kumar, and Subhash Suri

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We study the problem of finding shortest paths in the plane among h convex obstacles, where the path is allowed to pass through (violate) up to k obstacles, for k <= h. Equivalently, the problem is to find shortest paths that become obstacle-free if k obstacles are removed from the input. Given a fixed source point s, we show how to construct a map, called a shortest k-path map, so that all destinations in the same region of the map have the same combinatorial shortest path passing through at most k obstacles. We prove a tight bound of Theta(kn) on the size of this map, and show that it can be computed in O(k^2 n log n) time, where n is the total number of obstacle vertices.
Cite as

John Hershberger, Neeraj Kumar, and Subhash Suri. Shortest Paths in the Plane with Obstacle Violations. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hershberger_et_al:LIPIcs.ESA.2017.49,
  author =	{Hershberger, John and Kumar, Neeraj and Suri, Subhash},
  title =	{{Shortest Paths in the Plane with Obstacle Violations}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{49:1--49:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.49},
  URN =		{urn:nbn:de:0030-drops-78413},
  doi =		{10.4230/LIPIcs.ESA.2017.49},
  annote =	{Keywords: Shortest paths, Polygonal obstacles, Continuous Dijkstra, Obstacle crossing, Visibility}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.65
K-Dominance in Multidimensional Data: Theory and Applications

Authors: Thomas Schibler and Subhash Suri

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We study the problem of k-dominance in a set of d-dimensional vectors, prove bounds on the number of maxima (skyline vectors), under both worst-case and average-case models, perform experimental evaluation using synthetic and real-world data, and explore an application of k-dominant skyline for extracting a small set of top-ranked vectors in high dimensions where the full skylines can be unmanageably large.
Cite as

Thomas Schibler and Subhash Suri. K-Dominance in Multidimensional Data: Theory and Applications. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{schibler_et_al:LIPIcs.ESA.2017.65,
  author =	{Schibler, Thomas and Suri, Subhash},
  title =	{{K-Dominance in Multidimensional Data: Theory and Applications}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.65},
  URN =		{urn:nbn:de:0030-drops-78402},
  doi =		{10.4230/LIPIcs.ESA.2017.65},
  annote =	{Keywords: Dominance, skyline, database search, average case analysis, random vectors}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.7
Efficient Algorithms for k-Regret Minimizing Sets

Authors: Pankaj K. Agarwal, Nirman Kumar, Stavros Sintos, and Subhash Suri

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
A regret minimizing set Q is a small size representation of a much larger database P so that user queries executed on Q return answers whose scores are not much worse than those on the full dataset. In particular, a k-regret minimizing set has the property that the regret ratio between the score of the top-1 item in Q and the score of the top-k item in P is minimized, where the score of an item is the inner product of the item's attributes with a user's weight (preference) vector. The problem is challenging because we want to find a single representative set Q whose regret ratio is small with respect to all possible user weight vectors. We show that k-regret minimization is NP-Complete for all dimensions d>=3, settling an open problem from Chester et al. [VLDB 2014]. Our main algorithmic contributions are two approximation algorithms, both with provable guarantees, one based on coresets and another based on hitting sets. We perform extensive experimental evaluation of our algorithms, using both real-world and synthetic data, and compare their performance against the solution proposed in [VLDB 14]. The results show that our algorithms are significantly faster and scalable to much larger sets than the greedy algorithm of Chester et al. for comparable quality answers.
Cite as

Pankaj K. Agarwal, Nirman Kumar, Stavros Sintos, and Subhash Suri. Efficient Algorithms for k-Regret Minimizing Sets. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SEA.2017.7,
  author =	{Agarwal, Pankaj K. and Kumar, Nirman and Sintos, Stavros and Suri, Subhash},
  title =	{{Efficient Algorithms for k-Regret Minimizing Sets}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.7},
  URN =		{urn:nbn:de:0030-drops-76321},
  doi =		{10.4230/LIPIcs.SEA.2017.7},
  annote =	{Keywords: regret minimizing sets, skyline, top-k query, coreset, hitting set}
}
  • Refine by Author
  • 18 Suri, Subhash
  • 6 Xue, Jie
  • 5 Kumar, Neeraj
  • 3 Agarwal, Pankaj K.
  • 3 Bandyapadhyay, Sayan
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Sensor Networks
  • 2 art gallery problem
  • 2 skyline
  • 1 3-SUM hardness
  • 1 APX-hardness
  • Show More...

  • Refine by Type
  • 28 document

  • Refine by Publication Year
  • 6 2010
  • 3 2007
  • 3 2017
  • 3 2018
  • 3 2021
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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