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

approximation schemesfixed-parameter tractableinteger programmingscheduling

Mathematics Subject Classification ID

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

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

(28)

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

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)