An improved approximation ratio for the jump number problem on interval orders

DOI10.1016/J.TCS.2013.10.011MaRDI QIDQ391978zbMATH OpenOpenAlexFDO

Authors Przemysław Krysztowiak

Publication date 13 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.10.011

zbMATH Keywords

combinatorial optimizationapproximation algorithmset coverposetgraph packinglinear extensioninterval orderjump number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorics of partially ordered sets (06A07)

Recommendations

• A refined analysis on the jump number problem of interval orders
• A 3/2-approximation algorithm for the jump number of interval orders
• The jump number problem on interval orders: A 3/2 approximation algorithm
• scientific article; zbMATH DE number 764417
• Tackling the jump number of interval orders

Cites work

• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• A 3/2-approximation algorithm for the jump number of interval orders
• An algorithm for solving the jump number problem
• Computing the jump number on semi-orders is polynomial
• NP-completeness properties about linear extensions
• On the Complexity of General Graph Factor Problems
• Packing subgraphs in a graph
• Tackling the jump number of interval orders
• The jump number problem on interval orders: A 3/2 approximation algorithm

Cited in

(8)

• scientific article; zbMATH DE number 764417 (Why is no real title available?)
• A 3/2-approximation algorithm for the jump number of interval orders
• The jump number problem on interval orders: A 3/2 approximation algorithm
• A refined analysis on the jump number problem of interval orders
• On a setup optimization problem for interval orders
• A tabu search approach to the jump number problem
• scientific article; zbMATH DE number 3948306 (Why is no real title available?)
• The jump number problem: exact and parameterized

This page was built for publication: An improved approximation ratio for the jump number problem on interval orders

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