Bicriteria Network Design Problems

DOI10.1006/jagm.1998.0930zbMath0906.68076arXivcs/9809103MaRDI QIDQ4216149

S. S. Ravi, R. Ravi, Ravi Sundaram, Madhav V. Marathe, Harry B. III Hunt, Daniel J. Rosenkrantz

Publication date: 2 December 1998

Published in: Journal of Algorithms, Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/9809103

zbMATH Keywords

approximation algorithm; cost function; Steiner tree; input graph; bicriteria network design problems; span tree

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68W40: Analysis of algorithms

90C29: Multi-objective and goal programming

68R10: Graph theory (including graph drawing) in computer science

90C59: Approximation methods and heuristics in mathematical programming

68W10: Parallel algorithms in computer science

68W25: Approximation algorithms

Related Items

Strongly polynomial-time approximation for a class of bicriteria problems., Efficient offline algorithms for the bicriteria \(k\)-server problem and online applications, Optimizing cost flows by edge cost and capacity upgrade, Budget constrained minimum cost connected medians, Modifying edges of a network to obtain short subgraphs, Approximating the weight of shallow Steiner trees, Compact location problems, A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem., Approximation algorithms for multi-parameter graph optimization problems, The maximum \(f\)-depth spanning tree problem, The non-approximability of bicriteria network design problems, Approximation algorithms for time-dependent orienteering., Competitive algorithms for the bicriteria \(k\)-server problem, Approximating \(k\)-hop minimum-spanning trees, Bounded-hops power assignment in ad hoc wireless networks, The constrained minimum weighted sum of job completion times problem, Meet and merge: approximation algorithms for confluent flows, A class of node based bottleneck improvement problems