Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich, and Tobias Stamm. New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{berndt_et_al:LIPIcs.ISAAC.2023.13, author = {Berndt, Sebastian and Brinkop, Hauke and Jansen, Klaus and Mnich, Matthias and Stamm, Tobias}, title = {{New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {13:1--13:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.13}, URN = {urn:nbn:de:0030-drops-193155}, doi = {10.4230/LIPIcs.ISAAC.2023.13}, annote = {Keywords: Integer programming, scheduling algorithms, uniformly related machines, makespan minimization} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Ali Ahmadi, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Roodabeh Safavi, and Ðorđe Žikelić. Algorithms and Hardness Results for Computing Cores of Markov Chains. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ahmadi_et_al:LIPIcs.FSTTCS.2022.29, author = {Ahmadi, Ali and Chatterjee, Krishnendu and Goharshady, Amir Kafshdar and Meggendorfer, Tobias and Safavi, Roodabeh and \v{Z}ikeli\'{c}, Ðor{\d}e}, title = {{Algorithms and Hardness Results for Computing Cores of Markov Chains}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {29:1--29:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.29}, URN = {urn:nbn:de:0030-drops-174216}, doi = {10.4230/LIPIcs.FSTTCS.2022.29}, annote = {Keywords: Markov Chains, Cores, Complexity} }
Published in: Dagstuhl Reports, Volume 12, Issue 2 (2022)
Anne Auger, Carlos M. Fonseca, Tobias Friedrich, Johannes Lengler, and Armand Gissler. Theory of Randomized Optimization Heuristics (Dagstuhl Seminar 22081). In Dagstuhl Reports, Volume 12, Issue 2, pp. 87-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Article{auger_et_al:DagRep.12.2.87, author = {Auger, Anne and Fonseca, Carlos M. and Friedrich, Tobias and Lengler, Johannes and Gissler, Armand}, title = {{Theory of Randomized Optimization Heuristics (Dagstuhl Seminar 22081)}}, pages = {87--102}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {2}, editor = {Auger, Anne and Fonseca, Carlos M. and Friedrich, Tobias and Lengler, Johannes and Gissler, Armand}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.2.87}, URN = {urn:nbn:de:0030-drops-169325}, doi = {10.4230/DagRep.12.2.87}, annote = {Keywords: black-box optimization, derivative-free optimization, evolutionary and genetic algorithms, randomized search algorithms, stochastic gradient descent, theoretical computer science} }
Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
Payas Rajan, Moritz Baum, Michael Wegner, Tobias Zündorf, Christian J. West, Dennis Schieferdecker, and Daniel Delling. Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{rajan_et_al:OASIcs.ATMOS.2021.11, author = {Rajan, Payas and Baum, Moritz and Wegner, Michael and Z\"{u}ndorf, Tobias and West, Christian J. and Schieferdecker, Dennis and Delling, Daniel}, title = {{Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles}}, booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)}, pages = {11:1--11:18}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-213-6}, ISSN = {2190-6807}, year = {2021}, volume = {96}, editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.11}, URN = {urn:nbn:de:0030-drops-148807}, doi = {10.4230/OASIcs.ATMOS.2021.11}, annote = {Keywords: Electric Vehicles, Route Planning} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bilo_et_al:LIPIcs.ESA.2021.18, author = {Bil\`{o}, Davide and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, title = {{Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {18:1--18:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus 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.2021.18}, URN = {urn:nbn:de:0030-drops-145999}, doi = {10.4230/LIPIcs.ESA.2021.18}, annote = {Keywords: derandomization, distance sensitivity oracle, single-source replacement paths, space lower bound} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Thomas Bläsius, Tobias Friedrich, and Maximilian Katzmann. Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{blasius_et_al:LIPIcs.ESA.2021.20, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Katzmann, Maximilian}, title = {{Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {20:1--20:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus 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.2021.20}, URN = {urn:nbn:de:0030-drops-146012}, doi = {10.4230/LIPIcs.ESA.2021.20}, annote = {Keywords: vertex cover, approximation, random graphs, hyperbolic geometry, efficient algorithm} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese. Faster (1+ε)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{grandoni_et_al:LIPIcs.ESA.2021.49, author = {Grandoni, Fabrizio and M\"{o}mke, Tobias and Wiese, Andreas}, title = {{Faster (1+\epsilon)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {49:1--49:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus 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.2021.49}, URN = {urn:nbn:de:0030-drops-146301}, doi = {10.4230/LIPIcs.ESA.2021.49}, annote = {Keywords: Approximation Algorithms, Unsplittable Flow, Dynamic Programming} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Space-Efficient Fault-Tolerant Diameter Oracles. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bilo_et_al:LIPIcs.MFCS.2021.18, author = {Bil\`{o}, Davide and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, title = {{Space-Efficient Fault-Tolerant Diameter Oracles}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {18:1--18:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.18}, URN = {urn:nbn:de:0030-drops-144581}, doi = {10.4230/LIPIcs.MFCS.2021.18}, annote = {Keywords: derandomization, diameter, distance sensitivity oracle, fault-tolerant data structure, space lower bound} }
Published in: LIPIcs, Volume 166, 34th European Conference on Object-Oriented Programming (ECOOP 2020)
Benjamin Barslev Nielsen and Anders Møller. Value Partitioning: A Lightweight Approach to Relational Static Analysis for JavaScript. In 34th European Conference on Object-Oriented Programming (ECOOP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 166, pp. 16:1-16:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{nielsen_et_al:LIPIcs.ECOOP.2020.16, author = {Nielsen, Benjamin Barslev and M{\o}ller, Anders}, title = {{Value Partitioning: A Lightweight Approach to Relational Static Analysis for JavaScript}}, booktitle = {34th European Conference on Object-Oriented Programming (ECOOP 2020)}, pages = {16:1--16:28}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-154-2}, ISSN = {1868-8969}, year = {2020}, volume = {166}, editor = {Hirschfeld, Robert and Pape, Tobias}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2020.16}, URN = {urn:nbn:de:0030-drops-131731}, doi = {10.4230/LIPIcs.ECOOP.2020.16}, annote = {Keywords: JavaScript, dataflow analysis, abstract interpretation} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Thomas Bläsius, Tobias Friedrich, and Martin Schirneck. The Minimization of Random Hypergraphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{blasius_et_al:LIPIcs.ESA.2020.21, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Schirneck, Martin}, title = {{The Minimization of Random Hypergraphs}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {21:1--21:15}, 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.21}, URN = {urn:nbn:de:0030-drops-128871}, doi = {10.4230/LIPIcs.ESA.2020.21}, annote = {Keywords: Chernoff-Hoeffding theorem, maximum entropy, maximization, minimization, phase transition, random hypergraphs} }
Published in: OASIcs, Volume 79, 2nd International Workshop on Autonomous Systems Design (ASD 2020)
Tobias Kain, Philipp Mundhenk, Julian-Steffen Müller, Hans Tompits, Maximilian Wesche, and Hendrik Decke. Towards a Reliable and Context-Based System Architecture for Autonomous Vehicles. In 2nd International Workshop on Autonomous Systems Design (ASD 2020). Open Access Series in Informatics (OASIcs), Volume 79, pp. 1:1-1:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kain_et_al:OASIcs.ASD.2020.1, author = {Kain, Tobias and Mundhenk, Philipp and M\"{u}ller, Julian-Steffen and Tompits, Hans and Wesche, Maximilian and Decke, Hendrik}, title = {{Towards a Reliable and Context-Based System Architecture for Autonomous Vehicles}}, booktitle = {2nd International Workshop on Autonomous Systems Design (ASD 2020)}, pages = {1:1--1:7}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-141-2}, ISSN = {2190-6807}, year = {2020}, volume = {79}, editor = {Steinhorst, Sebastian and Deshmukh, Jyotirmoy V.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ASD.2020.1}, URN = {urn:nbn:de:0030-drops-125956}, doi = {10.4230/OASIcs.ASD.2020.1}, annote = {Keywords: autonomous driving, fail-operational systems, context-based architecture, application placement, optimization, monitoring} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Tobias Mömke and Andreas Wiese. Breaking the Barrier of 2 for the Storage Allocation Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 86:1-86:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{momke_et_al:LIPIcs.ICALP.2020.86, author = {M\"{o}mke, Tobias and Wiese, Andreas}, title = {{Breaking the Barrier of 2 for the Storage Allocation Problem}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {86:1--86:19}, 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.86}, URN = {urn:nbn:de:0030-drops-124931}, doi = {10.4230/LIPIcs.ICALP.2020.86}, annote = {Keywords: Approximation Algorithms, Resource Allocation, Dynamic Programming} }
Published in: Dagstuhl Reports, Volume 9, Issue 10 (2020)
Carola Doerr, Carlos M. Fonseca, Tobias Friedrich, and Xin Yao. Theory of Randomized Optimization Heuristics (Dagstuhl Reports 19431). In Dagstuhl Reports, Volume 9, Issue 10, pp. 61-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@Article{doerr_et_al:DagRep.9.10.61, author = {Doerr, Carola and Fonseca, Carlos M. and Friedrich, Tobias and Yao, Xin}, title = {{Theory of Randomized Optimization Heuristics (Dagstuhl Reports 19431)}}, pages = {61--94}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2020}, volume = {9}, number = {10}, editor = {Doerr, Carola and Fonseca, Carlos M. and Friedrich, Tobias and Yao, Xin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.10.61}, URN = {urn:nbn:de:0030-drops-118567}, doi = {10.4230/DagRep.9.10.61}, annote = {Keywords: algorithms and complexity, evolutionary algorithms, machine learning, optimization, soft computing} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Tobias Friedrich and Ralf Rothenberger. The Satisfiability Threshold for Non-Uniform Random 2-SAT. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{friedrich_et_al:LIPIcs.ICALP.2019.61, author = {Friedrich, Tobias and Rothenberger, Ralf}, title = {{The Satisfiability Threshold for Non-Uniform Random 2-SAT}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {61:1--61:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.61}, URN = {urn:nbn:de:0030-drops-106372}, doi = {10.4230/LIPIcs.ICALP.2019.61}, annote = {Keywords: random SAT, satisfiability threshold, sharpness, non-uniform distribution, 2-SAT} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Shilpa Garg and Tobias Mömke. A QPTAS for Gapless MEC. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{garg_et_al:LIPIcs.ESA.2018.34, author = {Garg, Shilpa and M\"{o}mke, Tobias}, title = {{A QPTAS for Gapless MEC}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {34:1--34: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.34}, URN = {urn:nbn:de:0030-drops-94978}, doi = {10.4230/LIPIcs.ESA.2018.34}, annote = {Keywords: approximation algorithms, QPTAS, minimum error correction, segmentation, computational biology} }
Feedback for Dagstuhl Publishing