LIPIcs, Volume 138
MFCS 2019, August 26-30, 2019, Aachen, Germany
Editors: Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Hans-Joachim Böckenhauer, Fabian Frei, and Peter Rossmanith. Removable Online Knapsack and Advice. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bockenhauer_et_al:LIPIcs.STACS.2024.18, author = {B\"{o}ckenhauer, Hans-Joachim and Frei, Fabian and Rossmanith, Peter}, title = {{Removable Online Knapsack and Advice}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {18:1--18:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.18}, URN = {urn:nbn:de:0030-drops-197283}, doi = {10.4230/LIPIcs.STACS.2024.18}, annote = {Keywords: Removable Online Knapsack, Multiple Knapsack, Advice Analysis, Advice Applications, Machine Learning and AI} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Matthias Gehnen, Henri Lotze, and Peter Rossmanith. Online Simple Knapsack with Bounded Predictions. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gehnen_et_al:LIPIcs.STACS.2024.37, author = {Gehnen, Matthias and Lotze, Henri and Rossmanith, Peter}, title = {{Online Simple Knapsack with Bounded Predictions}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {37:1--37:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.37}, URN = {urn:nbn:de:0030-drops-197476}, doi = {10.4230/LIPIcs.STACS.2024.37}, annote = {Keywords: Online problem, Simple Knapsack, Predictions, Machine-Learned Advice} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Jan Dreier, Daniel Mock, and Peter Rossmanith. Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dreier_et_al:LIPIcs.ESA.2023.43, author = {Dreier, Jan and Mock, Daniel and Rossmanith, Peter}, title = {{Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {43:1--43:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.43}, URN = {urn:nbn:de:0030-drops-186961}, doi = {10.4230/LIPIcs.ESA.2023.43}, annote = {Keywords: nowhere dense, sparsity, counting logic, dominating set, FPT} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Elisabet Burjons, Matthias Gehnen, Henri Lotze, Daniel Mock, and Peter Rossmanith. The Online Simple Knapsack Problem with Reservation and Removability. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 29:1-29:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{burjons_et_al:LIPIcs.MFCS.2023.29, author = {Burjons, Elisabet and Gehnen, Matthias and Lotze, Henri and Mock, Daniel and Rossmanith, Peter}, title = {{The Online Simple Knapsack Problem with Reservation and Removability}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {29:1--29:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.29}, URN = {urn:nbn:de:0030-drops-185635}, doi = {10.4230/LIPIcs.MFCS.2023.29}, annote = {Keywords: online algorithm, knapsack, competitive ratio, reservation, preemption} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Elisabet Burjons and Peter Rossmanith. Lower Bounds for Conjunctive and Disjunctive Turing Kernels. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{burjons_et_al:LIPIcs.IPEC.2021.12, author = {Burjons, Elisabet and Rossmanith, Peter}, title = {{Lower Bounds for Conjunctive and Disjunctive Turing Kernels}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.12}, URN = {urn:nbn:de:0030-drops-153953}, doi = {10.4230/LIPIcs.IPEC.2021.12}, annote = {Keywords: Parameterized Complexity, Turing kernels} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Hans-Joachim Böckenhauer, Elisabet Burjons, Juraj Hromkovič, Henri Lotze, and Peter Rossmanith. Online Simple Knapsack with Reservation Costs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bockenhauer_et_al:LIPIcs.STACS.2021.16, author = {B\"{o}ckenhauer, Hans-Joachim and Burjons, Elisabet and Hromkovi\v{c}, Juraj and Lotze, Henri and Rossmanith, Peter}, title = {{Online Simple Knapsack with Reservation Costs}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {16:1--16:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.16}, URN = {urn:nbn:de:0030-drops-136613}, doi = {10.4230/LIPIcs.STACS.2021.16}, annote = {Keywords: Online problem, Simple knapsack, Reservation costs} }
Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)
Fabian Frei, Peter Rossmanith, and David Wehner. An Open Pouring Problem. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 14:1-14:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{frei_et_al:LIPIcs.FUN.2021.14, author = {Frei, Fabian and Rossmanith, Peter and Wehner, David}, title = {{An Open Pouring Problem}}, booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)}, pages = {14:1--14:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-145-0}, ISSN = {1868-8969}, year = {2020}, volume = {157}, editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.14}, URN = {urn:nbn:de:0030-drops-127751}, doi = {10.4230/LIPIcs.FUN.2021.14}, annote = {Keywords: Pitcher Pouring Problem, Water Jug Riddle, Water Bucket Problem, Vessel Puzzle, Complexity, Die Hard} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Jan Dreier, Philipp Kuinke, and Peter Rossmanith. First-Order Model-Checking in Random Graphs and Complex Networks. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 40:1-40:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dreier_et_al:LIPIcs.ESA.2020.40, author = {Dreier, Jan and Kuinke, Philipp and Rossmanith, Peter}, title = {{First-Order Model-Checking in Random Graphs and Complex Networks}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {40:1--40:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.40}, URN = {urn:nbn:de:0030-drops-129068}, doi = {10.4230/LIPIcs.ESA.2020.40}, annote = {Keywords: random graphs, average case analysis, first-order model-checking} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Pavol Ďuriš, Rastislav Královič, Richard Královič, Dana Pardubská, Martin Pašen, and Peter Rossmanith. Randomization in Non-Uniform Finite Automata. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{duris_et_al:LIPIcs.MFCS.2020.30, author = {\v{D}uri\v{s}, Pavol and Kr\'{a}lovi\v{c}, Rastislav and Kr\'{a}lovi\v{c}, Richard and Pardubsk\'{a}, Dana and Pa\v{s}en, Martin and Rossmanith, Peter}, title = {{Randomization in Non-Uniform Finite Automata}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {30:1--30:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.30}, URN = {urn:nbn:de:0030-drops-126987}, doi = {10.4230/LIPIcs.MFCS.2020.30}, annote = {Keywords: finite automata, non-uniform computation, randomization} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Jan Dreier, Philipp Kuinke, and Peter Rossmanith. Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dreier_et_al:LIPIcs.APPROX/RANDOM.2020.14, author = {Dreier, Jan and Kuinke, Philipp and Rossmanith, Peter}, title = {{Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {14:1--14:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.14}, URN = {urn:nbn:de:0030-drops-126171}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.14}, annote = {Keywords: Random Graphs, Preferential Attachment, Sparsity, Somewhere Dense} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Jan Dreier, Henri Lotze, and Peter Rossmanith. Hard Problems on Random Graphs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dreier_et_al:LIPIcs.ICALP.2020.40, author = {Dreier, Jan and Lotze, Henri and Rossmanith, Peter}, title = {{Hard Problems on Random Graphs}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {40:1--40:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.40}, URN = {urn:nbn:de:0030-drops-124477}, doi = {10.4230/LIPIcs.ICALP.2020.40}, annote = {Keywords: random graphs, average-case complexity, first-order model checking} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, and Hung-Lung Wang. The Complexity of Packing Edge-Disjoint Paths. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dreier_et_al:LIPIcs.IPEC.2019.10, author = {Dreier, Jan and Fuchs, Janosch and Hartmann, Tim A. and Kuinke, Philipp and Rossmanith, Peter and Tauer, Bjoern and Wang, Hung-Lung}, title = {{The Complexity of Packing Edge-Disjoint Paths}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.10}, URN = {urn:nbn:de:0030-drops-114710}, doi = {10.4230/LIPIcs.IPEC.2019.10}, annote = {Keywords: parameterized complexity, embedding, packing, covering, Hamiltonian path, unary binpacking, path-perfect graphs} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Jan Dreier and Peter Rossmanith. Hardness of FO Model-Checking on Random Graphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dreier_et_al:LIPIcs.IPEC.2019.11, author = {Dreier, Jan and Rossmanith, Peter}, title = {{Hardness of FO Model-Checking on Random Graphs}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {11:1--11:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.11}, URN = {urn:nbn:de:0030-drops-114721}, doi = {10.4230/LIPIcs.IPEC.2019.11}, annote = {Keywords: random graphs, FO model-checking} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Jan Dreier and Peter Rossmanith. Motif Counting in Preferential Attachment Graphs. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dreier_et_al:LIPIcs.FSTTCS.2019.13, author = {Dreier, Jan and Rossmanith, Peter}, title = {{Motif Counting in Preferential Attachment Graphs}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {13:1--13:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.13}, URN = {urn:nbn:de:0030-drops-115750}, doi = {10.4230/LIPIcs.FSTTCS.2019.13}, annote = {Keywords: random graphs, motif counting, average case analysis, preferential attachment graphs} }
Feedback for Dagstuhl Publishing