4 Search Results for "Shin, Chan-Su"


Document
Inscribing or Circumscribing a Histogon to a Convex Polygon

Authors: Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)


Abstract
We consider two optimization problems of approximating a convex polygon, one by a largest inscribed histogon and the other by a smallest circumscribed histogon. An axis-aligned histogon is an axis-aligned rectilinear polygon such that every horizontal edge has an integer length. A histogon of orientation θ is a copy of an axis-aligned histogon rotated by θ in counterclockwise direction. The goal is to find a largest inscribed histogon and a smallest circumscribed histogon over all orientations in [0,π). Depending on whether the horizontal width of a histogon is predetermined or not, we consider several different versions of the problem and present exact algorithms. These optimization problems belong to shape analysis, classification, and simplification, and they have applications in various cost-optimization problems.

Cite as

Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn. Inscribing or Circumscribing a Histogon to a Convex Polygon. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.FSTTCS.2022.13,
  author =	{Chung, Jaehoon and Bae, Sang Won and Shin, Chan-Su and Yoon, Sang Duk and Ahn, Hee-Kap},
  title =	{{Inscribing or Circumscribing a Histogon to a Convex Polygon}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.13},
  URN =		{urn:nbn:de:0030-drops-174054},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.13},
  annote =	{Keywords: Shape simplification, Shape analysis, Histogon, Convex polygon}
}
Document
Making Three out of Two: Three-Way Online Correlated Selection

Authors: Yongho Shin and Hyung-Chan An

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


Abstract
Two-way online correlated selection (two-way OCS) is an online algorithm that, at each timestep, takes a pair of elements from the ground set and irrevocably chooses one of the two elements, while ensuring negative correlation in the algorithm's choices. Whilst OCS was initially invented by Fahrbach, Huang, Tao, and Zadimoghaddam to break a natural long-standing barrier in the edge-weighted online bipartite matching problem, it is an interesting technique on its own due to its capability of introducing a powerful algorithmic tool, namely negative correlation, to online algorithms. As such, Fahrbach et al. posed two tantalizing open questions in their paper, one of which was the following: Can we obtain n-way OCS for n > 2, in which the algorithm can be given n > 2 elements to choose from at each timestep? In this paper, we affirmatively answer this open question by presenting a three-way OCS. Our algorithm uses two-way OCS as its building block and is simple to describe; however, as it internally runs two instances of two-way OCS, one of which is fed with the output of the other, the final output probability distribution becomes highly elusive. We tackle this difficulty by approximating the output distribution of OCS by a flat, less correlated function and using it as a safe "surrogate" of the real distribution. Our three-way OCS also yields a 0.5093-competitive algorithm for edge-weighted online matching, demonstrating its usefulness.

Cite as

Yongho Shin and Hyung-Chan An. Making Three out of Two: Three-Way Online Correlated Selection. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 49:1-49:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{shin_et_al:LIPIcs.ISAAC.2021.49,
  author =	{Shin, Yongho and An, Hyung-Chan},
  title =	{{Making Three out of Two: Three-Way Online Correlated Selection}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{49:1--49:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.49},
  URN =		{urn:nbn:de:0030-drops-154822},
  doi =		{10.4230/LIPIcs.ISAAC.2021.49},
  annote =	{Keywords: online correlated selection, multi-way OCS, online algorithms, negative correlation, edge-weighted online bipartite matching}
}
Document
Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem

Authors: Kangsan Kim, Yongho Shin, and Hyung-Chan An

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


Abstract
Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement - odd, even, or unconstrained - of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse T-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound.

Cite as

Kangsan Kim, Yongho Shin, and Hyung-Chan An. Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.ISAAC.2020.21,
  author =	{Kim, Kangsan and Shin, Yongho and An, Hyung-Chan},
  title =	{{Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{21:1--21:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.21},
  URN =		{urn:nbn:de:0030-drops-133652},
  doi =		{10.4230/LIPIcs.ISAAC.2020.21},
  annote =	{Keywords: Facility location problems, approximation algorithms, clustering problems, parity constraints}
}
Document
Tree Drawings Revisited

Authors: Timothy M. Chan

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)


Abstract
We make progress on a number of open problems concerning the area requirement for drawing trees on a grid. We prove that 1) every tree of size n (with arbitrarily large degree) has a straight-line drawing with area n2^{O(sqrt{log log n log log log n})}, improving the longstanding O(n log n) bound; 2) every tree of size n (with arbitrarily large degree) has a straight-line upward drawing with area n sqrt{log n}(log log n)^{O(1)}, improving the longstanding O(n log n) bound; 3) every binary tree of size n has a straight-line orthogonal drawing with area n2^{O(log^*n)}, improving the previous O(n log log n) bound by Shin, Kim, and Chwa (1996) and Chan, Goodrich, Kosaraju, and Tamassia (1996); 4) every binary tree of size n has a straight-line order-preserving drawing with area n2^{O(log^*n)}, improving the previous O(n log log n) bound by Garg and Rusu (2003); 5) every binary tree of size n has a straight-line orthogonal order-preserving drawing with area n2^{O(sqrt{log n})}, improving the O(n^{3/2}) previous bound by Frati (2007).

Cite as

Timothy M. Chan. Tree Drawings Revisited. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chan:LIPIcs.SoCG.2018.23,
  author =	{Chan, Timothy M.},
  title =	{{Tree Drawings Revisited}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.23},
  URN =		{urn:nbn:de:0030-drops-87364},
  doi =		{10.4230/LIPIcs.SoCG.2018.23},
  annote =	{Keywords: graph drawing, trees, recursion}
}
  • Refine by Author
  • 2 An, Hyung-Chan
  • 2 Shin, Yongho
  • 1 Ahn, Hee-Kap
  • 1 Bae, Sang Won
  • 1 Chan, Timothy M.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 Convex polygon
  • 1 Facility location problems
  • 1 Histogon
  • 1 Shape analysis
  • 1 Shape simplification
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2018
  • 1 2020
  • 1 2021
  • 1 2022

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