3 Search Results for "Katzelnick, Dor"

Document
DOI: 10.4230/LIPIcs.ITCS.2025.15
Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems

Authors: Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar, and Saket Saurabh

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In this paper, we begin the exploration of vertex-ordering problems through the lens of exponential-time approximation algorithms. In particular, we ask the following question: Can we simultaneously beat the running times of the fastest known (exponential-time) exact algorithms and the best known approximation factors that can be achieved in polynomial time? Following the recent research initiated by Esmer et al. (ESA 2022, IPEC 2023, SODA 2024) on vertex-subset problems, and by Inamdar et al. (ITCS 2024) on graph-partitioning problems, we focus on vertex-ordering problems. In particular, we give positive results for Feedback Arc Set, Optimal Linear Arrangement, Cutwidth, and Pathwidth. Most of our algorithms build upon a novel "balanced-cut" approach - which is our main conceptual contribution. This allows us to solve various problems in very general settings allowing for directed and arc-weighted input graphs. Our main technical contribution is a (1+ε)-approximation for any ε > 0 for (weighted) Feedback Arc Set in O^*((2-δ_ε)^n) time, where δ_ε > 0 is a constant only depending on ε.
Cite as

Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar, and Saket Saurabh. Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ITCS.2025.15,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Inamdar, Tanmay and Saurabh, Saket},
  title =	{{Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.15},
  URN =		{urn:nbn:de:0030-drops-226431},
  doi =		{10.4230/LIPIcs.ITCS.2025.15},
  annote =	{Keywords: Feedback Arc Set, Cutwidth, Optimal Linear Arrangement, Pathwidth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.69
An Improved Approximation Algorithm for the Max-3-Section Problem

Authors: Dor Katzelnick, Aditya Pillai, Roy Schwartz, and Mohit Singh

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

Abstract
We consider the Max--Section problem, where we are given an undirected graph G=(V,E)equipped with non-negative edge weights w: E → R_+ and the goal is to find a partition of V into three equisized parts while maximizing the total weight of edges crossing between different parts. Max-3-Section is closely related to other well-studied graph partitioning problems, e.g., Max-Cut, Max-3-Cut, and Max-Bisection. We present a polynomial time algorithm achieving an approximation of 0.795, that improves upon the previous best known approximation of 0.673. The requirement of multiple parts that have equal sizes renders Max-3-Section much harder to cope with compared to, e.g., Max-Bisection. We show a new algorithm that combines the existing approach of Lassere hierarchy along with a random cut strategy that suffices to give our result.
Cite as

Dor Katzelnick, Aditya Pillai, Roy Schwartz, and Mohit Singh. An Improved Approximation Algorithm for the Max-3-Section Problem. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 69:1-69:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{katzelnick_et_al:LIPIcs.ESA.2023.69,
  author =	{Katzelnick, Dor and Pillai, Aditya and Schwartz, Roy and Singh, Mohit},
  title =	{{An Improved Approximation Algorithm for the Max-3-Section Problem}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{69:1--69: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.69},
  URN =		{urn:nbn:de:0030-drops-187229},
  doi =		{10.4230/LIPIcs.ESA.2023.69},
  annote =	{Keywords: Approximation Algorithms, Semidefinite Programming, Max-Cut, Max-Bisection}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.49
Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains

Authors: Dor Katzelnick and Roy Schwartz

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

Abstract
Correlation Clustering is an elegant model where given a graph with edges labeled + or -, the goal is to produce a clustering that agrees the most with the labels: + edges should reside within clusters and - edges should cross between clusters. In this work we study the MaxCorr objective, aiming to find a clustering that maximizes the difference between edges classified correctly and incorrectly. We focus on the case of bipartite graphs and present an improved approximation of 0.254, improving upon the known approximation of 0.219 given by Charikar and Wirth [FOCS`2004] and going beyond the 0.2296 barrier imposed by their technique. Our algorithm is inspired by Krivine’s method for bounding Grothendieck’s constant, and we extend this method to allow for more than two clusters in the output. Moreover, our algorithm leads to two additional results: (1) the first known approximation guarantees for MaxCorr where the output is constrained to have a bounded number of clusters; and (2) a natural extension of Grothendieck’s inequality to large domains.
Cite as

Dor Katzelnick and Roy Schwartz. Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{katzelnick_et_al:LIPIcs.APPROX/RANDOM.2020.49,
  author =	{Katzelnick, Dor and Schwartz, Roy},
  title =	{{Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{49:1--49:18},
  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.49},
  URN =		{urn:nbn:de:0030-drops-126525},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.49},
  annote =	{Keywords: Correlation Clustering, Grothendieck’s Inequality, Approximation}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023
  • 1 2020

  • Refine by Author
  • 2 Katzelnick, Dor
  • 2 Schwartz, Roy
  • 1 Bentert, Matthias
  • 1 Fomin, Fedor V.
  • 1 Inamdar, Tanmay
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Approximation algorithms analysis
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → Semidefinite programming

  • Refine by Keyword
  • 1 Approximation
  • 1 Approximation Algorithms
  • 1 Correlation Clustering
  • 1 Cutwidth
  • 1 Feedback Arc Set
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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