On approximability of linear ordering and related NP-optimization problems on graphs.

DOI10.1016/S0166-218X(03)00444-XzbMath1066.68162OpenAlexW1985462729MaRDI QIDQ1427183

Sounaka Mishra, Kripasindhu Sikdar

Publication date: 14 March 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00444-x

zbMATH Keywords

Approximation algorithmLP-relaxationAPX-completenessFeedback set problemLinear ordering polytopeLinear ordering problemNPO problemParametrized triangle inequality

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (1)

Analysis of a generalized linear ordering problem via integer programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completeness in approximation classes
• Non deterministic polynomial optimization problems and their approximations
• Optimization, approximation, and complexity classes
• Generalized transitive tournaments and doubly stochastic matrices
• Approximating maximum independent sets by excluding subgraphs
• On removing a vertex from the assignment polytope
• Parallel concepts in graph theory
• Approximation algorithms for multi-dimensional assignment problems with decomposable costs
• A new heuristic algorithm solving the linear ordering problem
• On weighted vs unweighted versions of combinatorial optimization problems
• \((0,{1\over 2},1)\) matrices which are extreme points of the generalized transitive tournament polytope
• Packing directed circuits fractionally
• On non-\(\{0,{1\over 2},1\}\) extreme points of the generalized transitive tournament polytope
• A threshold of ln n for approximating set cover
• A Cutting Plane Algorithm for the Linear Ordering Problem
• On the acyclic subgraph polytope
• A New Lower Bound Via Projection for the Quadratic Assignment Problem
• Vertex packings: Structural properties and algorithms
• `` Strong NP-Completeness Results
• Structure in Approximation Classes
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities

This page was built for publication: On approximability of linear ordering and related NP-optimization problems on graphs.