Search Results

Documents authored by Huang, Chien-Chung

Document
DOI: 10.4230/LIPIcs.ESA.2022.68
Maximum Weight b-Matchings in Random-Order Streams

Authors: Chien-Chung Huang and François Sellier

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

Abstract
We consider the maximum weight b-matching problem in the random-order semi-streaming model. Assuming all weights are small integers drawn from [1,W], we present a 2 - 1/(2W) + ε approximation algorithm, using a memory of O(max(|M_G|, n) ⋅ poly(log(m),W,1/ε)), where |M_G| denotes the cardinality of the optimal matching. Our result generalizes that of Bernstein [Aaron Bernstein, 2020], which achieves a 3/2 + ε approximation for the maximum cardinality simple matching. When W is small, our result also improves upon that of Gamlath et al. [Gamlath et al., 2019], which obtains a 2 - δ approximation (for some small constant δ ∼ 10^{-17}) for the maximum weight simple matching. In particular, for the weighted b-matching problem, ours is the first result beating the approximation ratio of 2. Our technique hinges on a generalized weighted version of edge-degree constrained subgraphs, originally developed by Bernstein and Stein [Aaron Bernstein and Cliff Stein, 2015]. Such a subgraph has bounded vertex degree (hence uses only a small number of edges), and can be easily computed. The fact that it contains a 2 - 1/(2W) + ε approximation of the maximum weight matching is proved using the classical Kőnig-Egerváry’s duality theorem.
Cite as

Chien-Chung Huang and François Sellier. Maximum Weight b-Matchings in Random-Order Streams. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ESA.2022.68,
  author =	{Huang, Chien-Chung and Sellier, Fran\c{c}ois},
  title =	{{Maximum Weight b-Matchings in Random-Order Streams}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{68:1--68:14},
  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.68},
  URN =		{urn:nbn:de:0030-drops-170062},
  doi =		{10.4230/LIPIcs.ESA.2022.68},
  annote =	{Keywords: Maximum weight matching, b-matching, streaming, random order}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.37
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

Authors: Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
In the k-edge-connected spanning subgraph (kECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to k link failures: Given an n-node m-edge graph with a cost function on the edges, our goal is to compute a minimum-cost k-edge-connected spanning subgraph. This NP-hard problem generalizes the minimum spanning tree problem and is the "uniform case" of a much broader class of survival network design problems (SNDP). A factor of two has remained the best approximation ratio for polynomial-time algorithms for the whole class of SNDP, even for a special case of 2ECSS. The fastest 2-approximation algorithm is however rather slow, taking O(mn k) time [Khuller, Vishkin, STOC'92]. A faster time complexity of O(n²) can be obtained, but with a higher approximation guarantee of (2k-1) [Gabow, Goemans, Williamson, IPCO'93]. Our main contribution is an algorithm that (1+ε)-approximates the optimal fractional solution in Õ(m/ε²) time (independent of k), which can be turned into a (2+ε) approximation algorithm that runs in time Õ(m/(ε²) + {k²n^{1.5}}/ε²) for (integral) kECSS; this improves the running time of the aforementioned results while keeping the approximation ratio arbitrarily close to a factor of two.
Cite as

Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai. Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.ICALP.2022.37,
  author =	{Chalermsook, Parinya and Huang, Chien-Chung and Nanongkai, Danupon and Saranurak, Thatchaphol and Sukprasert, Pattara and Yingchareonthawornchai, Sorrachai},
  title =	{{Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.37},
  URN =		{urn:nbn:de:0030-drops-163785},
  doi =		{10.4230/LIPIcs.ICALP.2022.37},
  annote =	{Keywords: Approximation Algorithms, Data Structures}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.27
Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms

Authors: Chien-Chung Huang and François Sellier

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
Given a graph with weights on the edges and a matroid imposed on the vertices, our problem is to choose a subset of vertices that is independent in the matroid, with the objective of maximizing the total weight of covered edges. This problem is a generalization of the much studied max k-vertex cover problem, where the matroid is the simple uniform matroid, and it is also a special case of maximizing a monotone submodular function under a matroid constraint. In this work, we give a Fixed Parameter Tractable Approximation Scheme (FPT-AS) when the given matroid is a partition matroid, a laminar matroid, or a transversal matroid. Precisely, if k is the rank of the matroid, we obtain (1 - ε) approximation using (1/(ε))^{O(k)}n^{O(1)} time for partition and laminar matroids and using (1/(ε)+k)^{O(k)}n^{O(1)} time for transversal matroids. This extends a result of Manurangsi for uniform matroids [Pasin Manurangsi, 2018]. We also show that these ideas can be applied in the context of (single-pass) streaming algorithms. Our FPT-AS introduces a new technique based on matroid union, which may be of independent interest in extremal combinatorics.
Cite as

Chien-Chung Huang and François Sellier. Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.SWAT.2022.27,
  author =	{Huang, Chien-Chung and Sellier, Fran\c{c}ois},
  title =	{{Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.27},
  URN =		{urn:nbn:de:0030-drops-161874},
  doi =		{10.4230/LIPIcs.SWAT.2022.27},
  annote =	{Keywords: Maximum vertex cover, matroid, approximate kernel, streaming}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.14
Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint

Authors: Chien-Chung Huang and François Sellier

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

Abstract
We consider the problem of maximizing a submodular function under the b-matching constraint, in the semi-streaming model. Our main results can be summarized as follows. - When the function is linear, i.e. for the maximum weight b-matching problem, we obtain a 2+ε approximation. This improves the previous best bound of 3+ε [Roie Levin and David Wajc, 2021]. - When the function is a non-negative monotone submodular function, we obtain a 3 + 2 √2 ≈ 5.828 approximation. This matches the currently best ratio [Roie Levin and David Wajc, 2021]. - When the function is a non-negative non-monotone submodular function, we obtain a 4 + 2 √3 ≈ 7.464 approximation. This ratio is also achieved in [Roie Levin and David Wajc, 2021], but only under the simple matching constraint, while we can deal with the more general b-matching constraint. We also consider a generalized problem, where a k-uniform hypergraph is given with an extra matroid constraint imposed on the edges, with the same goal of finding a b-matching that maximizes a submodular function. We extend our technique to this case to obtain an algorithm with an approximation of 8/3k+O(1). Our algorithms build on the ideas of the recent works of Levin and Wajc [Roie Levin and David Wajc, 2021] and of Garg, Jordan, and Svensson [Paritosh Garg et al., 2021]. Our main technical innovation is to introduce a data structure and associate it with each vertex and the matroid, to record the extra information of the stored edges. After the streaming phase, these data structures guide the greedy algorithm to make better choices.
Cite as

Chien-Chung Huang and François Sellier. Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.APPROX/RANDOM.2021.14,
  author =	{Huang, Chien-Chung and Sellier, Fran\c{c}ois},
  title =	{{Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.14},
  URN =		{urn:nbn:de:0030-drops-147072},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.14},
  annote =	{Keywords: Maximum Weight Matching, Submodular Function Maximization, Streaming, Matroid}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.80
Approximating Maximum Integral Multiflows on Bounded Genus Graphs

Authors: Chien-Chung Huang, Mathieu Mari, Claire Mathieu, and Jens Vygen

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.
Cite as

Chien-Chung Huang, Mathieu Mari, Claire Mathieu, and Jens Vygen. Approximating Maximum Integral Multiflows on Bounded Genus Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 80:1-80:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ICALP.2021.80,
  author =	{Huang, Chien-Chung and Mari, Mathieu and Mathieu, Claire and Vygen, Jens},
  title =	{{Approximating Maximum Integral Multiflows on Bounded Genus Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{80:1--80:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela 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.ICALP.2021.80},
  URN =		{urn:nbn:de:0030-drops-141491},
  doi =		{10.4230/LIPIcs.ICALP.2021.80},
  annote =	{Keywords: Multi-commodity flows, approximation algorithms, bounded genus graphs}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.62
Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints

Authors: Chien-Chung Huang, Theophile Thiery, and Justin Ward

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

Abstract
We give improved multi-pass streaming algorithms for the problem of maximizing a monotone or arbitrary non-negative submodular function subject to a general p-matchoid constraint in the model in which elements of the ground set arrive one at a time in a stream. The family of constraints we consider generalizes both the intersection of p arbitrary matroid constraints and p-uniform hypergraph matching. For monotone submodular functions, our algorithm attains a guarantee of p+1+ε using O(p/ε)-passes and requires storing only O(k) elements, where k is the maximum size of feasible solution. This immediately gives an O(1/ε)-pass (2+ε)-approximation for monotone submodular maximization in a matroid and (3+ε)-approximation for monotone submodular matching. Our algorithm is oblivious to the choice ε and can be stopped after any number of passes, delivering the appropriate guarantee. We extend our techniques to obtain the first multi-pass streaming algorithms for general, non-negative submodular functions subject to a p-matchoid constraint. We show that a randomized O(p/ε)-pass algorithm storing O(p³klog(k)/ε³) elements gives a (p+1+γ+O(ε))-approximation, where γ is the guarantee of the best-known offline algorithm for the same problem.
Cite as

Chien-Chung Huang, Theophile Thiery, and Justin Ward. Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.APPROX/RANDOM.2020.62,
  author =	{Huang, Chien-Chung and Thiery, Theophile and Ward, Justin},
  title =	{{Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{62:1--62:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.62},
  URN =		{urn:nbn:de:0030-drops-126657},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.62},
  annote =	{Keywords: submodular maximization, streaming algorithms, matroid, matchoid}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.32
Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint

Authors: Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa

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

Abstract
Given a set D of n unit disks in the plane and an integer k <= n, the maximum area connected subset problem asks for a set D' subseteq D of size k that maximizes the area of the union of disks, under the constraint that this union is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint. We prove that the problem is NP-hard and analyze a greedy algorithm, proving that it is a 1/2-approximation. We then give a polynomial-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of epsilon k disks that are not drawn from the input. Additionally, for two special cases of the problem we design a PTAS without resource augmentation.
Cite as

Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa. Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.APPROX-RANDOM.2019.32,
  author =	{Huang, Chien-Chung and Mari, Mathieu and Mathieu, Claire and Mitchell, Joseph S. B. and Mustafa, Nabil H.},
  title =	{{Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{32:1--32:21},
  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.32},
  URN =		{urn:nbn:de:0030-drops-112471},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.32},
  annote =	{Keywords: approximation algorithm, submodular function optimisation, unit disk graph, connectivity constraint}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.11
Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint

Authors: Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida

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

Abstract
In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to a small fraction of the data stored in primary memory. For this problem, we propose a (0.363-epsilon)-approximation algorithm, requiring only a single pass through the data; moreover, we propose a (0.4-epsilon)-approximation algorithm requiring a constant number of passes through the data. The required memory space of both algorithms depends only on the size of the knapsack capacity and epsilon.
Cite as

Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida. Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.APPROX-RANDOM.2017.11,
  author =	{Huang, Chien-Chung and Kakimura, Naonori and Yoshida, Yuichi},
  title =	{{Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.11},
  URN =		{urn:nbn:de:0030-drops-75602},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.11},
  annote =	{Keywords: submodular functions, single-pass streaming, multiple-pass streaming, constant approximation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.49
A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges

Authors: Chien-Chung Huang and Sebastian Ott

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Makespan minimization in restricted assignment (R|p_{ij} in {p_j, infinity}|C_{max}) is a classical problem in the field of machine scheduling. In a landmark paper, [Lenstra, Shmoys, and Tardos, Math. Progr. 1990] gave a 2-approximation algorithm and proved that the problem cannot be approximated within 1.5 unless P=NP. The upper and lower bounds of the problem have been essentially unimproved in the intervening 25 years, despite several remarkable successful attempts in some special cases of the problem recently. In this paper, we consider a special case called graph-balancing with light hyper edges, where heavy jobs can be assigned to at most two machines while light jobs can be assigned to any number of machines. For this case, we present algorithms with approximation ratios strictly better than 2. Specifically, - Two job sizes: Suppose that light jobs have weight w and heavy jobs have weight W, and w < W. We give a 1.5-approximation algorithm (note that the current 1.5 lower bound is established in an even more restrictive setting). Indeed, depending on the specific values of w and W, sometimes our algorithm guarantees sub-1.5 approximation ratios. - Arbitrary job sizes: Suppose that W is the largest given weight, heavy jobs have weights in the range of (beta W, W], where 4/7 <= beta < 1, and light jobs have weights in the range of (0,beta W]. We present a (5/3+beta/3)-approximation algorithm. Our algorithms are purely combinatorial, without the need of solving a linear program as required in most other known approaches.
Cite as

Chien-Chung Huang and Sebastian Ott. A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ESA.2016.49,
  author =	{Huang, Chien-Chung and Ott, Sebastian},
  title =	{{A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.49},
  URN =		{urn:nbn:de:0030-drops-63919},
  doi =		{10.4230/LIPIcs.ESA.2016.49},
  annote =	{Keywords: Approximation Algorithms, Machine Scheduling, Graph Balancing, Combinatorial Algorithms}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.361
A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties

Authors: Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki, and Hiroki Yanagisawa

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

Abstract
The problem of finding a maximum cardinality stable matching in the presence of ties and unacceptable partners, called MAX SMTI, is a well-studied NP-hard problem. The MAX SMTI is NP-hard even for highly restricted instances where (i) ties appear only in women's preference lists and (ii) each tie appears at the end of each woman's preference list. The current best lower bounds on the approximation ratio for this variant are 1.1052 unless P=NP and 1.25 under the unique games conjecture, while the current best upper bound is 1.4616. In this paper, we improve the upper bound to 1.25, which matches the lower bound under the unique games conjecture. Note that this is the first special case of the MAX SMTI where the tight approximation bound is obtained. The improved ratio is achieved via a new analysis technique, which avoids the complicated case-by-case analysis used in earlier studies. As a by-product of our analysis, we show that the integrality gap of natural IP and LP formulations for this variant is 1.25. We also show that the unrestricted MAX SMTI cannot be approximated with less than 1.5 unless the approximation ratio of a certain special case of the minimum maximal matching problem can be improved.
Cite as

Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki, and Hiroki Yanagisawa. A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 361-380, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.APPROX-RANDOM.2015.361,
  author =	{Huang, Chien-Chung and Iwama, Kazuo and Miyazaki, Shuichi and Yanagisawa, Hiroki},
  title =	{{A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{361--380},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.361},
  URN =		{urn:nbn:de:0030-drops-53123},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.361},
  annote =	{Keywords: stable marriage with ties and incomplete lists, approximation algorithm, integer program, linear program relaxation, integrality gap}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.339
Fair Matchings and Related Problems

Authors: Chien-Chung Huang, Telikepalli Kavitha, Kurt Mehlhorn, and Dimitrios Michail

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract
Let G = (A union B, E) be a bipartite graph, where every vertex ranks its neighbors in an order of preference (with ties allowed) and let r be the worst rank used. A matching M is fair in G if it has maximum cardinality, subject to this, M matches the minimum number of vertices to rank r neighbors, subject to that, M matches the minimum number of vertices to rank (r-1) neighbors, and so on. We show an efficient combinatorial algorithm based on LP duality to compute a fair matching in G. We also show a scaling based algorithm for the fair b-matching problem. Our two algorithms can be extended to solve other profile-based matching problems. In designing our combinatorial algorithm, we show how to solve a generalized version of the minimum weighted vertex cover problem in bipartite graphs, using a single-source shortest paths computation---this can be of independent interest.
Cite as

Chien-Chung Huang, Telikepalli Kavitha, Kurt Mehlhorn, and Dimitrios Michail. Fair Matchings and Related Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 339-350, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.FSTTCS.2013.339,
  author =	{Huang, Chien-Chung and Kavitha, Telikepalli and Mehlhorn, Kurt and Michail, Dimitrios},
  title =	{{Fair Matchings and Related Problems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{339--350},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.339},
  URN =		{urn:nbn:de:0030-drops-43841},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.339},
  annote =	{Keywords: Matching with Preferences, Fairness and Rank-Maximality, Bipartite Vertex Cover, Linear Programming Duality, Complementary Slackness}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2321
Donation Center Location Problem

Authors: Chien-Chung Huang and Zoya Svitkina

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
We introduce and study the {\em donation center location} problem, which has an additional application in network testing and may also be of independent interest as a general graph-theoreticproblem.Given a set of agents and a set of centers, where agents have preferences over centers and centers have capacities, the goal is to open a subset of centers and to assign a maximum-sized subset of agents to their most-preferred open centers, while respecting the capacity constraints. We prove that in general, the problem is hard to approximate within $n^{1/2-\epsilon}$ for any $\epsilon>0$. In view of this, we investigate two special cases. In one, every agent has a bounded number of centers on her preference list, and in the other, all preferences are induced by a line-metric. We present constant-factor approximation algorithms for the former and exact polynomial-time algorithms for the latter. Of particular interest among our techniques are an analysis of the greedy algorithm for a variant of the maximum coverage problem called\emph{frugal coverage}, the use of maximum matching subroutine with subsequent modification, analyzed using a counting argument, and a reduction to the independent set problem on \emph{terminal intersection graphs}, which we show to be a subclass of trapezoid graphs.
Cite as

Chien-Chung Huang and Zoya Svitkina. Donation Center Location Problem. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 227-238, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.FSTTCS.2009.2321,
  author =	{Huang, Chien-Chung and Svitkina, Zoya},
  title =	{{Donation Center Location Problem}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{227--238},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2321},
  URN =		{urn:nbn:de:0030-drops-23212},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2321},
  annote =	{Keywords: Approximation Algorithms, Facility Location, Matching with Preferences}
}
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 Imprint Privacy Contact