Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Tomer Cohen, Ariel Kulik, and Hadas Shachnai. Improved Approximation for Two-Dimensional Vector Multiple Knapsack. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 20:1-20:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{cohen_et_al:LIPIcs.ISAAC.2023.20, author = {Cohen, Tomer and Kulik, Ariel and Shachnai, Hadas}, title = {{Improved Approximation for Two-Dimensional Vector Multiple Knapsack}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {20:1--20: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.20}, URN = {urn:nbn:de:0030-drops-193229}, doi = {10.4230/LIPIcs.ISAAC.2023.20}, annote = {Keywords: vector multiple knapsack, two-dimensional packing, randomized rounding, approximation algorithms} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 22:1-22:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{doronarad_et_al:LIPIcs.APPROX/RANDOM.2023.22, author = {Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas}, title = {{An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {22:1--22:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.22}, URN = {urn:nbn:de:0030-drops-188470}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.22}, annote = {Keywords: bin packing, partition-matroid, AFPTAS, LP-rounding} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 49:1-49:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{doronarad_et_al:LIPIcs.ICALP.2023.49, author = {Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas}, title = {{An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {49:1--49:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.49}, URN = {urn:nbn:de:0030-drops-181018}, doi = {10.4230/LIPIcs.ICALP.2023.49}, annote = {Keywords: budgeted matching, budgeted matroid intersection, efficient polynomial-time approximation scheme} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Barış Can Esmer, Ariel Kulik, Dániel Marx, Philipp Schepper, and Karol Węgrzycki. Computing Generalized Convolutions Faster Than Brute Force. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 12:1-12:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{esmer_et_al:LIPIcs.IPEC.2022.12, author = {Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Schepper, Philipp and W\k{e}grzycki, Karol}, title = {{Computing Generalized Convolutions Faster Than Brute Force}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {12:1--12:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.12}, URN = {urn:nbn:de:0030-drops-173685}, doi = {10.4230/LIPIcs.IPEC.2022.12}, annote = {Keywords: Generalized Convolution, Fast Fourier Transform, Fast Subset Convolution} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Barış Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma. Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 50:1-50:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{esmer_et_al:LIPIcs.ESA.2022.50, author = {Esmer, Bar{\i}\c{s} Can and Kulik, Ariel and Marx, D\'{a}niel and Neuen, Daniel and Sharma, Roohani}, title = {{Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {50:1--50:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.50}, URN = {urn:nbn:de:0030-drops-169887}, doi = {10.4230/LIPIcs.ESA.2022.50}, annote = {Keywords: parameterized approximations, exponential approximations, monotone local search} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, and Danny Raz. General Knapsack Problems in a Dynamic Setting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 15:1-15:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{fairstein_et_al:LIPIcs.APPROX/RANDOM.2021.15, author = {Fairstein, Yaron and Kulik, Ariel and Naor, Joseph (Seffi) and Raz, Danny}, title = {{General Knapsack Problems in a Dynamic Setting}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {15:1--15:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.15}, URN = {urn:nbn:de:0030-drops-147081}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.15}, annote = {Keywords: Multistage, Multiple-Knapsacks, Multidimensional Knapsack} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Yaron Fairstein, Ariel Kulik, and Hadas Shachnai. Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 41:1-41:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{fairstein_et_al:LIPIcs.ESA.2021.41, author = {Fairstein, Yaron and Kulik, Ariel and Shachnai, Hadas}, title = {{Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {41:1--41:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.41}, URN = {urn:nbn:de:0030-drops-146229}, doi = {10.4230/LIPIcs.ESA.2021.41}, annote = {Keywords: Sumodular Optimization, Multiple Knapsack, Randomized Rounding, Linear Grouping, Multiple Choice Multiple Knapsack} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, Danny Raz, and Hadas Shachnai. A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 44:1-44:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{fairstein_et_al:LIPIcs.ESA.2020.44, author = {Fairstein, Yaron and Kulik, Ariel and Naor, Joseph (Seffi) and Raz, Danny and Shachnai, Hadas}, title = {{A (1-e^\{-1\}-\epsilon)-Approximation for the Monotone Submodular Multiple Knapsack Problem}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {44:1--44:19}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.44}, URN = {urn:nbn:de:0030-drops-129107}, doi = {10.4230/LIPIcs.ESA.2020.44}, annote = {Keywords: Sumodular Optimization, Multiple Knapsack, Randomized Rounding} }
Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)
Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Parameterized Distributed Algorithms. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 6:1-6:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{benbasat_et_al:LIPIcs.DISC.2019.6, author = {Ben-Basat, Ran and Kawarabayashi, Ken-ichi and Schwartzman, Gregory}, title = {{Parameterized Distributed Algorithms}}, booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)}, pages = {6:1--6:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-126-9}, ISSN = {1868-8969}, year = {2019}, volume = {146}, editor = {Suomela, Jukka}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.6}, URN = {urn:nbn:de:0030-drops-113135}, doi = {10.4230/LIPIcs.DISC.2019.6}, annote = {Keywords: Distributed Algorithms, Approximation Algorithms, Parameterized Algorithms} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Ariel Kulik, Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai. Generalized Assignment via Submodular Optimization with Reserved Capacity. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 69:1-69:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{kulik_et_al:LIPIcs.ESA.2019.69, author = {Kulik, Ariel and Sarpatwar, Kanthi and Schieber, Baruch and Shachnai, Hadas}, title = {{Generalized Assignment via Submodular Optimization with Reserved Capacity}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {69:1--69:15}, 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.69}, URN = {urn:nbn:de:0030-drops-111906}, doi = {10.4230/LIPIcs.ESA.2019.69}, annote = {Keywords: Group Generalized Assignment Problem, Submodular Maximization, Knapsack Constraints, Approximation Algorithms} }
Feedback for Dagstuhl Publishing