On the approximability of digraph ordering
From MaRDI portal
Publication:2408167
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
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)
Related Items (2)
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