Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems

DOI10.1016/S0304-3975(99)00181-4zbMath0947.90083OpenAlexW2069380066MaRDI QIDQ1978696

Goran Konjevod, Santosh Vempala, R. Ravi, Avrim L. Blum

Publication date: 4 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00181-4

zbMATH Keywords

semi-definite programmingapproximation algorithmsminimum bandwidth problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (9)

Matrix Relaxations in Combinatorial Optimization ⋮ Convex Relaxations for Permutation Problems ⋮ Flow metrics ⋮ Lower bounds for the bandwidth problem ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Interval degree and bandwidth of a graph ⋮ A branch and bound algorithm for the matrix bandwidth minimization ⋮ Retracting Graphs to Cycles ⋮ An Exponential Time 2-Approximation Algorithm for Bandwidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs with small bandwidth and cutwidth
• Geometric algorithms and combinatorial optimization
• The NP-completeness of the bandwidth minimization problem
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• The bandwidth problem for graphs and matrices—a survey
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Complexity Results for Bandwidth Minimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• A remark on a problem of Harary

This page was built for publication: Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems