Approximation Algorithm for Norm Multiway Cut

Medientyp: E-Artikel; Sonstige Veröffentlichung; Elektronischer Konferenzbericht

Titel: Approximation Algorithm for Norm Multiway Cut

Beteiligte: Carlson, Charlie [VerfasserIn]; Jafarov, Jafar [VerfasserIn]; Makarychev, Konstantin [VerfasserIn]; Makarychev, Yury [VerfasserIn]; Shan, Liren [VerfasserIn]

Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023

Sprache: Englisch

DOI: https://doi.org/10.4230/LIPIcs.ESA.2023.32

Schlagwörter: Multiway cut ; Approximation algorithms

Entstehung:

Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.

Beschreibung: We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph G into k parts so as to separate k given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced 𝓁_p-norm Multiway Cut, a generalization of the problem, in which the goal is to minimize the 𝓁_p norm of the edge boundaries of k parts. We provide an O(log^{1/2} nlog^{1/2+1/p} k) approximation algorithm for this problem, improving upon the approximation guarantee of O(log^{3/2} n log^{1/2} k) due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an O(log^{1/2} n log^{7/2} k) approximation algorithm with a weaker oracle and an O(log^{1/2} n log^{5/2} k) approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no n^{1/4-ε} approximation algorithm for every ε > 0 assuming the Hypergraph Dense-vs-Random Conjecture.

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: