Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Cornelius Brand, Martin Koutecký, Alexandra Lassota, and Sebastian Ordyniak. Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{brand_et_al:LIPIcs.ESA.2024.32, author = {Brand, Cornelius and Kouteck\'{y}, Martin and Lassota, Alexandra and Ordyniak, Sebastian}, title = {{Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {32:1--32:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.32}, URN = {urn:nbn:de:0030-drops-211033}, doi = {10.4230/LIPIcs.ESA.2024.32}, annote = {Keywords: Mixed-Integer Programming, Separable Convex Optimization, Parameterized Algorithms, Parameterized Complexity} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Karl Bringmann, Anita Dürr, and Adam Polak. Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bringmann_et_al:LIPIcs.ESA.2024.33, author = {Bringmann, Karl and D\"{u}rr, Anita and Polak, Adam}, title = {{Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {33:1--33:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.33}, URN = {urn:nbn:de:0030-drops-211047}, doi = {10.4230/LIPIcs.ESA.2024.33}, annote = {Keywords: 0-1-Knapsack problem, bounded monotone min-plus convolution, fine-grained complexity} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Klaus Heeger and Danny Hermelin. Minimizing the Weighted Number of Tardy Jobs Is W[1]-Hard. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{heeger_et_al:LIPIcs.ESA.2024.68, author = {Heeger, Klaus and Hermelin, Danny}, title = {{Minimizing the Weighted Number of Tardy Jobs Is W\lbrack1\rbrack-Hard}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {68:1--68:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.68}, URN = {urn:nbn:de:0030-drops-211392}, doi = {10.4230/LIPIcs.ESA.2024.68}, annote = {Keywords: single-machine scheduling, number of different weights, number of different processing times} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Tim Randolph and Karol Węgrzycki. Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 96:1-96:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{randolph_et_al:LIPIcs.ESA.2024.96, author = {Randolph, Tim and W\k{e}grzycki, Karol}, title = {{Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {96:1--96:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.96}, URN = {urn:nbn:de:0030-drops-211672}, doi = {10.4230/LIPIcs.ESA.2024.96}, annote = {Keywords: Parameterized algorithms, parameterized complexity, additive combinatorics, Subset Sum, integer programming, doubling constant} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Diba Hashemi and Weronika Wrzos-Kaminska. Weighted Matching in the Random-Order Streaming and Robust Communication Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 16:1-16:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hashemi_et_al:LIPIcs.APPROX/RANDOM.2024.16, author = {Hashemi, Diba and Wrzos-Kaminska, Weronika}, title = {{Weighted Matching in the Random-Order Streaming and Robust Communication Models}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {16:1--16:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.16}, URN = {urn:nbn:de:0030-drops-210097}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.16}, annote = {Keywords: Maximum Weight Matching, Streaming, Random-Order Streaming, Robust Communication Complexity} }
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} }
Feedback for Dagstuhl Publishing