LIPIcs, Volume 248
ISAAC 2022, December 19-21, 2022, Seoul, Korea
Editors: Sang Won Bae and Heejin Park
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Eunou Lee and Ojas Parekh. An Improved Quantum Max Cut Approximation via Maximum Matching. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 105:1-105:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lee_et_al:LIPIcs.ICALP.2024.105, author = {Lee, Eunou and Parekh, Ojas}, title = {{An Improved Quantum Max Cut Approximation via Maximum Matching}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {105:1--105:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.105}, URN = {urn:nbn:de:0030-drops-202482}, doi = {10.4230/LIPIcs.ICALP.2024.105}, annote = {Keywords: approximation, optimization, local Hamiltonian, rounding, SDP, matching} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
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)
@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} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Kyle Fox, Hongyao Huang, and Benjamin Raichel. Clustering with Faulty Centers. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fox_et_al:LIPIcs.ISAAC.2022.10, author = {Fox, Kyle and Huang, Hongyao and Raichel, Benjamin}, title = {{Clustering with Faulty Centers}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {10:1--10: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.10}, URN = {urn:nbn:de:0030-drops-172950}, doi = {10.4230/LIPIcs.ISAAC.2022.10}, annote = {Keywords: clustering, approximation, probabilistic input, uncertain input} }