Search Results

Documents authored by Cummings, Robert

Document
DOI: 10.4230/LIPIcs.ISAAC.2021.38
An Improved Approximation Algorithm for the Matching Augmentation Problem

Authors: Joseph Cheriyan, Robert Cummings, Jack Dippel, and Jasper Zhu

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We present a 5/3-approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. A 7/4-approximation algorithm for the same problem was presented recently, see Cheriyan, et al., "The matching augmentation problem: a 7/4-approximation algorithm," Math. Program., 182(1):315-354, 2020. Our improvement is based on new algorithmic techniques, and some of these may lead to advances on related problems.
Cite as

Joseph Cheriyan, Robert Cummings, Jack Dippel, and Jasper Zhu. An Improved Approximation Algorithm for the Matching Augmentation Problem. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cheriyan_et_al:LIPIcs.ISAAC.2021.38,
  author =	{Cheriyan, Joseph and Cummings, Robert and Dippel, Jack and Zhu, Jasper},
  title =	{{An Improved Approximation Algorithm for the Matching Augmentation Problem}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.38},
  URN =		{urn:nbn:de:0030-drops-154714},
  doi =		{10.4230/LIPIcs.ISAAC.2021.38},
  annote =	{Keywords: 2-Edge connected graph, 2-edge covers, approximation algorithms, connectivity augmentation, forest augmentation problem, matching augmentation problem, network design}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.61
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case

Authors: Sylvia Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, and Lu Wang

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

Abstract
Given a connected undirected graph G ̅ on n vertices, and non-negative edge costs c, the 2ECM problem is that of finding a 2-edge connected spanning multisubgraph of G ̅ of minimum cost. The natural linear program (LP) for 2ECM, which coincides with the subtour LP for the Traveling Salesman Problem on the metric closure of G ̅, gives a lower bound on the optimal cost. For instances where this LP is optimized by a half-integral solution x, Carr and Ravi (1998) showed that the integrality gap is at most 4/3: they show that the vector 4/3 x dominates a convex combination of incidence vectors of 2-edge connected spanning multisubgraphs of G ̅. We present a simpler proof of the result due to Carr and Ravi by applying an extension of Lovász’s splitting-off theorem. Our proof naturally leads to a 4/3-approximation algorithm for half-integral instances. Given a half-integral solution x to the LP for 2ECM, we give an O(n²)-time algorithm to obtain a 2-edge connected spanning multisubgraph of G ̅ whose cost is at most 4/3 c^T x.
Cite as

Sylvia Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, and Lu Wang. A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 61:1-61:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{boyd_et_al:LIPIcs.APPROX/RANDOM.2020.61,
  author =	{Boyd, Sylvia and Cheriyan, Joseph and Cummings, Robert and Grout, Logan and Ibrahimpur, Sharat and Szigeti, Zolt\'{a}n and Wang, Lu},
  title =	{{A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{61:1--61:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.61},
  URN =		{urn:nbn:de:0030-drops-126643},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.61},
  annote =	{Keywords: 2-Edge Connectivity, Approximation Algorithms, Subtour LP for TSP}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.18
Rollercoasters and Caterpillars

Authors: Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey Shallit

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence - increasing or decreasing - has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as an x-monotone polygonal path for which every maximal sub-path, with positive- or negative-slope edges, has at least three vertices. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length (not necessarily contiguous) subsequence that is a rollercoaster. It was conjectured that every sequence of n distinct real numbers contains a rollercoaster of length at least ceil[n/2] for n>7, while the best known lower bound is Omega(n/log n). In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the O(n log n)-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of {1,...,n} can be computed in O(n log log n) time. The search for rollercoasters was motivated by orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is one of maximum degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of the spine. As an application of our result on rollercoasters, we are able to find a planar drawing of every n-vertex top-view caterpillar on every set of 25/3(n+4) points in the plane, such that each edge is an orthogonal path with one bend. This improves the previous best known upper bound on the number of required points, which is O(n log n). We also show that such a drawing can be obtained in linear time, when the points are given in sorted order.
Cite as

Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey Shallit. Rollercoasters and Caterpillars. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.ICALP.2018.18,
  author =	{Biedl, Therese and Biniaz, Ahmad and Cummings, Robert and Lubiw, Anna and Manea, Florin and Nowotka, Dirk and Shallit, Jeffrey},
  title =	{{Rollercoasters and Caterpillars}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{18:1--18:15},
  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.18},
  URN =		{urn:nbn:de:0030-drops-90224},
  doi =		{10.4230/LIPIcs.ICALP.2018.18},
  annote =	{Keywords: sequences, alternating runs, patterns in permutations, caterpillars}
}
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 Imprint Privacy Contact