Search Results

Documents authored by Cheng, Siu-Wing

Document
DOI: 10.4230/LIPIcs.SoCG.2024.31
Geometric Matching and Bottleneck Problems

Authors: Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Let P be a set of at most n points and let R be a set of at most n geometric ranges, such as disks and rectangles, where each p ∈ P has an associated supply s_{p} > 0, and each r ∈ R has an associated demand d_r > 0. A (many-to-many) matching is a set 𝒜 of ordered triples (p,r,a_{pr}) ∈ P × R × ℝ_{> 0} such that p ∈ r and the a_{pr}’s satisfy the constraints given by the supplies and demands. We show how to compute a maximum matching, that is, a matching maximizing ∑_{(p,r,a_{pr}) ∈ 𝒜} a_{pr}. Using our techniques, we can also solve minimum bottleneck problems, such as computing a perfect matching between a set of n red points P and a set of n blue points Q that minimizes the length of the longest edge. For the L_∞-metric, we can do this in time O(n^{1+ε}) in any fixed dimension, for the L₂-metric in the plane in time O(n^{4/3 + ε}), for any ε > 0.
Cite as

Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer. Geometric Matching and Bottleneck Problems. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.SoCG.2024.31,
  author =	{Cabello, Sergio and Cheng, Siu-Wing and Cheong, Otfried and Knauer, Christian},
  title =	{{Geometric Matching and Bottleneck Problems}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.31},
  URN =		{urn:nbn:de:0030-drops-199768},
  doi =		{10.4230/LIPIcs.SoCG.2024.31},
  annote =	{Keywords: Many-to-many matching, bipartite, planar, geometric, approximation}
}
Document
DOI: 10.4230/DagRep.13.5.165
Computational Geometry (Dagstuhl Seminar 23221)

Authors: Siu-Wing Cheng, Maarten Löffler, Jeff M. Phillips, and Aleksandr Popov

Published in: Dagstuhl Reports, Volume 13, Issue 5 (2023)

Abstract
This report documents the program and the outcomes of the Dagstuhl Seminar 23221 "Computational Geometry". The seminar was held from May 29th to June 2nd, 2023, and 39 participants from various countries attended it, including two remote participants. Recent advances in computational geometry were presented and discussed, and new challenges were identified. This report collects the abstracts of the talks and the open problems presented at the seminar.
Cite as

