Publication:4216149

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

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

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 algorithmcost functionSteiner treeinput graphbicriteria network design problemsspan tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Multi-objective and goal programming (90C29) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)

Related Items (59)

Service-constrained network design problems ⋮ The constrained minimum spanning tree problem ⋮ Real time scheduling with a budget: parametric-search is better than binary search ⋮ Finding bounded diameter minimum spanning tree in general graphs ⋮ Efficient offline algorithms for the bicriteria \(k\)-server problem and online applications ⋮ Exact algorithms for bi-objective ring tree problems with reliability measures ⋮ On some network design problems with degree constraints ⋮ A general approximation method for bicriteria minimization problems ⋮ Optimizing cost flows by edge cost and capacity upgrade ⋮ Budget constrained minimum cost connected medians ⋮ The density maximization problem in graphs ⋮ Compact location problems ⋮ Approximability results for the $p$-centdian and the converse centdian problems ⋮ Compact location problems with budget and communication constraints ⋮ New approaches to multi-objective optimization ⋮ Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle ⋮ Approximability results for the converse connectedp-centre problem^† ⋮ Complexity and approximability of certain bicriteria location problems ⋮ On solving bi-objective constrained minimum spanning tree problems ⋮ Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem ⋮ Optimal Network Design with End-to-End Service Requirements ⋮ Competitive algorithms for the bicriteria \(k\)-server problem ⋮ Approximation algorithms for priority Steiner tree problems ⋮ Approximating some network design problems with node costs ⋮ Minimum diameter cost-constrained Steiner trees ⋮ Polynomial time approximation schemes for the constrained minimum spanning tree problem ⋮ A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. ⋮ Modeling and solving the bi-objective minimum diameter-cost spanning tree problem ⋮ Budgeted matching and budgeted matroid intersection via the gasoline puzzle ⋮ Approximating \(k\)-hop minimum-spanning trees ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ Strongly polynomial-time approximation for a class of bicriteria problems. ⋮ 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 ⋮ Bi-criteria path problem with minimum length and maximum survival probability ⋮ Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph ⋮ A new model for path planning with interval data ⋮ Minimum diameter vertex-weighted Steiner tree ⋮ Data aggregation in sensor networks: Balancing communication and delay costs ⋮ Realization problems on reachability sequences ⋮ Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees ⋮ Network-Design with Degree Constraints ⋮ Modifying edges of a network to obtain short subgraphs ⋮ A polynomial solvable minimum risk spanning tree problem with interval data ⋮ The non-approximability of bicriteria network design problems ⋮ Bicriteria Data Compression ⋮ Exact algorithms for finding constrained minimum spanning trees ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ An exact method for solving the bi-objective Minimum Diameter-Cost Spanning Tree Problem ⋮ Approximating the weight of shallow Steiner trees ⋮ Improving spanning trees by upgrading nodes ⋮ Approximation algorithms for time-dependent orienteering. ⋮ Approximate tradeoffs on weighted labeled matroids ⋮ Approximation algorithms for multi-parameter graph optimization problems ⋮ The maximum \(f\)-depth spanning tree problem ⋮ Reducing the diameter of a unit disk graph via node addition ⋮ When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem

Cites Work

• Graph minors. IV: Tree-width and well-quasi-ordering
• Easy problems for tree-decomposable graphs
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Approximation Schemes for the Restricted Shortest Path Problem
• An algebraic theory of graph reduction
• Linear-time computation of optimal subgraphs of decomposable graphs
• Routing to Multiple Destinations in Computer Networks
• The Bounded Path Tree Problem
• Approximation Algorithms for Minimum-Time Broadcast
• On the hardness of approximating minimization problems
• Efficient probabilistically checkable proofs and applications to approximations
• Many birds with one stone
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Bicriteria Network Design Problems