On the approximability of digraph ordering

DOI10.1007/s00453-016-0227-7zbMath1372.68302arXiv1507.00662OpenAlexW2952768013MaRDI QIDQ2408167

Sreyash Kenkre, Manish Purohit, Vinayaka Pandit, Rishi Saket

Publication date: 10 October 2017

Published in: Algorithmica, Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.00662

zbMATH Keywords

approximation algorithmsvertex orderingSherali-Adamssoft precedence constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

On the approximability of digraph ordering ⋮ Unnamed Item

Cites Work

• An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Parallel approximation algorithms by positive linear programming
• On the approximability of digraph ordering
• Hardness of Graph Pricing Through Generalized Max-Dicut
• Local Global Tradeoffs in Metric Embeddings
• Hardness of Vertex Deletion and Project Scheduling
• On the power of unique 2-prover 1-round games
• On Hardness of Pricing Items for Single-Minded Bidders
• Deleting vertices to bound path length
• Integrality gaps for Sherali-Adams relaxations
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the approximability of digraph ordering