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

DOI10.1016/S0304-3975(99)00181-4MaRDI QIDQ1978696zbMATH OpenOpenAlexFDO

Authors Goran Konjevod, R. Ravi, Santosh S. Vempala, Avrim 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

approximation algorithmssemi-definite programmingminimum bandwidth problem

Mathematics Subject Classification ID

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

Recommendations

• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• Semidefinite relaxations of ordering problems
• On semidefinite programming bounds for graph bandwidth
• Semidefinite relaxations for partitioning, assignment and ordering problems
• Semidefinite relaxations for partitioning, assignment and ordering problems
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• scientific article; zbMATH DE number 2119717
• Semidefinite programming relaxations for the graph partitioning problem
• scientific article; zbMATH DE number 2196288
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cites work

• scientific article; zbMATH DE number 1261808 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1775392 (Why is no real title available?)
• scientific article; zbMATH DE number 3892457 (Why is no real title available?)
• A remark on a problem of Harary
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Complexity Results for Bandwidth Minimization
• Geometric algorithms and combinatorial optimization
• Graphs with small bandwidth and cutwidth
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• The NP-completeness of the bandwidth minimization problem
• The bandwidth problem for graphs and matrices—a survey

Cited in

(15)

• An exponential time 2-approximation algorithm for bandwidth
• An exponential time 2-approximation algorithm for bandwidth
• Lower bounds for the bandwidth problem
• scientific article; zbMATH DE number 2166873 (Why is no real title available?)
• A branch and bound algorithm for the matrix bandwidth minimization
• Retracting Graphs to Cycles
• Convex relaxations for permutation problems
• Interval degree and bandwidth of a graph
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Matrix relaxations in combinatorial optimization
• Flow metrics
• Semidefinite relaxations of ordering problems
• \(\ell ^2_2\) spreading metrics for vertex ordering problems
• On semidefinite programming bounds for graph bandwidth
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems

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

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