LIPIcs, Volume 149
ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China
Editors: Pinyan Lu and Guochuan Zhang
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Nick Fischer and Leo Wennmann. Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 64:1-64:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fischer_et_al:LIPIcs.ICALP.2024.64, author = {Fischer, Nick and Wennmann, Leo}, title = {{Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {64:1--64:15}, 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.64}, URN = {urn:nbn:de:0030-drops-202079}, doi = {10.4230/LIPIcs.ICALP.2024.64}, annote = {Keywords: Scheduling, Fine-Grained Complexity, Dynamic Strings} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Klaus Heeger, Danny Hermelin, Matthias Mnich, and Dvir Shabtay. No Polynomial Kernels for Knapsack. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 83:1-83:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{heeger_et_al:LIPIcs.ICALP.2024.83, author = {Heeger, Klaus and Hermelin, Danny and Mnich, Matthias and Shabtay, Dvir}, title = {{No Polynomial Kernels for Knapsack}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {83:1--83:17}, 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.83}, URN = {urn:nbn:de:0030-drops-202261}, doi = {10.4230/LIPIcs.ICALP.2024.83}, annote = {Keywords: Knapsack, polynomial kernels, compositions, number of different weights, number of different profits} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Lin Chen, Xiaoyu Wu, and Guochuan Zhang. Approximation Algorithms for Interdiction Problem with Packing Constraints. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chen_et_al:LIPIcs.ICALP.2022.39, author = {Chen, Lin and Wu, Xiaoyu and Zhang, Guochuan}, title = {{Approximation Algorithms for Interdiction Problem with Packing Constraints}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {39:1--39:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.39}, URN = {urn:nbn:de:0030-drops-163806}, doi = {10.4230/LIPIcs.ICALP.2022.39}, annote = {Keywords: Bilevel Integer Programming, Interdiction Constraints, Knapsack} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Proceedings{lu_et_al:LIPIcs.ISAAC.2019, title = {{LIPIcs, Volume 149, ISAAC'19, Complete Volume}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019}, URN = {urn:nbn:de:0030-drops-116417}, doi = {10.4230/LIPIcs.ISAAC.2019}, annote = {Keywords: Theory of computation; Models of computation; Computational complexity and cryptography; Randomness, geometry and discrete structures; Theory and algorithms for application domains; Design and analysis of algorithms} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lu_et_al:LIPIcs.ISAAC.2019.0, author = {Lu, Pinyan and Zhang, Guochuan}, title = {{Front Matter, Table of Contents, Preface, Symposium Organization}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.0}, URN = {urn:nbn:de:0030-drops-114967}, doi = {10.4230/LIPIcs.ISAAC.2019.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Symposium Organization} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Yixin Cao, Zhifeng Wang, Guozhen Rong, and Jianxin Wang. Graph Searches and Their End Vertices. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cao_et_al:LIPIcs.ISAAC.2019.1, author = {Cao, Yixin and Wang, Zhifeng and Rong, Guozhen and Wang, Jianxin}, title = {{Graph Searches and Their End Vertices}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {1:1--1:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.1}, URN = {urn:nbn:de:0030-drops-114973}, doi = {10.4230/LIPIcs.ISAAC.2019.1}, annote = {Keywords: maximum cardinality search, (lexicographic) breadth-first search, (lexicographic) depth-first search, chordal graph, weighted clique graph, end vertex} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Nader H. Bshouty. Lower Bound for Non-Adaptive Estimation of the Number of Defective Items. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bshouty:LIPIcs.ISAAC.2019.2, author = {Bshouty, Nader H.}, title = {{Lower Bound for Non-Adaptive Estimation of the Number of Defective Items}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {2:1--2:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.2}, URN = {urn:nbn:de:0030-drops-114983}, doi = {10.4230/LIPIcs.ISAAC.2019.2}, annote = {Keywords: Group Testing, Estimation, Defective Items} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Kazuya Haraguchi and Hiroshi Nagamochi. A Polynomial-Delay Algorithm for Enumerating Connectors Under Various Connectivity Conditions. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{haraguchi_et_al:LIPIcs.ISAAC.2019.3, author = {Haraguchi, Kazuya and Nagamochi, Hiroshi}, title = {{A Polynomial-Delay Algorithm for Enumerating Connectors Under Various Connectivity Conditions}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.3}, URN = {urn:nbn:de:0030-drops-114990}, doi = {10.4230/LIPIcs.ISAAC.2019.3}, annote = {Keywords: Graph with itemsets, Enumeration, Polynomial-delay algorithms, Connectors} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau, and Oren Weimann. Top Tree Compression of Tries. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bille_et_al:LIPIcs.ISAAC.2019.4, author = {Bille, Philip and Gawrychowski, Pawe{\l} and G{\o}rtz, Inge Li and Landau, Gad M. and Weimann, Oren}, title = {{Top Tree Compression of Tries}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {4:1--4:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.4}, URN = {urn:nbn:de:0030-drops-115000}, doi = {10.4230/LIPIcs.ISAAC.2019.4}, annote = {Keywords: pattern matching, tree compression, top trees, pointer machine} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Ahad N. Zehmakan. Two Phase Transitions in Two-Way Bootstrap Percolation. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{zehmakan:LIPIcs.ISAAC.2019.5, author = {Zehmakan, Ahad N.}, title = {{Two Phase Transitions in Two-Way Bootstrap Percolation}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {5:1--5:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.5}, URN = {urn:nbn:de:0030-drops-115017}, doi = {10.4230/LIPIcs.ISAAC.2019.5}, annote = {Keywords: bootstrap percolation, cellular automata, phase transition, d-dimensional torus, r-threshold model, biased majority} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya. Sliding Window Property Testing for Regular Languages. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ganardi_et_al:LIPIcs.ISAAC.2019.6, author = {Ganardi, Moses and Hucke, Danny and Lohrey, Markus and Starikovskaya, Tatiana}, title = {{Sliding Window Property Testing for Regular Languages}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {6:1--6:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.6}, URN = {urn:nbn:de:0030-drops-115023}, doi = {10.4230/LIPIcs.ISAAC.2019.6}, annote = {Keywords: Streaming algorithms, approximation algorithms, regular languages} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Isaac Goldstein, Moshe Lewenstein, and Ely Porat. On the Hardness of Set Disjointness and Set Intersection with Bounded Universe. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{goldstein_et_al:LIPIcs.ISAAC.2019.7, author = {Goldstein, Isaac and Lewenstein, Moshe and Porat, Ely}, title = {{On the Hardness of Set Disjointness and Set Intersection with Bounded Universe}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {7:1--7:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.7}, URN = {urn:nbn:de:0030-drops-115036}, doi = {10.4230/LIPIcs.ISAAC.2019.7}, annote = {Keywords: set disjointness, set intersection, 3SUM, space-time tradeoff, conditional lower bounds} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Paola Flocchini, Ryan Killick, Evangelos Kranakis, Nicola Santoro, and Masafumi Yamashita. Gathering and Election by Mobile Robots in a Continuous Cycle. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{flocchini_et_al:LIPIcs.ISAAC.2019.8, author = {Flocchini, Paola and Killick, Ryan and Kranakis, Evangelos and Santoro, Nicola and Yamashita, Masafumi}, title = {{Gathering and Election by Mobile Robots in a Continuous Cycle}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {8:1--8:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.8}, URN = {urn:nbn:de:0030-drops-115044}, doi = {10.4230/LIPIcs.ISAAC.2019.8}, annote = {Keywords: Cycle, Election, Gathering, Las Vegas, Monte Carlo, Randomized Algorithm} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Koki Hamada, Shuichi Miyazaki, and Hiroki Yanagisawa. Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hamada_et_al:LIPIcs.ISAAC.2019.9, author = {Hamada, Koki and Miyazaki, Shuichi and Yanagisawa, Hiroki}, title = {{Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.9}, URN = {urn:nbn:de:0030-drops-115059}, doi = {10.4230/LIPIcs.ISAAC.2019.9}, annote = {Keywords: Stable marriage problem, strategy-proofness, approximation algorithm, ties, incomplete lists} }