Search Results

Documents authored by Maggs, Bruce

Found 3 Possible Name Variants:

Maggs, Bruce M.

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.70
Universal Algorithms for Clustering Problems

Authors: Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
This paper presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers such that they are a good solution for any subset of clients that actually realize. Specifically, we aim for low regret, defined as the maximum over all subsets of the difference between the cost of the algorithm’s solution and that of an optimal solution. A universal algorithm’s solution sol for a clustering problem is said to be an (α, β)-approximation if for all subsets of clients C', it satisfies sol(C') ≤ α ⋅ opt(C') + β ⋅ mr, where opt(C') is the cost of the optimal solution for clients C' and mr is the minimum regret achievable by any solution. Our main results are universal algorithms for the standard clustering objectives of k-median, k-means, and k-center that achieve (O(1), O(1))-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other 𝓁_p-objectives and the setting where some subset of the clients are fixed. We also give hardness results showing that (α, β)-approximation is NP-hard if α or β is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (O(1), O(1))-approximation is the strongest type of guarantee obtainable for universal clustering.
Cite as

Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi. Universal Algorithms for Clustering Problems. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 70:1-70:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.ICALP.2021.70,
  author =	{Ganesh, Arun and Maggs, Bruce M. and Panigrahi, Debmalya},
  title =	{{Universal Algorithms for Clustering Problems}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{70:1--70:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.70},
  URN =		{urn:nbn:de:0030-drops-141397},
  doi =		{10.4230/LIPIcs.ICALP.2021.70},
  annote =	{Keywords: universal algorithms, clustering, k-median, k-means, k-center}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.54
Robust Algorithms for TSP and Steiner Tree

Authors: Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defined as the maximum difference between the solution’s cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in P, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in NP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems.
Cite as

Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi. Robust Algorithms for TSP and Steiner Tree. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.ICALP.2020.54,
  author =	{Ganesh, Arun and Maggs, Bruce M. and Panigrahi, Debmalya},
  title =	{{Robust Algorithms for TSP and Steiner Tree}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{54:1--54:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.54},
  URN =		{urn:nbn:de:0030-drops-124619},
  doi =		{10.4230/LIPIcs.ICALP.2020.54},
  annote =	{Keywords: Robust optimization, Steiner tree, traveling salesman problem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.70
Retracting Graphs to Cycles

Authors: Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We initiate the algorithmic study of retracting a graph into a cycle in the graph, which seeks a mapping of the graph vertices to the cycle vertices so as to minimize the maximum stretch of any edge, subject to the constraint that the restriction of the mapping to the cycle is the identity map. This problem has its roots in the rich theory of retraction of topological spaces, and has strong ties to well-studied metric embedding problems such as minimum bandwidth and 0-extension. Our first result is an O(min{k, sqrt{n}})-approximation for retracting any graph on n nodes to a cycle with k nodes. We also show a surprising connection to Sperner’s Lemma that rules out the possibility of improving this result using certain natural convex relaxations of the problem. Nevertheless, if the problem is restricted to planar graphs, we show that we can overcome these integrality gaps by giving an optimal combinatorial algorithm, which is the technical centerpiece of the paper. Building on our planar graph algorithm, we also obtain a constant-factor approximation algorithm for retraction of points in the Euclidean plane to a uniform cycle.
Cite as

Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram. Retracting Graphs to Cycles. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 70:1-70:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{haney_et_al:LIPIcs.ICALP.2019.70,
  author =	{Haney, Samuel and Liaee, Mehraneh and Maggs, Bruce M. and Panigrahi, Debmalya and Rajaraman, Rajmohan and Sundaram, Ravi},
  title =	{{Retracting Graphs to Cycles}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{70:1--70:15},
  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.70},
  URN =		{urn:nbn:de:0030-drops-106462},
  doi =		{10.4230/LIPIcs.ICALP.2019.70},
  annote =	{Keywords: Graph algorithms, Graph embedding, Planar graphs, Approximation algorithms}
}

Maggs, Bruce MacDowell

Document
DOI: 10.4230/DagRep.7.1.74
Network Function Virtualization in Software Defined Infrastructures (Dagstuhl Seminar 17032)

Authors: David Hausheer, Oliver Hohlfeld, Diego R. López, Bruce MacDowell Maggs, and Costin Raiciu

Published in: Dagstuhl Reports, Volume 7, Issue 1 (2017)

Abstract
The softwarization of networks by introducing concepts such as Software-Defined Networking (SDN) or Network Functions Virtualization (NFV) currently massively changes network management by enabling more flexible communication networks. The main goal of this seminar was to gather researchers from academia, industry, and standardization bodies to discuss a joint perspective on research questions in the field of NFV. This report contains talk summaries, reports on the discussion groups, as well as the personal statements and main challenges contributed by the seminar participants.
Cite as

David Hausheer, Oliver Hohlfeld, Diego R. López, Bruce MacDowell Maggs, and Costin Raiciu. Network Function Virtualization in Software Defined Infrastructures (Dagstuhl Seminar 17032). In Dagstuhl Reports, Volume 7, Issue 1, pp. 74-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{hausheer_et_al:DagRep.7.1.74,
  author =	{Hausheer, David and Hohlfeld, Oliver and López, Diego R. and Maggs, Bruce MacDowell and Raiciu, Costin},
  title =	{{Network Function Virtualization in Software Defined Infrastructures (Dagstuhl Seminar 17032)}},
  pages =	{74--102},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{1},
  editor =	{Hausheer, David and Hohlfeld, Oliver and López, Diego R. and Maggs, Bruce MacDowell and Raiciu, Costin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.1.74},
  URN =		{urn:nbn:de:0030-drops-72464},
  doi =		{10.4230/DagRep.7.1.74},
  annote =	{Keywords: flexible network management, network function virtualization, software-defined networking}
}

Maggs, Bruce

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.9
Symmetric Interdiction for Matching Problems

Authors: Samuel Haney, Bruce Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
Motivated by denial-of-service network attacks, we introduce the symmetric interdiction model, where both the interdictor and the optimizer are subject to the same constraints of the underlying optimization problem. We give a general framework that relates optimization to symmetric interdiction for a broad class of optimization problems. We then study the symmetric matching interdiction problem - with applications in traffic engineering - in more detail. This problem can be simply stated as follows: find a matching whose removal minimizes the size of the maximum matching in the remaining graph. We show that this problem is APX-hard, and obtain a 3/2-approximation algorithm that improves on the approximation guarantee provided by the general framework.
Cite as

Samuel Haney, Bruce Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram. Symmetric Interdiction for Matching Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{haney_et_al:LIPIcs.APPROX-RANDOM.2017.9,
  author =	{Haney, Samuel and Maggs, Bruce and Maiti, Biswaroop and Panigrahi, Debmalya and Rajaraman, Rajmohan and Sundaram, Ravi},
  title =	{{Symmetric Interdiction for Matching Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.9},
  URN =		{urn:nbn:de:0030-drops-75587},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.9},
  annote =	{Keywords: Approximation algorithms, matching, interdiction Digital Object}
}
Document
DOI: 10.4230/DagSemRep.246
Parallel and Distributed Algorithms (Dagstuhl Seminar 99291)

Authors: Bruce Maggs, Friedhelm Meyer auf der Heide, and Ernst W. Mayr

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Bruce Maggs, Friedhelm Meyer auf der Heide, and Ernst W. Mayr. Parallel and Distributed Algorithms (Dagstuhl Seminar 99291). Dagstuhl Seminar Report 246, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{maggs_et_al:DagSemRep.246,
  author =	{Maggs, Bruce and Meyer auf der Heide, Friedhelm and Mayr, Ernst W.},
  title =	{{Parallel and Distributed Algorithms (Dagstuhl Seminar 99291)}},
  pages =	{1--22},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{246},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.246},
  URN =		{urn:nbn:de:0030-drops-151326},
  doi =		{10.4230/DagSemRep.246},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact