82 Search Results for "Bae, Sang Won"

Volume

LIPIcs, Volume 248

33rd International Symposium on Algorithms and Computation (ISAAC 2022)

ISAAC 2022, December 19-21, 2022, Seoul, Korea

Editors: Sang Won Bae and Heejin Park

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.5
Constrained Two-Line Center Problems

Authors: Taehoon Ahn and Sang Won Bae

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Given a set P of n points in the plane, the two-line center problem asks to find two lines that minimize the maximum distance from each point in P to its closer one of the two resulting lines. The currently best algorithm for the problem takes O(n² log² n) time by Jaromczyk and Kowaluk in 1995. In this paper, we present faster algorithms for three variants of the two-line center problem in which the orientations of the resulting lines are constrained. Specifically, our algorithms solve the problem in O(n log n) time when the orientations of both lines are fixed; in O(n log³ n) time when the orientation of one line is fixed; and in O(n² α(n) log n) time when the angle between the two lines is fixed, where α(n) denotes the inverse Ackermann function.
Cite as

Taehoon Ahn and Sang Won Bae. Constrained Two-Line Center Problems. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2024.5,
  author =	{Ahn, Taehoon and Bae, Sang Won},
  title =	{{Constrained Two-Line Center Problems}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.5},
  URN =		{urn:nbn:de:0030-drops-221327},
  doi =		{10.4230/LIPIcs.ISAAC.2024.5},
  annote =	{Keywords: two-line center problem, geometric location problem, geometric optimization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.2
Indexing Graphs for Shortest Beer Path Queries

Authors: David Coudert, Andrea D'Ascenzo, and Mattia D'Emidio

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract
A beer graph is an edge-weighted graph G = (V,E,ω) with beer vertices B ⊆ V. A beer path between two vertices s and t of a beer graph is a path that connects s and t and visits at least one vertex in B. The beer distance between two vertices is the weight of a shortest beer path, i.e. a beer path having minimum total weight. A graph indexing scheme is a two-phase method that constructs an index data structure by a one-time preprocessing of an input graph and then exploits it to compute (or accelerate the computation of) answers to queries on structures of the graph dataset. In the last decade, such indexing schemes have been designed to perform, effectively, many relevant types of queries, e.g. on reachability, and have gained significant popularity in essentially all data-intensive application domains where large number of queries have to be routinely answered (e.g. journey planners), since they have been shown, through many experimental studies, to offer extremely low query times at the price of limited preprocessing time and space overheads. In this paper, we showcase that an indexing scheme, to efficiently execute queries on beer distances or shortest beer paths for pairs of vertices of a beer graph, can be obtained by adapting the highway labeling, a recently introduced indexing method to accelerate the computation of classical shortest paths. We design a preprocessing algorithm to build a whl index, i.e. a weighted highway labeling of a beer graph, and show how it can be queried to compute beer distances and shortest beer paths. Through extensive experimentation on real networks, we empirically demonstrate its practical effectiveness and superiority, in terms of offered trade-off between preprocessing time, space overhead and query time, with respect to the state-of-the-art.
Cite as

David Coudert, Andrea D'Ascenzo, and Mattia D'Emidio. Indexing Graphs for Shortest Beer Path Queries. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{coudert_et_al:OASIcs.ATMOS.2024.2,
  author =	{Coudert, David and D'Ascenzo, Andrea and D'Emidio, Mattia},
  title =	{{Indexing Graphs for Shortest Beer Path Queries}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{2:1--2:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.2},
  URN =		{urn:nbn:de:0030-drops-211907},
  doi =		{10.4230/OASIcs.ATMOS.2024.2},
  annote =	{Keywords: Graph Algorithms, Indexing Schemes, Beer Distances, Algorithms Engineering}
}
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
Complete Volume
DOI: 10.4230/LIPIcs.ISAAC.2022
LIPIcs, Volume 248, ISAAC 2022, Complete Volume

Authors: Sang Won Bae and Heejin Park

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
LIPIcs, Volume 248, ISAAC 2022, Complete Volume
Cite as

33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 1-1080, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Proceedings{bae_et_al:LIPIcs.ISAAC.2022,
  title =	{{LIPIcs, Volume 248, ISAAC 2022, Complete Volume}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{1--1080},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022},
  URN =		{urn:nbn:de:0030-drops-172849},
  doi =		{10.4230/LIPIcs.ISAAC.2022},
  annote =	{Keywords: LIPIcs, Volume 248, ISAAC 2022, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ISAAC.2022.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Sang Won Bae and Heejin Park

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

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

33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bae_et_al:LIPIcs.ISAAC.2022.0,
  author =	{Bae, Sang Won and Park, Heejin},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.0},
  URN =		{urn:nbn:de:0030-drops-172858},
  doi =		{10.4230/LIPIcs.ISAAC.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2022.1
Succinct Representations of Graphs (Invited Talk)

Authors: Kunihiko Sadakane

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We consider the problem of finding succinct representations of graphs, that is, encodings using asymptotically the minimum number of bits which support queries on the graphs efficiently. For a special class of graphs, there exist many theoretical results and practical implementations on ordered trees. On the other hand, for wider classes of graphs, though there are many results on counting the number of non-isomorphic graphs belonging to a graph class, there were few number of results on their succinct representations until recently. In this talk, we review some recent results on succinct representations of graphs such as interval, permutation, circle, circular-arc, trapezoid, circle-trapezoid, k-polygon, circle-polygon, cograph, separable, ptolemaic, distance hereditary, clique width k, block, cactus, series-parallel, planar, tree width k, path, boxicity k, chordal bipartite, strongly chordal, chordal graphs, etc.
Cite as

Kunihiko Sadakane. Succinct Representations of Graphs (Invited Talk). In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{sadakane:LIPIcs.ISAAC.2022.1,
  author =	{Sadakane, Kunihiko},
  title =	{{Succinct Representations of Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.1},
  URN =		{urn:nbn:de:0030-drops-172865},
  doi =		{10.4230/LIPIcs.ISAAC.2022.1},
  annote =	{Keywords: Graph Enumeration, Succinct Data Structure, Compression}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2022.2
The Tragedy of Being Almost but Not Quite Planar (Invited Talk)

Authors: Jeff Erickson

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Planar graphs have been fertile grounds for algorithms research for decades, both because they model several types of real-world networks, and because they admit simpler and and faster algorithms than arbitrary graphs. Many important structural properties of planar graphs extend naturally to graphs that embed on more complex surfaces. As a result, efficient algorithms for planar graphs often extend naturally to higher-genus surface graphs with little or no modification. I will describe a few of my favorite exceptions to this rule - classical problems that admit simple, efficient, and practical algorithms for planar graphs, but where algorithms for graphs on other surfaces are significantly slower and/or more complex.
Cite as

Jeff Erickson. The Tragedy of Being Almost but Not Quite Planar (Invited Talk). In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{erickson:LIPIcs.ISAAC.2022.2,
  author =	{Erickson, Jeff},
  title =	{{The Tragedy of Being Almost but Not Quite Planar}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.2},
  URN =		{urn:nbn:de:0030-drops-172875},
  doi =		{10.4230/LIPIcs.ISAAC.2022.2},
  annote =	{Keywords: planar graphs, surface graphs, algorithms, open problems}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.3
A Local Search Algorithm for the Min-Sum Submodular Cover Problem

Authors: Lisa Hellerstein, Thomas Lidbetter, and R. Teal Witter

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We consider the problem of solving the Min-Sum Submodular Cover problem using local search. The Min-Sum Submodular Cover problem generalizes the NP-complete Min-Sum Set Cover problem, replacing the input set cover instance with a monotone submodular set function. A simple greedy algorithm achieves an approximation factor of 4, which is tight unless P=NP [Streeter and Golovin, NeurIPS, 2008]. We complement the greedy algorithm with analysis of a local search algorithm. Building on work of Munagala et al. [ICDT, 2005], we show that, using simple initialization, a straightforward local search algorithm achieves a (4+ε)-approximate solution in time O(n³log(n/ε)), provided that the monotone submodular set function is also second-order supermodular. Second-order supermodularity has been shown to hold for a number of submodular functions of practical interest, including functions associated with set cover, matching, and facility location. We present experiments on two special cases of Min-Sum Submodular Cover and find that the local search algorithm can outperform the greedy algorithm on small data sets.
Cite as

Lisa Hellerstein, Thomas Lidbetter, and R. Teal Witter. A Local Search Algorithm for the Min-Sum Submodular Cover Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hellerstein_et_al:LIPIcs.ISAAC.2022.3,
  author =	{Hellerstein, Lisa and Lidbetter, Thomas and Witter, R. Teal},
  title =	{{A Local Search Algorithm for the Min-Sum Submodular Cover Problem}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{3:1--3:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.3},
  URN =		{urn:nbn:de:0030-drops-172880},
  doi =		{10.4230/LIPIcs.ISAAC.2022.3},
  annote =	{Keywords: Local search, submodularity, second-order supermodularity, min-sum set cover}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.4
Algorithms for Coloring Reconfiguration Under Recolorability Digraphs

Authors: Soichiro Fujii, Yuni Iwamasa, Kei Kimura, and Akira Suzuki

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
In the k-Recoloring problem, we are given two (vertex-)colorings of a graph using k colors, and asked to transform one into the other by recoloring only one vertex at a time, while at all times maintaining a proper k-coloring. This problem is known to be solvable in polynomial time if k ≤ 3, and is PSPACE-complete if k ≥ 4. In this paper, we consider a (directed) recolorability constraint on the k colors, which forbids some pairs of colors to be recolored directly. The recolorability constraint is given in terms of a digraph R, whose vertices correspond to the colors and whose arcs represent the pairs of colors that can be recolored directly. We provide algorithms for the problem based on the structure of recolorability constraints R, showing that the problem is solvable in linear time when R is a directed cycle or is in a class of multitrees.
Cite as

Soichiro Fujii, Yuni Iwamasa, Kei Kimura, and Akira Suzuki. Algorithms for Coloring Reconfiguration Under Recolorability Digraphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fujii_et_al:LIPIcs.ISAAC.2022.4,
  author =	{Fujii, Soichiro and Iwamasa, Yuni and Kimura, Kei and Suzuki, Akira},
  title =	{{Algorithms for Coloring Reconfiguration Under Recolorability Digraphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.4},
  URN =		{urn:nbn:de:0030-drops-172896},
  doi =		{10.4230/LIPIcs.ISAAC.2022.4},
  annote =	{Keywords: combinatorial reconfiguration, graph coloring, recolorability, recoloring}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.5
Algorithms for Landmark Hub Labeling

Authors: Sabine Storandt

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Landmark-based routing and Hub Labeling (HL) are shortest path planning techniques, both of which rely on storing shortest path distances between selected pairs of nodes in a preprocessing phase to accelerate query answering. In Landmark-based routing, stored distances to landmark nodes are used to obtain distance lower bounds that guide A* search from node s to node t. With HL, tight upper bounds for shortest path distances between any s-t-pair can be interfered from their stored node labels, making HL an efficient distance oracle. However, for shortest path retrieval, the oracle has to be called once per edge in said path. Furthermore, HL often suffers from a large space consumption as many node pair distances have to be stored in the labels to allow for correct query answering. In this paper, we propose a novel technique, called Landmark Hub Labeling (LHL), which integrates the landmark concept into HL. We prove better worst-case path retrieval times for LHL in case it is path-consistent (a new labeling property we introduce). Moreover, we design efficient (approximation) algorithms that produce path-consistent LHL with small label size and provide parametrized upper bounds, depending on the highway dimension h or the geodesic transversal number gt of the graph. Finally, we show that the space consumption of LHL is smaller than that of (hierarchical) HL, both in theory and in experiments on real-world road networks.
Cite as

Sabine Storandt. Algorithms for Landmark Hub Labeling. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{storandt:LIPIcs.ISAAC.2022.5,
  author =	{Storandt, Sabine},
  title =	{{Algorithms for Landmark Hub Labeling}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.5},
  URN =		{urn:nbn:de:0030-drops-172901},
  doi =		{10.4230/LIPIcs.ISAAC.2022.5},
  annote =	{Keywords: Hub Labeling, Landmark, Geodesic, Hitting Set, Highway Dimension}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.6
An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes

Authors: Atsuya Hasegawa and François Le Gall

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 2020) have shown that there exists an oracle 𝒪 such that BQP^𝒪 ≠ (BPP^BQNC)^𝒪 ∪ (BQNC^BPP)^𝒪. In fact, Chia et al. proved a stronger statement: for any depth parameter d, there exists an oracle that separates quantum depth d and 2d+1, when polynomial-time classical computation is allowed. This implies that relative to an oracle, doubling quantum depth gives classical and quantum hybrid schemes more computational power. In this paper, we show that for any depth parameter d, there exists an oracle that separates quantum depth d and d+1, when polynomial-time classical computation is allowed. This gives an optimal oracle separation of classical and quantum hybrid schemes. To prove our result, we consider d-Bijective Shuffling Simon’s Problem (which is a variant of d-Shuffling Simon’s Problem considered by Chia et al.) and an oracle inspired by an "in-place" permutation oracle.
Cite as

Atsuya Hasegawa and François Le Gall. An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hasegawa_et_al:LIPIcs.ISAAC.2022.6,
  author =	{Hasegawa, Atsuya and Le Gall, Fran\c{c}ois},
  title =	{{An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.6},
  URN =		{urn:nbn:de:0030-drops-172918},
  doi =		{10.4230/LIPIcs.ISAAC.2022.6},
  annote =	{Keywords: small-depth quantum circuit, hybrid quantum computer, oracle separation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.7
Approximating the Minimum Logarithmic Arrangement Problem

Authors: Julián Mestre and Sergey Pupyrev

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We study a graph reordering problem motivated by compressing massive graphs such as social networks and inverted indexes. Given a graph, G = (V, E), the Minimum Logarithmic Arrangement problem is to find a permutation, π, of the vertices that minimizes ∑_{(u, v) ∈ E} (1 + ⌊ lg |π(u) - π(v)| ⌋). This objective has been shown to be a good measure of how many bits are needed to encode the graph if the adjacency list of each vertex is encoded using relative positions of two consecutive neighbors under the π order in the list rather than using absolute indices or node identifiers, which requires at least lg n bits per edge. We show the first non-trivial approximation factor for this problem by giving a polynomial time 𝒪(log k)-approximation algorithm for graphs with treewidth k.
Cite as

Julián Mestre and Sergey Pupyrev. Approximating the Minimum Logarithmic Arrangement Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mestre_et_al:LIPIcs.ISAAC.2022.7,
  author =	{Mestre, Juli\'{a}n and Pupyrev, Sergey},
  title =	{{Approximating the Minimum Logarithmic Arrangement Problem}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.7},
  URN =		{urn:nbn:de:0030-drops-172924},
  doi =		{10.4230/LIPIcs.ISAAC.2022.7},
  annote =	{Keywords: approximation algorithms, graph compression}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.8
Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP

Authors: Zachary Friggstad and Ramin Mousavi

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We initiate the study of the Bounded-Degree Subset Traveling Salesman problem (BDSTSP) in which we are given a graph G = (V,E) with edge cost c_e ≥ 0 on each edge e, degree bounds b_v ≥ 0 on each vertex v ∈ V and a subset of terminals X ⊆ V. The goal is to find a minimum-cost closed walk that spans all terminals and visits each vertex v ∈ V at most b_v/2 times. In this paper, we study bi-criteria approximations that find tours whose cost is within a constant-factor of the optimum tour length while violating the bounds b_v at each vertex by additive quantities. If X = V, an adaptation of the Christofides-Serdyukov algorithm yields a (3/2, +4)-approximation, that is the tour passes through each vertex at most b_v/2+2 times (the degree of v in the multiset of edges on the tour being at most b_v + 4). This is enabled through known results in bounded-degree Steiner trees and integrality of the bounded-degree Y-join polytope. The general case X ≠ V is more challenging since we cannot pass to the metric completion on X. However, it is at least simple to get a (5/3, +4)-bicriteria approximation by using ideas similar to Hoogeveen’s TSP-Path algorithm. Our main result is an improved approximation with marginally worse violations of the vertex bounds: a (13/8, +6)-approximation. We obtain this primarily through adapting the bounded-degree Steiner tree approximation to ensure certain "dangerous" nodes always have even degree in the resulting tree which allows us to bound the cost of the resulting degree-bounded Y-join. We also recover a (3/2, +8)-approximation for this general case.
Cite as

Zachary Friggstad and Ramin Mousavi. Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.ISAAC.2022.8,
  author =	{Friggstad, Zachary and Mousavi, Ramin},
  title =	{{Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.8},
  URN =		{urn:nbn:de:0030-drops-172932},
  doi =		{10.4230/LIPIcs.ISAAC.2022.8},
  annote =	{Keywords: Linear programming, approximation algorithms, combinatorial optimization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.9
Budgeted Out-Tree Maximization with Submodular Prizes

Authors: Gianlorenzo D'Angelo, Esmaeil Delfaraz, and Hugo Gilbert

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We consider a variant of the prize collecting Steiner tree problem in which we are given a directed graph D = (V,A), a monotone submodular prize function p:2^V → ℝ^+ ∪ {0}, a cost function c:V → ℤ^+, a root vertex r ∈ V, and a budget B. The aim is to find an out-subtree T of D rooted at r that costs at most B and maximizes the prize function. We call this problem Directed Rooted Submodular Tree (DRST). For the case of undirected graphs and additive prize functions, Moss and Rabani [SIAM J. Comput. 2007] gave an algorithm that guarantees an O(log|V|)-approximation factor if a violation by a factor 2 of the budget constraint is allowed. Bateni et al. [SIAM J. Comput. 2018] improved the budget violation factor to 1+ε at the cost of an additional approximation factor of O(1/ε²), for any ε ∈ (0,1]. For directed graphs, Ghuge and Nagarajan [SODA 2020] gave an optimal quasi-polynomial time O({log n'}/{log log n'})-approximation algorithm, where n' is the number of vertices in an optimal solution, for the case in which the costs are associated to the edges. In this paper, we give a polynomial time algorithm for DRST that guarantees an approximation factor of O(√B/ε³) at the cost of a budget violation of a factor 1+ε, for any ε ∈ (0,1]. The same result holds for the edge-cost case, to the best of our knowledge this is the first polynomial time approximation algorithm for this case. We further show that the unrooted version of DRST can be approximated to a factor of O(√B) without budget violation, which is an improvement over the factor O(Δ √B) given in [Kuo et al. IEEE/ACM Trans. Netw. 2015] for the undirected and unrooted case, where Δ is the maximum degree of the graph. Finally, we provide some new/improved approximation bounds for several related problems, including the additive-prize version of DRST, the maximum budgeted connected set cover problem, and the budgeted sensor cover problem.
Cite as

Gianlorenzo D'Angelo, Esmaeil Delfaraz, and Hugo Gilbert. Budgeted Out-Tree Maximization with Submodular Prizes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dangelo_et_al:LIPIcs.ISAAC.2022.9,
  author =	{D'Angelo, Gianlorenzo and Delfaraz, Esmaeil and Gilbert, Hugo},
  title =	{{Budgeted Out-Tree Maximization with Submodular Prizes}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.9},
  URN =		{urn:nbn:de:0030-drops-172945},
  doi =		{10.4230/LIPIcs.ISAAC.2022.9},
  annote =	{Keywords: Prize Collecting Steiner Tree, Directed graphs, Approximation Algorithms, Budgeted Problem}
}
  • Refine by Author
  • 11 Bae, Sang Won
  • 4 Cheong, Otfried
  • 3 Yoon, Sang Duk
  • 2 Agarwal, Pankaj K.
  • 2 Ahn, Hee-Kap
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 Shortest paths
  • 3 approximation
  • 3 fixed-parameter tractability
  • 3 planar graphs
  • 2 Approximation algorithm
  • Show More...

  • Refine by Type
  • 81 document
  • 1 volume

  • Refine by Publication Year
  • 71 2022
  • 3 2016
  • 3 2024
  • 2 2017
  • 1 2018
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact