Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Fully-Scalable MPC Algorithms for Clustering in High Dimension. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{czumaj_et_al:LIPIcs.ICALP.2024.50, author = {Czumaj, Artur and Gao, Guichen and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Vesel\'{y}, Pavel}, title = {{Fully-Scalable MPC Algorithms for Clustering in High Dimension}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {50:1--50: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.50}, URN = {urn:nbn:de:0030-drops-201938}, doi = {10.4230/LIPIcs.ICALP.2024.50}, annote = {Keywords: Massively parallel computing, high dimension, facility location, k-median, k-means} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sami Davies, Benjamin Moseley, and Heather Newman. Simultaneously Approximating All 𝓁_p-Norms in Correlation Clustering. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{davies_et_al:LIPIcs.ICALP.2024.52, author = {Davies, Sami and Moseley, Benjamin and Newman, Heather}, title = {{Simultaneously Approximating All 𝓁\underlinep-Norms in Correlation Clustering}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {52:1--52: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.52}, URN = {urn:nbn:de:0030-drops-201950}, doi = {10.4230/LIPIcs.ICALP.2024.52}, annote = {Keywords: Approximation algorithms, correlation clustering, all-norms, lp-norms} }
Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Improved Sample Complexity Bounds for Branch-And-Cut. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{balcan_et_al:LIPIcs.CP.2022.3, author = {Balcan, Maria-Florina and Prasad, Siddharth and Sandholm, Tuomas and Vitercik, Ellen}, title = {{Improved Sample Complexity Bounds for Branch-And-Cut}}, booktitle = {28th International Conference on Principles and Practice of Constraint Programming (CP 2022)}, pages = {3:1--3:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-240-2}, ISSN = {1868-8969}, year = {2022}, volume = {235}, editor = {Solnon, Christine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.3}, URN = {urn:nbn:de:0030-drops-166321}, doi = {10.4230/LIPIcs.CP.2022.3}, annote = {Keywords: Automated algorithm configuration, integer programming, machine learning theory, tree search, branch-and-bound, branch-and-cut, cutting planes, sample complexity, generalization guarantees, data-driven algorithm design} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Maria-Florina Balcan. Generalization Guarantees for Data-Driven Mechanism Design (Invited Talk). In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{balcan:LIPIcs.STACS.2022.2, author = {Balcan, Maria-Florina}, title = {{Generalization Guarantees for Data-Driven Mechanism Design}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {2:1--2:1}, 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.2}, URN = {urn:nbn:de:0030-drops-158127}, doi = {10.4230/LIPIcs.STACS.2022.2}, annote = {Keywords: mechanism configuration, algorithm configuration, machine learning, generalization guarantees} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, and David P. Woodruff. Robust Communication-Optimal Distributed Clustering Algorithms. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{awasthi_et_al:LIPIcs.ICALP.2019.18, author = {Awasthi, Pranjal and Bakshi, Ainesh and Balcan, Maria-Florina and White, Colin and Woodruff, David P.}, title = {{Robust Communication-Optimal Distributed Clustering Algorithms}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {18:1--18:16}, 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.18}, URN = {urn:nbn:de:0030-drops-105942}, doi = {10.4230/LIPIcs.ICALP.2019.18}, annote = {Keywords: robust distributed clustering, communication complexity} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Chandra Chekuri and Shalmoli Gupta. Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chekuri_et_al:LIPIcs.APPROX-RANDOM.2018.9, author = {Chekuri, Chandra and Gupta, Shalmoli}, title = {{Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {9:1--9:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.9}, URN = {urn:nbn:de:0030-drops-94136}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.9}, annote = {Keywords: Clustering, Perturbation Resilience, LP Integrality, Outliers, Beyond Worst Case Analysis} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, and Hongyang Zhang. Matrix Completion and Related Problems via Strong Duality. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{balcan_et_al:LIPIcs.ITCS.2018.5, author = {Balcan, Maria-Florina and Liang, Yingyu and Woodruff, David P. and Zhang, Hongyang}, title = {{Matrix Completion and Related Problems via Strong Duality}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {5:1--5:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.5}, URN = {urn:nbn:de:0030-drops-83583}, doi = {10.4230/LIPIcs.ITCS.2018.5}, annote = {Keywords: Non-Convex Optimization, Strong Duality, Matrix Completion, Robust PCA, Sample Complexity} }
Published in: Dagstuhl Reports, Volume 6, Issue 9 (2017)
Maria-Florina Balcan, Shai Ben-David, Ruth Urner, and Ulrike von Luxburg. Foundations of Unsupervised Learning (Dagstuhl Seminar 16382). In Dagstuhl Reports, Volume 6, Issue 9, pp. 94-109, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Article{balcan_et_al:DagRep.6.9.94, author = {Balcan, Maria-Florina and Ben-David, Shai and Urner, Ruth and von Luxburg, Ulrike}, title = {{Foundations of Unsupervised Learning (Dagstuhl Seminar 16382)}}, pages = {94--109}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {6}, number = {9}, editor = {Balcan, Maria-Florina and Ben-David, Shai and Urner, Ruth and von Luxburg, Ulrike}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.9.94}, URN = {urn:nbn:de:0030-drops-69542}, doi = {10.4230/DagRep.6.9.94}, annote = {Keywords: Machine learning, theory of computing, unsupervised learning, representation learning} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Maria-Florina Balcan, Nika Haghtalab, and Colin White. k-Center Clustering Under Perturbation Resilience. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{balcan_et_al:LIPIcs.ICALP.2016.68, author = {Balcan, Maria-Florina and Haghtalab, Nika and White, Colin}, title = {{k-Center Clustering Under Perturbation Resilience}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {68:1--68:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.68}, URN = {urn:nbn:de:0030-drops-62160}, doi = {10.4230/LIPIcs.ICALP.2016.68}, annote = {Keywords: k-center, clustering, perturbation resilience} }
Published in: Dagstuhl Reports, Volume 4, Issue 9 (2015)
Marina-Florina Balcan, Bodo Manthey, Heiko Röglin, and Tim Roughgarden. Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372). In Dagstuhl Reports, Volume 4, Issue 9, pp. 30-49, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@Article{balcan_et_al:DagRep.4.9.30, author = {Balcan, Marina-Florina and Manthey, Bodo and R\"{o}glin, Heiko and Roughgarden, Tim}, title = {{Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372)}}, pages = {30--49}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {4}, number = {9}, editor = {Balcan, Marina-Florina and Manthey, Bodo and R\"{o}glin, Heiko and Roughgarden, Tim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.9.30}, URN = {urn:nbn:de:0030-drops-48829}, doi = {10.4230/DagRep.4.9.30}, annote = {Keywords: analysis of algorithms, probabilistic analysis, smoothed analysis, approximation stability, machine learning} }
Published in: Dagstuhl Seminar Proceedings, Volume 7271, Computational Social Systems and the Internet (2007)
Maria-Florina Balcan. Item Pricing for Revenue Maximization in Combinatorial Auctions. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{balcan:DagSemProc.07271.8, author = {Balcan, Maria-Florina}, title = {{Item Pricing for Revenue Maximization in Combinatorial Auctions}}, booktitle = {Computational Social Systems and the Internet}, pages = {1--2}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7271}, editor = {Peter Cramton and Rudolf M\"{u}ller and Eva Tardos and Moshe Tennenholtz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07271.8}, URN = {urn:nbn:de:0030-drops-11534}, doi = {10.4230/DagSemProc.07271.8}, annote = {Keywords: Item Pricing, Revenue Maximizing, Combinatorial Auctions} }