Worst-Case Analysis of Network Design Problem Heuristics

DOI10.1137/0601008zbMath0498.90032OpenAlexW1973297532MaRDI QIDQ3964299

Richard T. Wong

Publication date: 1980

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/5158

zbMATH Keywords

heuristicsupper boundNP-completenessoptimal solutionnetwork designworst-case analysisoptimal network problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical optimization and variational techniques (65K10) Deterministic network models in operations research (90B10)

Related Items

On the minimum routing cost clustered tree problem, Approximation algorithms for the optimal \(p\)-source communication spanning tree, Light graphs with small routing cost, Exact algorithms for minimum routing cost trees, Models and algorithms for network reduction, A variable fixing heuristic with local branching for the fixed charge uncapacitated network design problem with user-optimal flow, On the intercluster distance of a tree metric, Compact location problems with budget and communication constraints, Finding best swap edges minimizing the routing cost of a spanning tree, Spanning trees: A survey, On the minimum average distance spanning tree of the hypercube, Bounded-degree light approximate shortest-path trees in doubling metrics, Efficient methods for multiple sequence alignment with guaranteed error bounds, Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité, Approximation algorithms for some optimum communication spanning tree problems, The minimum routing cost tree problem. State of the art and a core-node based heuristic algorithm, Approximation algorithms for the shortest total path length spanning tree problem, DISTANCE PRESERVING SUBTREES IN MINIMUM AVERAGE DISTANCE SPANNING TREES, Low complexity variants of the arrow distributed directory

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal subset selection. Multiple regression, interdependence and optimal network algorithms
• The Complexity of Near-Optimal Graph Coloring
• On the Computational Complexity of Combinatorial Problems
• P-Complete Approximation Problems
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• The complexity of the network design problem
• Reducibility among Combinatorial Problems
• A Computational Approach to the Selection of an Optimal Network