2 Search Results for "Uniyal, Sumedha"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.85
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints

Authors: Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase, and Sumedha Uniyal

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

Abstract
Motivated by applications in machine learning, such as subset selection and data summarization, we consider the problem of maximizing a monotone submodular function subject to mixed packing and covering constraints. We present a tight approximation algorithm that for any constant epsilon >0 achieves a guarantee of 1-(1/e)-epsilon while violating only the covering constraints by a multiplicative factor of 1-epsilon. Our algorithm is based on a novel enumeration method, which unlike previously known enumeration techniques, can handle both packing and covering constraints. We extend the above main result by additionally handling a matroid independence constraint as well as finding (approximate) pareto set optimal solutions when multiple submodular objectives are present. Finally, we propose a novel and purely combinatorial dynamic programming approach. While this approach does not give tight bounds it yields deterministic and in some special cases also considerably faster algorithms. For example, for the well-studied special case of only packing constraints (Kulik et al. [Math. Oper. Res. `13] and Chekuri et al. [FOCS `10]), we are able to present the first deterministic non-trivial approximation algorithm. We believe our new combinatorial approach might be of independent interest.
Cite as

Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase, and Sumedha Uniyal. A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 85:1-85:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mizrachi_et_al:LIPIcs.ICALP.2019.85,
  author =	{Mizrachi, Eyal and Schwartz, Roy and Spoerhase, Joachim and Uniyal, Sumedha},
  title =	{{A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{85:1--85: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.85},
  URN =		{urn:nbn:de:0030-drops-106610},
  doi =		{10.4230/LIPIcs.ICALP.2019.85},
  annote =	{Keywords: submodular function, approximation algorithm, covering, packing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.19
A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs

Authors: Parinya Chalermsook, Andreas Schmid, and Sumedha Uniyal

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph G contains a cactus subgraph C where C contains at least a 1/6 fraction of the triangular faces of G. We also show that this ratio cannot be improved by showing a tight lower bound. Together with an algorithm for linear matroid parity, our bound implies two approximation algorithms for computing "dense planar structures" inside any graph: (i) A 1/6 approximation algorithm for, given any graph G, finding a planar subgraph with a maximum number of triangular faces; this improves upon the previous 1/11-approximation; (ii) An alternate (and arguably more illustrative) proof of the 4/9 approximation algorithm for finding a planar subgraph with a maximum number of edges. Our bound is obtained by analyzing a natural local search strategy and heavily exploiting the exchange arguments. Therefore, this suggests the power of local search in handling problems of this kind.
Cite as

Parinya Chalermsook, Andreas Schmid, and Sumedha Uniyal. A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.STACS.2019.19,
  author =	{Chalermsook, Parinya and Schmid, Andreas and Uniyal, Sumedha},
  title =	{{A Tight Extremal Bound on the Lov\'{a}sz Cactus Number in Planar Graphs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.19},
  URN =		{urn:nbn:de:0030-drops-102583},
  doi =		{10.4230/LIPIcs.STACS.2019.19},
  annote =	{Keywords: Graph Drawing, Matroid Matching, Maximum Planar Subgraph, Local Search Algorithms}
}
  • Refine by Author
  • 2 Uniyal, Sumedha
  • 1 Chalermsook, Parinya
  • 1 Mizrachi, Eyal
  • 1 Schmid, Andreas
  • 1 Schwartz, Roy
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Submodular optimization and polymatroids

  • Refine by Keyword
  • 1 Graph Drawing
  • 1 Local Search Algorithms
  • 1 Matroid Matching
  • 1 Maximum Planar Subgraph
  • 1 approximation algorithm
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2019

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