Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Mónika Csikós and Nabil H. Mustafa. Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{csikos_et_al:LIPIcs.SoCG.2021.28, author = {Csik\'{o}s, M\'{o}nika and Mustafa, Nabil H.}, title = {{Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and Their Applications}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {28:1--28:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.28}, URN = {urn:nbn:de:0030-drops-138273}, doi = {10.4230/LIPIcs.SoCG.2021.28}, annote = {Keywords: Matchings, crossing numbers, approximations} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Rajiv Raman and Saurabh Ray. Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 78:1-78:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{raman_et_al:LIPIcs.ESA.2020.78, author = {Raman, Rajiv and Ray, Saurabh}, title = {{Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {78:1--78:16}, 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.78}, URN = {urn:nbn:de:0030-drops-129441}, doi = {10.4230/LIPIcs.ESA.2020.78}, annote = {Keywords: Approximation algorithms, geometry, Covering} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa. Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{huang_et_al:LIPIcs.APPROX-RANDOM.2019.32, author = {Huang, Chien-Chung and Mari, Mathieu and Mathieu, Claire and Mitchell, Joseph S. B. and Mustafa, Nabil H.}, title = {{Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {32:1--32:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.32}, URN = {urn:nbn:de:0030-drops-112471}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.32}, annote = {Keywords: approximation algorithm, submodular function optimisation, unit disk graph, connectivity constraint} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, and Erik Jan van Leeuwen. On Geometric Set Cover for Orthants. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bringmann_et_al:LIPIcs.ESA.2019.26, author = {Bringmann, Karl and Kisfaludi-Bak, S\'{a}ndor and Pilipczuk, Micha{\l} and van Leeuwen, Erik Jan}, title = {{On Geometric Set Cover for Orthants}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {26:1--26:18}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.26}, URN = {urn:nbn:de:0030-drops-111476}, doi = {10.4230/LIPIcs.ESA.2019.26}, annote = {Keywords: Set Cover, parameterized complexity, algorithms, Exponential Time Hypothesis} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Nabil H. Mustafa. Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 87:1-87:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{mustafa:LIPIcs.ICALP.2019.87, author = {Mustafa, Nabil H.}, title = {{Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {87:1--87:12}, 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.87}, URN = {urn:nbn:de:0030-drops-106632}, doi = {10.4230/LIPIcs.ICALP.2019.87}, annote = {Keywords: epsilon-nets, Geometric Set Systems} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase. Approximation Schemes for Geometric Coverage Problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chaplick_et_al:LIPIcs.ESA.2018.17, author = {Chaplick, Steven and De, Minati and Ravsky, Alexander and Spoerhase, Joachim}, title = {{Approximation Schemes for Geometric Coverage Problems}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {17:1--17:15}, 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.17}, URN = {urn:nbn:de:0030-drops-94809}, doi = {10.4230/LIPIcs.ESA.2018.17}, annote = {Keywords: balanced separators, maximum coverage, local search, approximation scheme, geometric approximation algorithms} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Nabil H. Mustafa and Saurabh Ray. On a Problem of Danzer. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 64:1-64:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{mustafa_et_al:LIPIcs.ESA.2018.64, author = {Mustafa, Nabil H. and Ray, Saurabh}, title = {{On a Problem of Danzer}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {64:1--64:8}, 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.64}, URN = {urn:nbn:de:0030-drops-95271}, doi = {10.4230/LIPIcs.ESA.2018.64}, annote = {Keywords: Convex polytopes, Hadwiger-Debrunner numbers, Epsilon-nets, Balls} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase. Brief Announcement: Approximation Schemes for Geometric Coverage Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 107:1-107:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chaplick_et_al:LIPIcs.ICALP.2018.107, author = {Chaplick, Steven and De, Minati and Ravsky, Alexander and Spoerhase, Joachim}, title = {{Brief Announcement: Approximation Schemes for Geometric Coverage Problems}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {107:1--107:4}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.107}, URN = {urn:nbn:de:0030-drops-91113}, doi = {10.4230/LIPIcs.ICALP.2018.107}, annote = {Keywords: balanced separators, maximum coverage, local search, approximation scheme, geometric approximation algorithms} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Bruno Jartoux and Nabil H. Mustafa. Optimality of Geometric Local Search. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{jartoux_et_al:LIPIcs.SoCG.2018.48, author = {Jartoux, Bruno and Mustafa, Nabil H.}, title = {{Optimality of Geometric Local Search}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {48:1--48:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.48}, URN = {urn:nbn:de:0030-drops-87615}, doi = {10.4230/LIPIcs.SoCG.2018.48}, annote = {Keywords: local search, expansion, matchings, Hall's marriage theorem} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Daniel Antunes, Claire Mathieu, and Nabil H. Mustafa. Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{antunes_et_al:LIPIcs.ESA.2017.8, author = {Antunes, Daniel and Mathieu, Claire and Mustafa, Nabil H.}, title = {{Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {8:1--8:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.8}, URN = {urn:nbn:de:0030-drops-78293}, doi = {10.4230/LIPIcs.ESA.2017.8}, annote = {Keywords: Planar graphs, Local search, Hall's theorem, Combinatorial optimization, Expansion} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Kunal Dutta, Arijit Ghosh, Bruno Jartoux, and Nabil H. Mustafa. Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{dutta_et_al:LIPIcs.SoCG.2017.38, author = {Dutta, Kunal and Ghosh, Arijit and Jartoux, Bruno and Mustafa, Nabil H.}, title = {{Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {38:1--38:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.38}, URN = {urn:nbn:de:0030-drops-71991}, doi = {10.4230/LIPIcs.SoCG.2017.38}, annote = {Keywords: Epsilon-nets, Haussler's packing lemma, Mnets, shallow-cell complexity, shallow packing lemma} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Norbert Bus, Shashwat Garg, Nabil H. Mustafa, and Saurabh Ray. Improved Local Search for Geometric Hitting Set. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 184-196, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bus_et_al:LIPIcs.STACS.2015.184, author = {Bus, Norbert and Garg, Shashwat and Mustafa, Nabil H. and Ray, Saurabh}, title = {{Improved Local Search for Geometric Hitting Set}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {184--196}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.184}, URN = {urn:nbn:de:0030-drops-49135}, doi = {10.4230/LIPIcs.STACS.2015.184}, annote = {Keywords: hitting sets, Delaunay triangulation, local search, disks, geometric algorithms} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Nabil H. Mustafa and Saurabh Ray. Near-Optimal Generalisations of a Theorem of Macbeath. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 578-589, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{mustafa_et_al:LIPIcs.STACS.2014.578, author = {Mustafa, Nabil H. and Ray, Saurabh}, title = {{Near-Optimal Generalisations of a Theorem of Macbeath}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {578--589}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.578}, URN = {urn:nbn:de:0030-drops-44890}, doi = {10.4230/LIPIcs.STACS.2014.578}, annote = {Keywords: Epsilon Nets, Cuttings, Union Complexity, Geometric Set systems, Convex Geometry} }
Feedback for Dagstuhl Publishing