Approximating Minimum Linear Ordering Problems

DOI10.1007/978-3-642-32512-0_18MaRDI QIDQ3167397zbMATH OpenOpenAlexFDO

Authors Satoru Iwata, Pushkar Tripathi, Prasad Tetali

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32512-0_18

Mathematics Subject Classification ID

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

Recommendations

• On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
• A General Framework for Approximating Min Sum Ordering Problems
• New Approximation Techniques for Some Linear Ordering Problems
• scientific article; zbMATH DE number 1759471
• scientific article; zbMATH DE number 3902051
• Approximation algorithms for minimum norm and ordered optimization problems
• The linear ordering problem: instances, search space analysis and algorithms
• An Approximate Minimum Degree Ordering Algorithm
• On approximability of linear ordering and related NP-optimization problems on graphs.
• On approximability of linear ordering and related NP-optimization problems on graphs (extended abstract)

Cited in

(11)

• On Submodular Search and Machine Scheduling
• On approximability of linear ordering and related NP-optimization problems on graphs.
• A General Framework for Approximating Min Sum Ordering Problems
• scientific article; zbMATH DE number 1303559 (Why is no real title available?)
• scientific article; zbMATH DE number 5556488 (Why is no real title available?)
• An improved approximation ratio for the minimum linear arrangement problem
• Hardness and approximation of submodular minimum linear ordering problems
• scientific article; zbMATH DE number 1759471 (Why is no real title available?)
• Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues
• On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
• On min sum vertex cover and generalized min sum set cover

This page was built for publication: Approximating Minimum Linear Ordering Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167397)