Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
S M Ferdous, Alex Pothen, and Mahantesh Halappanavar. Streaming Matching and Edge Cover in Practice. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ferdous_et_al:LIPIcs.SEA.2024.12, author = {Ferdous, S M and Pothen, Alex and Halappanavar, Mahantesh}, title = {{Streaming Matching and Edge Cover in Practice}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {12:1--12:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.12}, URN = {urn:nbn:de:0030-drops-203773}, doi = {10.4230/LIPIcs.SEA.2024.12}, annote = {Keywords: Matching, Edge Cover, Semi-Streaming Algorithm, Parallel Algorithms, Algorithm Engineering} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Surender Baswana and Koustav Bhanja. Vital Edges for (s,t)-Mincut: Efficient Algorithms, Compact Structures, & Optimal Sensitivity Oracles. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{baswana_et_al:LIPIcs.ICALP.2024.17, author = {Baswana, Surender and Bhanja, Koustav}, title = {{Vital Edges for (s,t)-Mincut: Efficient Algorithms, Compact Structures, \& Optimal Sensitivity Oracles}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {17:1--17:20}, 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.17}, URN = {urn:nbn:de:0030-drops-201601}, doi = {10.4230/LIPIcs.ICALP.2024.17}, annote = {Keywords: maxflow, vital edges, graph algorithms, structures, st-cuts, sensitivity oracle} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. Lower Bounds for Matroid Optimization Problems with a Linear Constraint. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 56:1-56:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{doronarad_et_al:LIPIcs.ICALP.2024.56, author = {Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas}, title = {{Lower Bounds for Matroid Optimization Problems with a Linear Constraint}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {56:1--56:20}, 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.56}, URN = {urn:nbn:de:0030-drops-201990}, doi = {10.4230/LIPIcs.ICALP.2024.56}, annote = {Keywords: matroid optimization, budgeted problems, knapsack, approximation schemes} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yaniv Sadeh and Haim Kaplan. Caching Connections in Matchings. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 120:1-120:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{sadeh_et_al:LIPIcs.ICALP.2024.120, author = {Sadeh, Yaniv and Kaplan, Haim}, title = {{Caching Connections in Matchings}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {120:1--120:20}, 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.120}, URN = {urn:nbn:de:0030-drops-202639}, doi = {10.4230/LIPIcs.ICALP.2024.120}, annote = {Keywords: Caching, Matchings, Caching in Matchings, Edge Coloring, Online Algorithms} }
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 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
János Balogh, Ilan Reuven Cohen, Leah Epstein, and Asaf Levin. Truly Asymptotic Lower Bounds for Online Vector Bin Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{balogh_et_al:LIPIcs.APPROX/RANDOM.2021.8, author = {Balogh, J\'{a}nos and Cohen, Ilan Reuven and Epstein, Leah and Levin, Asaf}, title = {{Truly Asymptotic Lower Bounds for Online Vector Bin Packing}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {8:1--8: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.8}, URN = {urn:nbn:de:0030-drops-147013}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.8}, annote = {Keywords: Bin packing, online algorithms, approximation algorithms, vector packing} }
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 112, 26th Annual European Symposium on Algorithms (ESA 2018)
János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin. A New and Improved Algorithm for Online Bin Packing. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{balogh_et_al:LIPIcs.ESA.2018.5, author = {Balogh, J\'{a}nos and B\'{e}k\'{e}si, J\'{o}zsef and D\'{o}sa, Gy\"{o}rgy and Epstein, Leah and Levin, Asaf}, title = {{A New and Improved Algorithm for Online Bin Packing}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {5:1--5: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.5}, URN = {urn:nbn:de:0030-drops-94686}, doi = {10.4230/LIPIcs.ESA.2018.5}, annote = {Keywords: Bin packing, online algorithms, competitive analysis} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Martin Koutecký, Asaf Levin, and Shmuel Onn. A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 85:1-85:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{koutecky_et_al:LIPIcs.ICALP.2018.85, author = {Kouteck\'{y}, Martin and Levin, Asaf and Onn, Shmuel}, title = {{A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {85:1--85:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.85}, URN = {urn:nbn:de:0030-drops-90898}, doi = {10.4230/LIPIcs.ICALP.2018.85}, annote = {Keywords: integer programming, parameterized complexity, Graver basis, n-fold integer programming} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Janos Balogh, Jozsef Bekesi, Gyorgy Dosa, Leah Epstein, and Asaf Levin. Online Bin Packing with Cardinality Constraints Resolved. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{balogh_et_al:LIPIcs.ESA.2017.10, author = {Balogh, Janos and Bekesi, Jozsef and Dosa, Gyorgy and Epstein, Leah and Levin, Asaf}, title = {{Online Bin Packing with Cardinality Constraints Resolved}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {10:1--10:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.10}, URN = {urn:nbn:de:0030-drops-78514}, doi = {10.4230/LIPIcs.ESA.2017.10}, annote = {Keywords: Online algorithms, bin packing, cardinality constraints, lower bounds} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Leah Epstein, Asaf Levin, Danny Segev, and Oren Weimann. Improved Bounds for Online Preemptive Matching. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 389-399, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{epstein_et_al:LIPIcs.STACS.2013.389, author = {Epstein, Leah and Levin, Asaf and Segev, Danny and Weimann, Oren}, title = {{Improved Bounds for Online Preemptive Matching}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {389--399}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.389}, URN = {urn:nbn:de:0030-drops-39501}, doi = {10.4230/LIPIcs.STACS.2013.389}, annote = {Keywords: Online algorithms, matching, lower bound} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Leah Epstein, Asaf Levin, Julián Mestre, and Danny Segev. Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 347-358, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{epstein_et_al:LIPIcs.STACS.2010.2476, author = {Epstein, Leah and Levin, Asaf and Mestre, Juli\'{a}n and Segev, Danny}, title = {{Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {347--358}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2476}, URN = {urn:nbn:de:0030-drops-24766}, doi = {10.4230/LIPIcs.STACS.2010.2476}, annote = {Keywords: Approximation guarantees, semi-streaming model, one-pass algorithm} }
Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)
Asaf Levin. Approximating min-max k-clustering. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{levin:DagSemProc.07261.4, author = {Levin, Asaf}, title = {{Approximating min-max k-clustering}}, booktitle = {Fair Division}, pages = {1--5}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7261}, editor = {Steven Brams and Kirk Pruhs and Gerhard Woeginger}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.4}, URN = {urn:nbn:de:0030-drops-12282}, doi = {10.4230/DagSemProc.07261.4}, annote = {Keywords: Approximation algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)
Leah Epstein and Asaf Levin. Tracking mobile users. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)
@InProceedings{epstein_et_al:DagSemProc.05031.30, author = {Epstein, Leah and Levin, Asaf}, title = {{Tracking mobile users}}, booktitle = {Algorithms for Optimization with Incomplete Information}, pages = {1--3}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2005}, volume = {5031}, editor = {Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.30}, URN = {urn:nbn:de:0030-drops-580}, doi = {10.4230/DagSemProc.05031.30}, annote = {Keywords: mobile users , PTAS} }