Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Venkatesan Guruswami, Xuandi Ren, and Sai Sandeep. Baby PIH: Parameterized Inapproximability of Min CSP. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{guruswami_et_al:LIPIcs.CCC.2024.27, author = {Guruswami, Venkatesan and Ren, Xuandi and Sandeep, Sai}, title = {{Baby PIH: Parameterized Inapproximability of Min CSP}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {27:1--27:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.27}, URN = {urn:nbn:de:0030-drops-204237}, doi = {10.4230/LIPIcs.CCC.2024.27}, annote = {Keywords: Parameterized Inapproximability Hypothesis, Constraint Satisfaction Problems} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Theo Conrads, Lukas Drexler, Joshua Könen, Daniel R. Schmidt, and Melanie Schmidt. Local Search k-means++ with Foresight. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{conrads_et_al:LIPIcs.SEA.2024.7, author = {Conrads, Theo and Drexler, Lukas and K\"{o}nen, Joshua and Schmidt, Daniel R. and Schmidt, Melanie}, title = {{Local Search k-means++ with Foresight}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {7:1--7:20}, 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.7}, URN = {urn:nbn:de:0030-drops-203727}, doi = {10.4230/LIPIcs.SEA.2024.7}, annote = {Keywords: k-means clustering, kmeans++, greedy, local search} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abbasi_et_al:LIPIcs.ICALP.2024.6, author = {Abbasi, Fateme and Banerjee, Sandip and Byrka, Jaros{\l}aw and Chalermsook, Parinya and Gadekar, Ameet and Khodamoradi, Kamyar and Marx, D\'{a}niel and Sharma, Roohani and Spoerhase, Joachim}, title = {{Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {6:1--6:19}, 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.6}, URN = {urn:nbn:de:0030-drops-201494}, doi = {10.4230/LIPIcs.ICALP.2024.6}, annote = {Keywords: Clustering, approximation algorithms, parameterized complexity} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Nithin Parepally, Ainesh Chatterjee, Auguste H. Gezalyan, Hongyang Du, Sukrit Mangla, Kenny Wu, Sarah Hwang, and David M. Mount. Ipelets for the Convex Polygonal Geometry (Media Exposition). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 92:1-92:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{parepally_et_al:LIPIcs.SoCG.2024.92, author = {Parepally, Nithin and Chatterjee, Ainesh and Gezalyan, Auguste H. and Du, Hongyang and Mangla, Sukrit and Wu, Kenny and Hwang, Sarah and Mount, David M.}, title = {{Ipelets for the Convex Polygonal Geometry}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {92:1--92:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-316-4}, ISSN = {1868-8969}, year = {2024}, volume = {293}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.92}, URN = {urn:nbn:de:0030-drops-200375}, doi = {10.4230/LIPIcs.SoCG.2024.92}, annote = {Keywords: Hilbert metric, Macbeath Regions, Polar Bodies, Convexity} }
Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)
Auguste H. Gezalyan, Soo H. Kim, Carlos Lopez, Daniel Skora, Zofia Stefankovic, and David M. Mount. Delaunay Triangulations in the Hilbert Metric. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gezalyan_et_al:LIPIcs.SWAT.2024.25, author = {Gezalyan, Auguste H. and Kim, Soo H. and Lopez, Carlos and Skora, Daniel and Stefankovic, Zofia and Mount, David M.}, title = {{Delaunay Triangulations in the Hilbert Metric}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {25:1--25:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.25}, URN = {urn:nbn:de:0030-drops-200657}, doi = {10.4230/LIPIcs.SWAT.2024.25}, annote = {Keywords: Delaunay Triangulations, Hilbert metric, convexity, randomized algorithms} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Ahmed Abdelkader and David M. Mount. Smooth Distance Approximation. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{abdelkader_et_al:LIPIcs.ESA.2023.5, author = {Abdelkader, Ahmed and Mount, David M.}, title = {{Smooth Distance Approximation}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {5:1--5:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.5}, URN = {urn:nbn:de:0030-drops-186589}, doi = {10.4230/LIPIcs.ESA.2023.5}, annote = {Keywords: Approximation algorithms, convexity, continuity, partition of unity} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Sunil Arya and David M. Mount. Optimal Volume-Sensitive Bounds for Polytope Approximation. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arya_et_al:LIPIcs.SoCG.2023.9, author = {Arya, Sunil and Mount, David M.}, title = {{Optimal Volume-Sensitive Bounds for Polytope Approximation}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {9:1--9:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.9}, URN = {urn:nbn:de:0030-drops-178592}, doi = {10.4230/LIPIcs.SoCG.2023.9}, annote = {Keywords: Approximation algorithms, convexity, Macbeath regions} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Auguste H. Gezalyan and David M. Mount. Voronoi Diagrams in the Hilbert Metric. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gezalyan_et_al:LIPIcs.SoCG.2023.35, author = {Gezalyan, Auguste H. and Mount, David M.}, title = {{Voronoi Diagrams in the Hilbert Metric}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {35:1--35:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.35}, URN = {urn:nbn:de:0030-drops-178851}, doi = {10.4230/LIPIcs.SoCG.2023.35}, annote = {Keywords: Voronoi diagrams, Hilbert metric, convexity, randomized algorithms} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Alejandro Flores-Velazco and David M. Mount. Boundary-Sensitive Approach for Approximate Nearest-Neighbor Classification. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{floresvelazco_et_al:LIPIcs.ESA.2021.44, author = {Flores-Velazco, Alejandro and Mount, David M.}, title = {{Boundary-Sensitive Approach for Approximate Nearest-Neighbor Classification}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {44:1--44:15}, 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.44}, URN = {urn:nbn:de:0030-drops-146252}, doi = {10.4230/LIPIcs.ESA.2021.44}, annote = {Keywords: approximate nearest-neighbor searching, nearest-neighbor classification, geometric data structures, space-time tradeoffs} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Ahmed Abdelkader and David M. Mount. Approximate Nearest-Neighbor Search for Line Segments. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{abdelkader_et_al:LIPIcs.SoCG.2021.4, author = {Abdelkader, Ahmed and Mount, David M.}, title = {{Approximate Nearest-Neighbor Search for Line Segments}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {4:1--4:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.4}, URN = {urn:nbn:de:0030-drops-138039}, doi = {10.4230/LIPIcs.SoCG.2021.4}, annote = {Keywords: Approximate nearest-neighbor searching, Approximate Voronoi diagrams, Line segments, Macbeath regions} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Alejandro Flores-Velazco and David M. Mount. Coresets for the Nearest-Neighbor Rule. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 47:1-47:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{floresvelazco_et_al:LIPIcs.ESA.2020.47, author = {Flores-Velazco, Alejandro and Mount, David M.}, title = {{Coresets for the Nearest-Neighbor Rule}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {47:1--47: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.47}, URN = {urn:nbn:de:0030-drops-129138}, doi = {10.4230/LIPIcs.ESA.2020.47}, annote = {Keywords: coresets, nearest-neighbor rule, classification, nearest-neighbor condensation, training-set reduction, approximate nearest-neighbor, approximation algorithms} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Philip Dasler and David M. Mount. Online Algorithms for Warehouse Management. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 56:1-56:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dasler_et_al:LIPIcs.ISAAC.2019.56, author = {Dasler, Philip and Mount, David M.}, title = {{Online Algorithms for Warehouse Management}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {56:1--56:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.56}, URN = {urn:nbn:de:0030-drops-115526}, doi = {10.4230/LIPIcs.ISAAC.2019.56}, annote = {Keywords: Warehouse management, online algorithms, competitive analysis, robotics} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{arya_et_al:LIPIcs.ESA.2018.3, author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.}, title = {{Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {3:1--3: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.3}, URN = {urn:nbn:de:0030-drops-94664}, doi = {10.4230/LIPIcs.ESA.2018.3}, annote = {Keywords: Minkowski sum, convex intersection, width, approximation} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Ahmed Abdelkader and David M. Mount. Economical Delone Sets for Approximating Convex Bodies. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{abdelkader_et_al:LIPIcs.SWAT.2018.4, author = {Abdelkader, Ahmed and Mount, David M.}, title = {{Economical Delone Sets for Approximating Convex Bodies}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {4:1--4:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.4}, URN = {urn:nbn:de:0030-drops-88300}, doi = {10.4230/LIPIcs.SWAT.2018.4}, annote = {Keywords: Approximate polytope membership, Macbeath regions, Delone sets, Hilbert geometry} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Near-Optimal epsilon-Kernel Construction and Related Problems. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{arya_et_al:LIPIcs.SoCG.2017.10, author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.}, title = {{Near-Optimal epsilon-Kernel Construction and Related Problems}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {10:1--10: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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.10}, URN = {urn:nbn:de:0030-drops-72257}, doi = {10.4230/LIPIcs.SoCG.2017.10}, annote = {Keywords: Approximation, diameter, kernel, coreset, nearest neighbor, polytope membership, bichromatic closest pair, Macbeath regions} }