Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix

DOI10.3934/jimo.2016.12.1249zbMath1364.90262OpenAlexW2526840193MaRDI QIDQ2358291

Fang Tian, Zi-Long Liu

Publication date: 14 June 2017

Published in: Journal of Industrial and Management Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3934/jimo.2016.12.1249

zbMATH Keywords

approximation algorithmtriangle inequalitysemidefinite relaxationcatalog segmentationLasserres SDP hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Uses Software

• YALMIP
• SDP_S

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Approximation of dense-\(\frac n2\)-subgraph and table compression problems
• Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
• From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems
• Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
• On approximation of max-vertex-cover
• An improved rounding method and semidefinite programming relaxation for graph partition
• Improved approximations for max set splitting and max NAE SAT
• An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation
• Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
• Approximation algorithms for maximum cut with limited unbalance
• Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Quasi-Random PCP and Hardness of 2-Catalog Segmentation
• Relations between average case complexity and approximation complexity
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
• Semidefinite Programming
• Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• The RPR2 rounding technique for semidefinite programs
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• Segmentation problems
• Expander flows, geometric embeddings and graph partitioning
• A .699-approximation algorithm for Max-Bisection.

This page was built for publication: Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix