^2_2 spreading metrics for vertex ordering problems
DOI10.1007/S00453-008-9191-1zbMATH Open1194.68259OpenAlexW3004468478MaRDI QIDQ848848FDOQ848848
Publication date: 23 February 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9191-1
Recommendations
- scientific article; zbMATH DE number 1303559
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
- New Approximation Techniques for Some Linear Ordering Problems
- Divide-and-conquer approximation algorithms via spreading metrics
- scientific article; zbMATH DE number 2086253
semidefinite programmingapproximation algorithmminimum linear arrangementminimum containing interval graphminimum storage-time productvertex ordering problem
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Semidefinite programming (90C22) Approximation algorithms (68W25) Distance in graphs (05C12)
Cites Work
- Applications of a Planar Separator Theorem
- The geometry of graphs and some of its algorithmic applications
- Measured descent: A new embedding method for finite metrics
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Euclidean distortion and the sparsest cut
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Expander flows, geometric embeddings and graph partitioning
- Approximating minimum feedback sets and multicuts in directed graphs
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
- A framework for solving VLSI graph layout problems
- Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
- A unified approach to domination problems on interval graphs
- On Lipschitz embedding of finite metric spaces in Hilbert space
- On distance scales, embeddings, and efficient relaxations of the cut cone
- Fast Approximate Graph Partitioning Algorithms
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Divide-and-conquer approximation algorithms via spreading metrics
- Low-distortion embeddings of general metrics into the line
- Packing directed circuits fractionally
- Improved approximation algorithms for minimum-weight vertex separators
- Title not available (Why is that?)
- An improved approximation ratio for the minimum linear arrangement problem
- Title not available (Why is that?)
- Low-dimensional embedding with extra information
- Integrality gaps for sparsest cut and minimum linear arrangement problems
Cited In (10)
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- \(d\)-dimensional arrangement revisited
- Distributed balanced partitioning via linear embedding
- Title not available (Why is that?)
- Flow metrics
- On a class of metrics related to graph layout problems
- Convex Relaxations for Permutation Problems
- Hardness and approximation of submodular minimum linear ordering problems
- New Approximation Techniques for Some Linear Ordering Problems
- Demand-aware network designs of bounded degree
This page was built for publication: \(\ell ^2_2\) spreading metrics for vertex ordering problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q848848)