A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.

DOI10.1016/j.orl.2003.06.003zbMath1044.90061OpenAlexW2024840331MaRDI QIDQ1426727

Bum Hwan Park, Sung-Jin Chung, Sung-Pil Hong

Publication date: 15 March 2004

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2003.06.003

zbMATH Keywords

Spanning treeMatrix-tree theoremFully polynomial approximation schemeBicriteria approximation

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (16)

Implicit cover inequalities ⋮ Approximation of min-max and min-max regret versions of some combinatorial optimization problems ⋮ Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle ⋮ On the minimum \(s-t\) cut problem with budget constraints ⋮ General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems ⋮ Polynomial time approximation schemes for the constrained minimum spanning tree problem ⋮ Covers and approximations in multiobjective optimization ⋮ Exact algorithms for OWA-optimization in multiobjective spanning tree problems ⋮ Budgeted matching and budgeted matroid intersection via the gasoline puzzle ⋮ Approximate Pareto sets of minimal size for multi-objective optimization problems ⋮ The subdivision-constrained minimum spanning tree problem ⋮ A Survey on Multiple Objective Minimum Spanning Tree Problems ⋮ A polynomial solvable minimum risk spanning tree problem with interval data ⋮ Exact algorithms for finding constrained minimum spanning trees ⋮ When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Exact arborescences, matchings and cycles
• Matrix tree theorems
• Approximation algorithms for multi-parameter graph optimization problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• Approximation Schemes for the Restricted Shortest Path Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Bicriteria Network Design Problems
• Counting Minimum Weight Spanning Trees
• Determinant: Old Algorithms, New Insights
• The constrained minimum spanning tree problem
• A simple efficient approximation scheme for the restricted shortest path problem

This page was built for publication: A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.