1 Search Results for "Vahidi, Soroush"

Document
DOI: 10.4230/LIPIcs.ESA.2023.93
Approximating Connected Maximum Cuts via Local Search

Authors: Baruch Schieber and Soroush Vahidi

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
The Connected Max Cut (CMC) problem takes in an undirected graph G(V,E) and finds a subset S ⊆ V such that the induced subgraph G[S] is connected and the number of edges connecting vertices in S to vertices in V⧵S is maximized. This problem is closely related to the Max Leaf Degree (MLD) problem. The input to the MLD problem is an undirected graph G(V,E) and the goal is to find a subtree of G that maximizes the degree (in G) of its leaves. [Gandhi et al. 2018] observed that an α-approximation for the MLD problem induces an 𝒪(α)-approximation for the CMC problem. We present an 𝒪(log log |V|)-approximation algorithm for the MLD problem via local search. This implies an 𝒪(log log |V|)-approximation algorithm for the CMC problem. Thus, improving (exponentially) the best known 𝒪(log |V|) approximation of the Connected Max Cut problem [Hajiaghayi et al. 2015].
Cite as

Baruch Schieber and Soroush Vahidi. Approximating Connected Maximum Cuts via Local Search. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 93:1-93:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{schieber_et_al:LIPIcs.ESA.2023.93,
  author =	{Schieber, Baruch and Vahidi, Soroush},
  title =	{{Approximating Connected Maximum Cuts via Local Search}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{93:1--93:17},
  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.93},
  URN =		{urn:nbn:de:0030-drops-187466},
  doi =		{10.4230/LIPIcs.ESA.2023.93},
  annote =	{Keywords: approximation algorithms, graph theory, max-cut, local search}
}
  • Refine by Author
  • 1 Schieber, Baruch
  • 1 Vahidi, Soroush

  • Refine by Classification

  • Refine by Keyword
  • 1 approximation algorithms
  • 1 graph theory
  • 1 local search
  • 1 max-cut

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

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