An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
From MaRDI portal
Publication:4651462
DOI10.1137/S0097539703426775zbMath1112.90068MaRDI QIDQ4651462
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
Implicit cover inequalities ⋮ Evolutionary algorithms and matroid optimization problems ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix ⋮ Approximation Methods for Multiobjective Optimization Problems: A Survey ⋮ New approaches to multi-objective optimization ⋮ Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle ⋮ Polynomial time approximation schemes for the constrained minimum spanning tree problem ⋮ The subdivision-constrained minimum spanning tree problem ⋮ Delay-constrained minimum shortest path trees and related problems ⋮ A Survey on Multiple Objective Minimum Spanning Tree Problems ⋮ Exact algorithms for finding constrained minimum spanning trees
