An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph

DOI10.1016/j.ipl.2014.09.008zbMath1302.68317arXiv1405.0456OpenAlexW2104651156MaRDI QIDQ477619

Michał Włodarczyk, Fabrizio Grandoni, Tomasz Kociumaka

Publication date: 9 December 2014

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingdirected graphsapproximation algorithmsderandomizationvertex pricing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

On the approximability of digraph ordering

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees
• A quasi-PTAS for unsplittable flow on line graphs
• Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply
• Maximum directed cuts in acyclic digraphs
• A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs
• Single-minded unlimited supply pricing on sparse instances
• A Sublogarithmic Approximation for Highway and Tollbooth Pricing
• On Hardness of Pricing Items for Single-Minded Bidders
• On Profit-Maximizing Pricing for the Highway and Tollbooth Problems
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation

This page was built for publication: An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph