An approximation algorithm for MAX p-SECTION

DOI10.1007/3-540-49116-3_22MaRDI QIDQ4251055zbMATH OpenFDO

Authors Gunnar Andersson

Publication date 28 November 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-49116-3_22

zbMATH Keywords

max \(p\)-cutmax \(p\)-sectionmax bisectionmax cut

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

MAX \(p\)-SECTION is the problem of partitioning the vertices of an edge-weighted graph into \(p\) blocks of equal size such that the edges crossing block boundaries have maximum weight. The author presents a \(\big({{p-1}\over{p}} + \Theta(p^{-3})\big)\)-approximation algorithm for MAX \(p\)-SECTION based on semidefinite programming. This algorithm generalizes a prior one by \textit{A. Frieze} and \textit{M. Jerrum} [Algorithmica 18, No. 1, 67-81 (1997; Zbl 0873.68078)] for the case \(p=2\). For the entire collection see [Zbl 0909.00052].

Recommendations

• Approximate algorithms for the \(P\parallel C_{\max}\) problem
• scientific article; zbMATH DE number 1258327
• scientific article; zbMATH DE number 6129431
• scientific article; zbMATH DE number 1552232
• On the approximability of Max-Cut
• scientific article; zbMATH DE number 1670527
• Approximation Algorithms for the Max-Min Allocation Problem
• Approximation algorithms for maximization problems arising in graph partitioning
• Approximation algorithm for MAX DICUT with given sizes of parts
• Approximation algorithms for the maximum satisfiability problem

Cited in

(16)

• An \(O(mn^ 2)\) algorithm for the maximin problem in \(E^ 2\)
• On semidefinite programming relaxations of maximum \(k\)-section
• A VNS metaheuristic with stochastic steps for Max 3-cut and Max 3-section
• An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
• A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• Relaxations of combinatorial problems via association schemes
• Is constraint satisfaction over two variables always easy?
• An approximation algorithm for max k-uncut with capacity constraints
• An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding
• scientific article; zbMATH DE number 5734227 (Why is no real title available?)
• Approximation Algorithms for Max 3-Section Using Complex Semidefinite Programming Relaxation
• scientific article; zbMATH DE number 6129431 (Why is no real title available?)
• A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem
• A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis
• An improved approximation algorithm for hypergraph max p-section
• The capacitated max \(k\)-cut problem

This page was built for publication: An approximation algorithm for MAX \(p\)-SECTION

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4251055)