Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Matthias Englert, Nicolaos Matsakis, and Pavel Veselý. Approximation Guarantees for Shortest Superstrings: Simpler and Better. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 29:1-29:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{englert_et_al:LIPIcs.ISAAC.2023.29, author = {Englert, Matthias and Matsakis, Nicolaos and Vesel\'{y}, Pavel}, title = {{Approximation Guarantees for Shortest Superstrings: Simpler and Better}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {29:1--29:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.29}, URN = {urn:nbn:de:0030-drops-193319}, doi = {10.4230/LIPIcs.ISAAC.2023.29}, annote = {Keywords: Shortest Superstring problem, Approximation Algorithms} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Antonios Antoniadis, Matthias Englert, Nicolaos Matsakis, and Pavel Veselý. Breaking the Barrier Of 2 for the Competitiveness of Longest Queue Drop. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 17:1-17:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{antoniadis_et_al:LIPIcs.ICALP.2021.17, author = {Antoniadis, Antonios and Englert, Matthias and Matsakis, Nicolaos and Vesel\'{y}, Pavel}, title = {{Breaking the Barrier Of 2 for the Competitiveness of Longest Queue Drop}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {17:1--17:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.17}, URN = {urn:nbn:de:0030-drops-140864}, doi = {10.4230/LIPIcs.ICALP.2021.17}, annote = {Keywords: buffer management, online scheduling, online algorithms, longest queue drop} }
Published in: LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020)
Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, and Filip Mazowiecki. Reachability in Fixed Dimension Vector Addition Systems with States. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 48:1-48:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{czerwinski_et_al:LIPIcs.CONCUR.2020.48, author = {Czerwi\'{n}ski, Wojciech and Lasota, S{\l}awomir and Lazi\'{c}, Ranko and Leroux, J\'{e}r\^{o}me and Mazowiecki, Filip}, title = {{Reachability in Fixed Dimension Vector Addition Systems with States}}, booktitle = {31st International Conference on Concurrency Theory (CONCUR 2020)}, pages = {48:1--48:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-160-3}, ISSN = {1868-8969}, year = {2020}, volume = {171}, editor = {Konnov, Igor and Kov\'{a}cs, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.48}, URN = {urn:nbn:de:0030-drops-128605}, doi = {10.4230/LIPIcs.CONCUR.2020.48}, annote = {Keywords: reachability problem, vector addition systems, Petri nets} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Ranko Lazić. Finkel Was Right: Counter-Examples to Several Conjectures on Variants of Vector Addition Systems (Invited Talk). 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. 3:1-3:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{lazic:LIPIcs.FSTTCS.2019.3, author = {Lazi\'{c}, Ranko}, title = {{Finkel Was Right: Counter-Examples to Several Conjectures on Variants of Vector Addition Systems}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {3:1--3:2}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.3}, URN = {urn:nbn:de:0030-drops-115653}, doi = {10.4230/LIPIcs.FSTTCS.2019.3}, annote = {Keywords: Petri nets, vector addition systems, reachability} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Wojciech Czerwiński, Sławomir Lasota, Christof Löding, and Radosław Piórkowski. New Pumping Technique for 2-Dimensional VASS. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{czerwinski_et_al:LIPIcs.MFCS.2019.62, author = {Czerwi\'{n}ski, Wojciech and Lasota, S{\l}awomir and L\"{o}ding, Christof and Pi\'{o}rkowski, Rados{\l}aw}, title = {{New Pumping Technique for 2-Dimensional VASS}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {62:1--62:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.62}, URN = {urn:nbn:de:0030-drops-110066}, doi = {10.4230/LIPIcs.MFCS.2019.62}, annote = {Keywords: vector addition systems with states, pumping, decidability} }
Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)
Filip Mazowiecki and Michał Pilipczuk. Reachability for Bounded Branching VASS. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{mazowiecki_et_al:LIPIcs.CONCUR.2019.28, author = {Mazowiecki, Filip and Pilipczuk, Micha{\l}}, title = {{Reachability for Bounded Branching VASS}}, booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)}, pages = {28:1--28:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-121-4}, ISSN = {1868-8969}, year = {2019}, volume = {140}, editor = {Fokkink, Wan and van Glabbeek, Rob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.28}, URN = {urn:nbn:de:0030-drops-109303}, doi = {10.4230/LIPIcs.CONCUR.2019.28}, annote = {Keywords: Branching VASS, counter machines, reachability problem, bobrvass} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Jérôme Leroux. Petri Net Reachability Problem (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 5:1-5:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{leroux:LIPIcs.MFCS.2019.5, author = {Leroux, J\'{e}r\^{o}me}, title = {{Petri Net Reachability Problem}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {5:1--5:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.5}, URN = {urn:nbn:de:0030-drops-109493}, doi = {10.4230/LIPIcs.MFCS.2019.5}, annote = {Keywords: Petri net, Reachability problem, Formal verification, Concurrency} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Matthias Englert, David Mezlaf, and Matthias Westermann. Online Makespan Scheduling with Job Migration on Uniform Machines. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 26:1-26:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{englert_et_al:LIPIcs.ESA.2018.26, author = {Englert, Matthias and Mezlaf, David and Westermann, Matthias}, title = {{Online Makespan Scheduling with Job Migration on Uniform Machines}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {26:1--26:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.26}, URN = {urn:nbn:de:0030-drops-94890}, doi = {10.4230/LIPIcs.ESA.2018.26}, annote = {Keywords: online algorithms, competitive analysis, minimum makespan scheduling, job migration} }
Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Sepehr Assadi, Sanjeev Khanna, Yang Li, and Val Tannen. Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 52-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{assadi_et_al:LIPIcs.FSTTCS.2015.52, author = {Assadi, Sepehr and Khanna, Sanjeev and Li, Yang and Tannen, Val}, title = {{Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {52--68}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.52}, URN = {urn:nbn:de:0030-drops-56361}, doi = {10.4230/LIPIcs.FSTTCS.2015.52}, annote = {Keywords: Small-space Algorithms, Maximum Matchings, Vertex Sparsifiers} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 242-264, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{elkin_et_al:LIPIcs.APPROX-RANDOM.2015.242, author = {Elkin, Michael and Filtser, Arnold and Neiman, Ofer}, title = {{Terminal Embeddings}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {242--264}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.242}, URN = {urn:nbn:de:0030-drops-53064}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.242}, annote = {Keywords: embedding, distortion, terminals} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Yossi Azar, Matthias Englert, Iftah Gamzu, and Eytan Kidron. Generalized Reordering Buffer Management. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 87-98, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{azar_et_al:LIPIcs.STACS.2014.87, author = {Azar, Yossi and Englert, Matthias and Gamzu, Iftah and Kidron, Eytan}, title = {{Generalized Reordering Buffer Management}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {87--98}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.87}, URN = {urn:nbn:de:0030-drops-44498}, doi = {10.4230/LIPIcs.STACS.2014.87}, annote = {Keywords: online algorithms, paging, reordering buffer} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Matthias Englert, Heiko Röglin, Jacob Spönemann, and Berthold Vöcking. Economical Caching. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 385-396, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)
@InProceedings{englert_et_al:LIPIcs.STACS.2009.1826, author = {Englert, Matthias and R\"{o}glin, Heiko and Sp\"{o}nemann, Jacob and V\"{o}cking, Berthold}, title = {{Economical Caching}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {385--396}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1826}, URN = {urn:nbn:de:0030-drops-18263}, doi = {10.4230/LIPIcs.STACS.2009.1826}, annote = {Keywords: Online algorithms, Competitive analysis, Storage management} }
Feedback for Dagstuhl Publishing