Siu-Wing Cheng, Maarten Löffler, Jeff M. Phillips, and Aleksandr Popov. Computational Geometry (Dagstuhl Seminar 23221). In Dagstuhl Reports, Volume 13, Issue 5, pp. 165-181, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{cheng_et_al:DagRep.13.5.165,
  author =	{Cheng, Siu-Wing and L\"{o}ffler, Maarten and Phillips, Jeff M. and Popov, Aleksandr},
  title =	{{Computational Geometry (Dagstuhl Seminar 23221)}},
  pages =	{165--181},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{5},
  editor =	{Cheng, Siu-Wing and L\"{o}ffler, Maarten and Phillips, Jeff M. and Popov, Aleksandr},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.5.165},
  URN =		{urn:nbn:de:0030-drops-193692},
  doi =		{10.4230/DagRep.13.5.165},
  annote =	{Keywords: Algorithms, Combinatorics, Geometric Computing, Reconfiguration, Uncertainty}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.40
Approximate Nearest Neighbor for Polygonal Curves Under Fréchet Distance

Authors: Siu-Wing Cheng and Haoqiang Huang

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We propose κ-approximate nearest neighbor (ANN) data structures for n polygonal curves under the Fréchet distance in ℝ^d, where κ ∈ {1+ε,3+ε} and d ≥ 2. We assume that every input curve has at most m vertices, every query curve has at most k vertices, k ≪ m, and k is given for preprocessing. The query times are Õ(k(mn)^{0.5+ε}/ε^d+ k(d/ε)^O(dk)) for (1+ε)-ANN and Õ(k(mn)^{0.5+ε}/ε^d) for (3+ε)-ANN. The space and expected preprocessing time are Õ(k(mnd^d/ε^d)^O(k+1/ε²)) in both cases. In two and three dimensions, we improve the query times to O(1/ε)^O(k) ⋅ Õ(k) for (1+ε)-ANN and Õ(k) for (3+ε)-ANN. The space and expected preprocessing time improve to O(mn/ε)^O(k) ⋅ Õ(k) in both cases. For ease of presentation, we treat factors in our bounds that depend purely on d as O(1). The hidden polylog factors in the big-Õ notation have powers dependent on d.
Cite as

Siu-Wing Cheng and Haoqiang Huang. Approximate Nearest Neighbor for Polygonal Curves Under Fréchet Distance. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ICALP.2023.40,
  author =	{Cheng, Siu-Wing and Huang, Haoqiang},
  title =	{{Approximate Nearest Neighbor for Polygonal Curves Under Fr\'{e}chet Distance}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel 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.2023.40},
  URN =		{urn:nbn:de:0030-drops-180929},
  doi =		{10.4230/LIPIcs.ICALP.2023.40},
  annote =	{Keywords: Polygonal curves, Fr\'{e}chet distance, approximate nearest neighbor}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.8
Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions

Authors: Siu-Wing Cheng and Man Ting Wong

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

Abstract
We propose a self-improving algorithm for computing Voronoi diagrams under a given convex distance function with constant description complexity. The n input points are drawn from a hidden mixture of product distributions; we are only given an upper bound m = o(√n) on the number of distributions in the mixture, and the property that for each distribution, an input instance is drawn from it with a probability of Ω(1/n). For any ε ∈ (0,1), after spending O(mn log^O(1)(mn) + m^ε n^(1+ε) log(mn)) time in a training phase, our algorithm achieves an O(1/ε n log m + 1/ε n 2^O(log^* n) + 1/ε H) expected running time with probability at least 1 - O(1/n), where H is the entropy of the distribution of the Voronoi diagram output. The expectation is taken over the input distribution and the randomized decisions of the algorithm. For the Euclidean metric, the expected running time improves to O(1/ε n log m + 1/ε H).
Cite as

Siu-Wing Cheng and Man Ting Wong. Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ISAAC.2021.8,
  author =	{Cheng, Siu-Wing and Wong, Man Ting},
  title =	{{Self-Improving Voronoi Construction for a Hidden Mixture of Product Distributions}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{8:1--8:13},
  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.8},
  URN =		{urn:nbn:de:0030-drops-154418},
  doi =		{10.4230/LIPIcs.ISAAC.2021.8},
  annote =	{Keywords: entropy, Voronoi diagram, convex distance function, hidden mixture of product distributions}
}
Document
DOI: 10.4230/DagRep.11.4.1
Computational Geometry (Dagstuhl Seminar 21181)

Authors: Siu-Wing Cheng, Anne Driemel, and Jeff M. Phillips

Published in: Dagstuhl Reports, Volume 11, Issue 4 (2021)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21181 "Computational Geometry". The seminar was held from May 2 to May 7, 2021. Because of COVID, the seminar was held online in a virtual manner, and 36 participants from various countries attended it. New advances and directions in computational geometry were presented and discussed. The report collects the abstracts of talks and open problems presented in the seminar.
Cite as

Siu-Wing Cheng, Anne Driemel, and Jeff M. Phillips. Computational Geometry (Dagstuhl Seminar 21181). In Dagstuhl Reports, Volume 11, Issue 4, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{cheng_et_al:DagRep.11.4.1,
  author =	{Cheng, Siu-Wing and Driemel, Anne and Phillips, Jeff M.},
  title =	{{Computational Geometry (Dagstuhl Seminar 21181)}},
  pages =	{1--19},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{4},
  editor =	{Cheng, Siu-Wing and Driemel, Anne and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.4.1},
  URN =		{urn:nbn:de:0030-drops-147963},
  doi =		{10.4230/DagRep.11.4.1},
  annote =	{Keywords: algorithms, computational geometry, Computational topology, data structures, Discrete geometry}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ISAAC.2020
LIPIcs, Volume 181, ISAAC 2020, Complete Volume

Authors: Yixin Cao, Siu-Wing Cheng, and Minming Li

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
LIPIcs, Volume 181, ISAAC 2020, Complete Volume
Cite as

31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 1-1012, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{cao_et_al:LIPIcs.ISAAC.2020,
  title =	{{LIPIcs, Volume 181, ISAAC 2020, Complete Volume}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{1--1012},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020},
  URN =		{urn:nbn:de:0030-drops-133439},
  doi =		{10.4230/LIPIcs.ISAAC.2020},
  annote =	{Keywords: LIPIcs, Volume 181, ISAAC 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ISAAC.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Yixin Cao, Siu-Wing Cheng, and Minming Li

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ISAAC.2020.0,
  author =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.0},
  URN =		{urn:nbn:de:0030-drops-133448},
  doi =		{10.4230/LIPIcs.ISAAC.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.29
A Generalization of Self-Improving Algorithms

Authors: Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin, and Man Ting Wong

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

Abstract
Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances x₁,⋯,x_n follow some unknown product distribution. That is, x_i comes from a fixed unknown distribution 𝒟_i, and the x_i’s are drawn independently. After spending O(n^{1+ε}) time in a learning phase, the subsequent expected running time is O((n+ H)/ε), where H ∈ {H_S,H_DT}, and H_S and H_DT are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the x_i’s under the group product distribution. There is a hidden partition of [1,n] into groups; the x_i’s in the k-th group are fixed unknown functions of the same hidden variable u_k; and the u_k’s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map u_k to x_i’s are well-behaved. After an O(poly(n))-time training phase, we achieve O(n + H_S) and O(nα(n) + H_DT) expected running times for sorting and DT, respectively, where α(⋅) is the inverse Ackermann function.
Cite as

Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin, and Man Ting Wong. A Generalization of Self-Improving Algorithms. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.SoCG.2020.29,
  author =	{Cheng, Siu-Wing and Chiu, Man-Kwun and Jin, Kai and Wong, Man Ting},
  title =	{{A Generalization of Self-Improving Algorithms}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{29:1--29:13},
  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.29},
  URN =		{urn:nbn:de:0030-drops-121873},
  doi =		{10.4230/LIPIcs.SoCG.2020.29},
  annote =	{Keywords: expected running time, entropy, sorting, Delaunay triangulation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.30
Dynamic Distribution-Sensitive Point Location

Authors: Siu-Wing Cheng and Man-Kit Lau

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

Abstract
We propose a dynamic data structure for the distribution-sensitive point location problem. Suppose that there is a fixed query distribution in ℝ², and we are given an oracle that can return in O(1) time the probability of a query point falling into a polygonal region of constant complexity. We can maintain a convex subdivision S with n vertices such that each query is answered in O(OPT) expected time, where OPT is the minimum expected time of the best linear decision tree for point location in S. The space and construction time are O(n log² n). An update of S as a mixed sequence of k edge insertions and deletions takes O(k log⁵ n) amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of n sites can be performed in O(n log⁵ n) expected time so that, during the incremental construction, a nearest neighbor query at any time can be answered optimally with respect to the intermediate Voronoi diagram at that time.
Cite as

Siu-Wing Cheng and Man-Kit Lau. Dynamic Distribution-Sensitive Point Location. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.SoCG.2020.30,
  author =	{Cheng, Siu-Wing and Lau, Man-Kit},
  title =	{{Dynamic Distribution-Sensitive Point Location}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{30:1--30:13},
  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.30},
  URN =		{urn:nbn:de:0030-drops-121882},
  doi =		{10.4230/LIPIcs.SoCG.2020.30},
  annote =	{Keywords: dynamic planar point location, convex subdivision, linear decision tree}
}
Document
DOI: 10.4230/DagRep.9.4.107
Computational Geometry (Dagstuhl Seminar 19181)

Authors: Siu-Wing Cheng, Anne Driemel, and Jeff Erickson

Published in: Dagstuhl Reports, Volume 9, Issue 4 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19181 "Computational Geometry". The seminar was held from April 28 to May 3, 2019 and 40 participants from various countries attended it. New advances and directions in computational geometry were presented and discussed. The report collects the abstracts of talks and open problems presented in the seminar.
Cite as

Siu-Wing Cheng, Anne Driemel, and Jeff Erickson. Computational Geometry (Dagstuhl Seminar 19181). In Dagstuhl Reports, Volume 9, Issue 4, pp. 107-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{cheng_et_al:DagRep.9.4.107,
  author =	{Cheng, Siu-Wing and Driemel, Anne and Erickson, Jeff},
  title =	{{Computational Geometry (Dagstuhl Seminar 19181)}},
  pages =	{107--123},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{4},
  editor =	{Cheng, Siu-Wing and Driemel, Anne and Erickson, Jeff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.4.107},
  URN =		{urn:nbn:de:0030-drops-113064},
  doi =		{10.4230/DagRep.9.4.107},
  annote =	{Keywords: Computational geometry, polynomial partition, geometric data structures, approximation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.38
Restricted Max-Min Allocation: Approximation and Integrality Gap

Authors: Siu-Wing Cheng and Yuchen Mao

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Asadpour, Feige, and Saberi proved that the integrality gap of the configuration LP for the restricted max-min allocation problem is at most 4. However, their proof does not give a polynomial-time approximation algorithm. A lot of efforts have been devoted to designing an efficient algorithm whose approximation ratio can match this upper bound for the integrality gap. In ICALP 2018, we present a (6 + delta)-approximation algorithm where delta can be any positive constant, and there is still a gap of roughly 2. In this paper, we narrow the gap significantly by proposing a (4+delta)-approximation algorithm where delta can be any positive constant. The approximation ratio is with respect to the optimal value of the configuration LP, and the running time is poly(m,n)* n^{poly(1/(delta))} where n is the number of players and m is the number of resources. We also improve the upper bound for the integrality gap of the configuration LP to 3 + 21/26 =~ 3.808.
Cite as

Siu-Wing Cheng and Yuchen Mao. Restricted Max-Min Allocation: Approximation and Integrality Gap. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ICALP.2019.38,
  author =	{Cheng, Siu-Wing and Mao, Yuchen},
  title =	{{Restricted Max-Min Allocation: Approximation and Integrality Gap}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{38:1--38:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.38},
  URN =		{urn:nbn:de:0030-drops-106143},
  doi =		{10.4230/LIPIcs.ICALP.2019.38},
  annote =	{Keywords: fair allocation, configuration LP, approximation, integrality gap}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.63
Extensions of Self-Improving Sorters

Authors: Siu-Wing Cheng and Lie Yan

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Ailon et al. (SICOMP 2011) proposed a self-improving sorter that tunes its performance to the unknown input distribution in a training phase. The distribution of the input numbers x_1,x_2,...,x_n must be of the product type, that is, each x_i is drawn independently from an arbitrary distribution D_i, and the D_i's are independent of each other. We study two extensions that relax this requirement. The first extension models hidden classes in the input. We consider the case that numbers in the same class are governed by linear functions of the same hidden random parameter. The second extension considers a hidden mixture of product distributions.
Cite as

Siu-Wing Cheng and Lie Yan. Extensions of Self-Improving Sorters. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 63:1-63:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ISAAC.2018.63,
  author =	{Cheng, Siu-Wing and Yan, Lie},
  title =	{{Extensions of Self-Improving Sorters}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{63:1--63:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.63},
  URN =		{urn:nbn:de:0030-drops-100111},
  doi =		{10.4230/LIPIcs.ISAAC.2018.63},
  annote =	{Keywords: sorting, self-improving algorithms, entropy}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.37
Restricted Max-Min Fair Allocation

Authors: Siu-Wing Cheng and Yuchen Mao

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
The restricted max-min fair allocation problem seeks an allocation of resources to players that maximizes the minimum total value obtained by any player. It is NP-hard to approximate the problem to a ratio less than 2. Comparing the current best algorithm for estimating the optimal value with the current best for constructing an allocation, there is quite a gap between the ratios that can be achieved in polynomial time: 4+delta for estimation and 6 + 2 sqrt{10} + delta ~~ 12.325 + delta for construction, where delta is an arbitrarily small constant greater than 0. We propose an algorithm that constructs an allocation with value within a factor 6 + delta from the optimum for any constant delta > 0. The running time is polynomial in the input size for any constant delta chosen.
Cite as

Siu-Wing Cheng and Yuchen Mao. Restricted Max-Min Fair Allocation. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ICALP.2018.37,
  author =	{Cheng, Siu-Wing and Mao, Yuchen},
  title =	{{Restricted Max-Min Fair Allocation}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{37:1--37:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.37},
  URN =		{urn:nbn:de:0030-drops-90418},
  doi =		{10.4230/LIPIcs.ICALP.2018.37},
  annote =	{Keywords: Fair allocation, approximation, local search}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.30
Adaptive Planar Point Location

Authors: Siu-Wing Cheng and Man-Kit Lau

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
We present a self-adjusting point location structure for convex subdivisions. Let n be the number of vertices in a convex subdivision S. Our structure for S uses O(n) space and processes any online query sequence sigma in O(n + OPT) time, where OPT is the minimum time required by any linear decision tree for answering point location queries in S to process sigma. The O(n + OPT) time bound includes the preprocessing time. Our result is a two-dimensional analog of the static optimality property of splay trees. For connected subdivisions, we achieve a processing time of O(|sigma| log log n + n + OPT).
Cite as

Siu-Wing Cheng and Man-Kit Lau. Adaptive Planar Point Location. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.SoCG.2017.30,
  author =	{Cheng, Siu-Wing and Lau, Man-Kit},
  title =	{{Adaptive Planar Point Location}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.30},
  URN =		{urn:nbn:de:0030-drops-71897},
  doi =		{10.4230/LIPIcs.SoCG.2017.30},
  annote =	{Keywords: point location, planar subdivision, static optimality}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.63
Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties

Authors: Juyoung Yon, Sang Won Bae, Siu-Wing Cheng, Otfried Cheong, and Bryan T. Wilkinson

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
The symmetric difference is a robust operator for measuring the error of approximating one shape by another. Given two convex shapes P and C, we study the problem of minimizing the volume of their symmetric difference under all possible scalings and translations of C. We prove that the problem can be solved by convex programming. We also present a combinatorial algorithm for convex polygons in the plane that runs in O((m+n) log^3(m+n)) expected time, where n and m denote the number of vertices of P and C, respectively.
Cite as

Juyoung Yon, Sang Won Bae, Siu-Wing Cheng, Otfried Cheong, and Bryan T. Wilkinson. Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{yon_et_al:LIPIcs.SoCG.2016.63,
  author =	{Yon, Juyoung and Bae, Sang Won and Cheng, Siu-Wing and Cheong, Otfried and Wilkinson, Bryan T.},
  title =	{{Approximating Convex Shapes With Respect to Symmetric Difference Under Homotheties}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{63:1--63:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.63},
  URN =		{urn:nbn:de:0030-drops-59551},
  doi =		{10.4230/LIPIcs.SoCG.2016.63},
  annote =	{Keywords: shape matching, convexity, symmetric difference, homotheties}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.498
Overlap of Convex Polytopes under Rigid Motion

Authors: Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, and Juyoung Yon

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

Abstract
We present an algorithm to compute an approximate overlap of two convex polytopes P_1 and P_2 in R^3 under rigid motion. Given any epsilon in (0,1/2], our algorithm runs in O(epsilon^{-3}n log^{3.5}n) time with probability 1 - n^{-O(1)} and returns a (1-epsilon)-approximate maximum overlap, provided that the maximum overlap is at least lambda max(|P_1|,|P_2|) for some given constant lambda in (0,1].
Cite as

Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon, and Juyoung Yon. Overlap of Convex Polytopes under Rigid Motion. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 498-509, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.FSTTCS.2012.498,
  author =	{Ahn, Hee-Kap and Cheng, Siu-Wing and Kweon, Hyuk Jun and Yon, Juyoung},
  title =	{{Overlap of Convex Polytopes under Rigid Motion}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{498--509},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.498},
  URN =		{urn:nbn:de:0030-drops-38845},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.498},
  annote =	{Keywords: convex polytope, overlap, approximation, rigid motion}
}
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