Search Results

Documents authored by Huang, Shang-En

Document
DOI: 10.4230/LIPIcs.FORC.2025.4
Hardness and Approximation Algorithms for Balanced Districting Problems

Authors: Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract
We introduce and study the problem of balanced districting, where given an undirected graph with vertices carrying two types of weights (different population, resource types, etc) the goal is to maximize the total weights covered in vertex disjoint districts such that each district is a star or (in general) a connected induced subgraph with the two weights to be balanced. This problem is strongly motivated by political redistricting, where contiguity, population balance, and compactness are essential. We provide hardness and approximation algorithms for this problem. In particular, we show NP-hardness for an approximation better than n^{1/2-δ} for any constant δ > 0 in general graphs even when the districts are star graphs, as well as NP-hardness on complete graphs, tree graphs, planar graphs and other restricted settings. On the other hand, we develop an algorithm for balanced star districting that gives an O(√n)-approximation on any graph (which is basically tight considering matching hardness of approximation results), an O(log n) approximation on planar graphs with extensions to minor-free graphs. Our algorithm uses a modified Whack-a-Mole algorithm [Bhattacharya, Kiss, and Saranurak, SODA 2023] to find a sparse solution of a fractional packing linear program (despite exponentially many variables) which requires a new design of a separation oracle specific for our balanced districting problem. To turn the fractional solution to a feasible integer solution, we adopt the randomized rounding algorithm by [Chan and Har-Peled, SoCG 2009]. To get a good approximation ratio of the rounding procedure, a crucial element in the analysis is the balanced scattering separators for planar graphs and minor-free graphs - separators that can be partitioned into a small number of k-hop independent sets for some constant k - which may find independent interest in solving other packing style problems. Further, our algorithm is versatile - the very same algorithm can be analyzed in different ways on various graph classes, which leads to class-dependent approximation ratios. We also provide a FPTAS algorithm for complete graphs and tree graphs, as well as greedy algorithms and approximation ratios when the district cardinality is bounded, the graph has bounded degree or the weights are binary. We refer the readers to the full version of the paper for complete set of results and proofs.
Cite as

Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu. Hardness and Approximation Algorithms for Balanced Districting Problems. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 4:1-4:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dharangutte_et_al:LIPIcs.FORC.2025.4,
  author =	{Dharangutte, Prathamesh and Gao, Jie and Huang, Shang-En and Yu, Fang-Yi},
  title =	{{Hardness and Approximation Algorithms for Balanced Districting Problems}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{4:1--4:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.4},
  URN =		{urn:nbn:de:0030-drops-231310},
  doi =		{10.4230/LIPIcs.FORC.2025.4},
  annote =	{Keywords: Approximation algorithms, algorithmic fairness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.70
Vertex Sparsifiers for Hyperedge Connectivity

Authors: Han Jiang, Shang-En Huang, Thatchaphol Saranurak, and Tian Zhang

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Recently, Chalermsook et al. {[}SODA'21{]} introduces a notion of vertex sparsifiers for c-edge connectivity, which has found applications in parameterized algorithms for network design and also led to exciting dynamic algorithms for c-edge st-connectivity {[}Jin and Sun FOCS'22{]}. We study a natural extension called vertex sparsifiers for c-hyperedge connectivity and construct a sparsifier whose size matches the state-of-the-art for normal graphs. More specifically, we show that, given a hypergraph G = (V,E) with n vertices and m hyperedges with k terminal vertices and a parameter c, there exists a hypergraph H containing only O(kc³) hyperedges that preserves all minimum cuts (up to value c) between all subset of terminals. This matches the best bound of O(kc³) edges for normal graphs by [Liu'20]. Moreover, H can be constructed in almost-linear O(p^{1+o(1)} + n(rclog n)^{O(rc)}log m) time where r = max_{e ∈ E}|e| is the rank of G and p = ∑_{e ∈ E}|e| is the total size of G, or in poly(m, n) time if we slightly relax the size to O(kc³log^{1.5}(kc)) hyperedges.
Cite as

Han Jiang, Shang-En Huang, Thatchaphol Saranurak, and Tian Zhang. Vertex Sparsifiers for Hyperedge Connectivity. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ESA.2022.70,
  author =	{Jiang, Han and Huang, Shang-En and Saranurak, Thatchaphol and Zhang, Tian},
  title =	{{Vertex Sparsifiers for Hyperedge Connectivity}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{70:1--70:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.70},
  URN =		{urn:nbn:de:0030-drops-170081},
  doi =		{10.4230/LIPIcs.ESA.2022.70},
  annote =	{Keywords: Vertex sparsifier, hypergraph, connectivity}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.26
Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts

Authors: Shang-En Huang and Seth Pettie

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

Abstract
We prove better lower bounds on additive spanners and emulators, which are lossy compression schemes for undirected graphs, as well as lower bounds on shortcut sets, which reduce the diameter of directed graphs. We show that any O(n)-size shortcut set cannot bring the diameter below Omega(n^{1/6}), and that any O(m)-size shortcut set cannot bring it below Omega(n^{1/11}). These improve Hesse's [Hesse, 2003] lower bound of Omega(n^{1/17}). By combining these constructions with Abboud and Bodwin's [Abboud and Bodwin, 2017] edge-splitting technique, we get additive stretch lower bounds of +Omega(n^{1/13}) for O(n)-size spanners and +Omega(n^{1/18}) for O(n)-size emulators. These improve Abboud and Bodwin's +Omega(n^{1/22}) lower bounds.
Cite as

Shang-En Huang and Seth Pettie. Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 26:1-26:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.SWAT.2018.26,
  author =	{Huang, Shang-En and Pettie, Seth},
  title =	{{Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{26:1--26:12},
  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.26},
  URN =		{urn:nbn:de:0030-drops-88521},
  doi =		{10.4230/LIPIcs.SWAT.2018.26},
  annote =	{Keywords: additive spanners, emulators, shortcutting directed graphs}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact