Covering a tree with rooted subtrees -- parameterized and approximation algorithms

MaRDI QIDQ4608073zbMATH OpenFDO

Authors Lin Chen, Dániel Marx

Publication date 15 March 2018

Full work available at URL http://dl.acm.org/citation.cfm?id=3175482

zbMATH Keywords

integer programmingapproximation schemesschedulingfixed-parameter tractable

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Integer programming (90C10)

Recommendations

• Exact and approximation algorithms for the min-max \(k\)-traveling salesmen problem on a tree
• A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree
• Algorithms and Computation
• Packing and covering a tree by subtrees
• Min-max tree covers of graphs.

Cited in

(24)

• Mixed covering of trees and the augmentation problem with odd diameter constraints
• Trees with the mos subtrees - an algorithmic approach
• scientific article; zbMATH DE number 7758357 (Why is no real title available?)
• High-multiplicity \(N\)-fold IP via configuration LP
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• Block-structured integer programming: can we parameterize without the largest coefficient?
• Exact approaches for solving a covering problem with capacitated subtrees
• Faster Algorithms for Integer Programs with Block Structure
• Subset selection in sparse matrices
• Integer programming in parameterized complexity: three miniatures
• Minmax subtree cover problem on cacti
• A minimum-length covering subtree of a tree
• Two fixed-parameter algorithms for vertex covering by paths on trees
• Tight complexity lower bounds for integer linear programming with few constraints
• Approximating the minmax rooted-tree cover in a tree
• Optimal direct and indirect covering trees
• Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
• Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• Integer programming in parameterized complexity: five miniatures
• Extremal cover cost and reverse cover cost of trees with given segment sequence
• FPT algorithms for a special block-structured integer program with applications in scheduling
• Evaluating and tuning \(n\)-fold integer programming
• scientific article; zbMATH DE number 7651172 (Why is no real title available?)

This page was built for publication: Covering a tree with rooted subtrees -- parameterized and approximation algorithms

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