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 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Leah Epstein, Alexandra Lassota, Asaf Levin, Marten Maack, and Lars Rohwedder. Cardinality Constrained Scheduling in Online Models. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{epstein_et_al:LIPIcs.STACS.2022.28, author = {Epstein, Leah and Lassota, Alexandra and Levin, Asaf and Maack, Marten and Rohwedder, Lars}, title = {{Cardinality Constrained Scheduling in Online Models}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {28:1--28:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.28}, URN = {urn:nbn:de:0030-drops-158385}, doi = {10.4230/LIPIcs.STACS.2022.28}, annote = {Keywords: Cardinality Constrained Scheduling, Makespan Minimization, Online Algorithms, Lower Bounds, Pure Online, Migration, Ordinal Algorithms} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Moritz Buchem, Lars Rohwedder, Tjark Vredeveld, and Andreas Wiese. Additive Approximation Schemes for Load Balancing Problems. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{buchem_et_al:LIPIcs.ICALP.2021.42, author = {Buchem, Moritz and Rohwedder, Lars and Vredeveld, Tjark and Wiese, Andreas}, title = {{Additive Approximation Schemes for Load Balancing Problems}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {42:1--42:17}, 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.42}, URN = {urn:nbn:de:0030-drops-141116}, doi = {10.4230/LIPIcs.ICALP.2021.42}, annote = {Keywords: Load balancing, Approximation schemes, Parallel machine scheduling} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Adam Polak, Lars Rohwedder, and Karol Węgrzycki. Knapsack and Subset Sum with Small Items. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 106:1-106:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{polak_et_al:LIPIcs.ICALP.2021.106, author = {Polak, Adam and Rohwedder, Lars and W\k{e}grzycki, Karol}, title = {{Knapsack and Subset Sum with Small Items}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {106:1--106:19}, 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.106}, URN = {urn:nbn:de:0030-drops-141752}, doi = {10.4230/LIPIcs.ICALP.2021.106}, annote = {Keywords: Knapsack, Subset Sum, Proximity, Additive Combinatorics, Multiset} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Etienne Bamas, Paritosh Garg, and Lars Rohwedder. The Submodular Santa Claus Problem in the Restricted Assignment Case. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bamas_et_al:LIPIcs.ICALP.2021.22, author = {Bamas, Etienne and Garg, Paritosh and Rohwedder, Lars}, title = {{The Submodular Santa Claus Problem in the Restricted Assignment Case}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {22:1--22:18}, 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.22}, URN = {urn:nbn:de:0030-drops-140912}, doi = {10.4230/LIPIcs.ICALP.2021.22}, annote = {Keywords: Scheduling, submodularity, approximation algorithm, hypergraph matching} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Paritosh Garg, Sagar Kale, Lars Rohwedder, and Ola Svensson. Robust Algorithms Under Adversarial Injections. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{garg_et_al:LIPIcs.ICALP.2020.56, author = {Garg, Paritosh and Kale, Sagar and Rohwedder, Lars and Svensson, Ola}, title = {{Robust Algorithms Under Adversarial Injections}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {56:1--56:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.56}, URN = {urn:nbn:de:0030-drops-124632}, doi = {10.4230/LIPIcs.ICALP.2020.56}, annote = {Keywords: Streaming algorithm, adversary, submodular maximization, matching} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Marten Maack and Klaus Jansen. Inapproximability Results for Scheduling with Interval and Resource Restrictions. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{maack_et_al:LIPIcs.STACS.2020.5, author = {Maack, Marten and Jansen, Klaus}, title = {{Inapproximability Results for Scheduling with Interval and Resource Restrictions}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {5:1--5:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.5}, URN = {urn:nbn:de:0030-drops-118663}, doi = {10.4230/LIPIcs.STACS.2020.5}, annote = {Keywords: Scheduling, Restricted Assignment, Approximation, Inapproximability, PTAS} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, and Lars Rohwedder. Online Bin Covering with Limited Migration. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{berndt_et_al:LIPIcs.ESA.2019.18, author = {Berndt, Sebastian and Epstein, Leah and Jansen, Klaus and Levin, Asaf and Maack, Marten and Rohwedder, Lars}, title = {{Online Bin Covering with Limited Migration}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {18:1--18:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.18}, URN = {urn:nbn:de:0030-drops-111391}, doi = {10.4230/LIPIcs.ESA.2019.18}, annote = {Keywords: online algorithms, dynamic algorithms, competitive ratio, bin covering, migration factor} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Klaus Jansen and Lars Rohwedder. Local Search Breaks 1.75 for Graph Balancing. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{jansen_et_al:LIPIcs.ICALP.2019.74, author = {Jansen, Klaus and Rohwedder, Lars}, title = {{Local Search Breaks 1.75 for Graph Balancing}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {74:1--74: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.74}, URN = {urn:nbn:de:0030-drops-106501}, doi = {10.4230/LIPIcs.ICALP.2019.74}, annote = {Keywords: graph, approximation algorithm, scheduling, integrality gap, local search} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Klaus Jansen, Alexandra Lassota, and Lars Rohwedder. Near-Linear Time Algorithm for n-fold ILPs via Color Coding. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 75:1-75:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{jansen_et_al:LIPIcs.ICALP.2019.75, author = {Jansen, Klaus and Lassota, Alexandra and Rohwedder, Lars}, title = {{Near-Linear Time Algorithm for n-fold ILPs via Color Coding}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {75:1--75:13}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.75}, URN = {urn:nbn:de:0030-drops-106518}, doi = {10.4230/LIPIcs.ICALP.2019.75}, annote = {Keywords: Near-Linear Time Algorithm, n-fold ILP, Color Coding} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Dušan Knop, Michał Pilipczuk, and Marcin Wrochna. Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{knop_et_al:LIPIcs.STACS.2019.44, author = {Knop, Du\v{s}an and Pilipczuk, Micha{\l} and Wrochna, Marcin}, title = {{Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {44:1--44:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.44}, URN = {urn:nbn:de:0030-drops-102831}, doi = {10.4230/LIPIcs.STACS.2019.44}, annote = {Keywords: integer linear programming, fixed-parameter tractability, ETH} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Klaus Jansen and Lars Rohwedder. On Integer Programming and Convolution. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{jansen_et_al:LIPIcs.ITCS.2019.43, author = {Jansen, Klaus and Rohwedder, Lars}, title = {{On Integer Programming and Convolution}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {43:1--43:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.43}, URN = {urn:nbn:de:0030-drops-101365}, doi = {10.4230/LIPIcs.ITCS.2019.43}, annote = {Keywords: Integer programming, convolution, dynamic programming, SETH} }
Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Klaus Jansen and Lars Rohwedder. Compact LP Relaxations for Allocation Problems. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{jansen_et_al:OASIcs.SOSA.2018.11, author = {Jansen, Klaus and Rohwedder, Lars}, title = {{Compact LP Relaxations for Allocation Problems}}, booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)}, pages = {11:1--11:19}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-064-4}, ISSN = {2190-6807}, year = {2018}, volume = {61}, editor = {Seidel, Raimund}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.11}, URN = {urn:nbn:de:0030-drops-83012}, doi = {10.4230/OASIcs.SOSA.2018.11}, annote = {Keywords: Linear programming, unrelated machines, makespan, max-min, restricted assignment, santa claus} }