Many birds with one stone

DOI10.1145/167088.167209zbMath1310.68247OpenAlexW2002764437MaRDI QIDQ5248513

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

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167209

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Approximation algorithms (68W25)

Related Items (41)

On approximating degree-bounded network design problems ⋮ ILP formulation of the degree-constrained minimum spanning hierarchy problem ⋮ The constrained minimum spanning tree problem ⋮ Spanning trees with minimum weighted degrees ⋮ Efficient offline algorithms for the bicriteria \(k\)-server problem and online applications ⋮ What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs ⋮ Optimizing cost flows by edge cost and capacity upgrade ⋮ On generalizations of network design problems with degree bounds ⋮ On the approximability of some maximum spanning tree problems ⋮ On the approximability of some Maximum Spanning Tree Problems ⋮ Multi-objective Problems in Terms of Relational Algebra ⋮ Compact location problems with budget and communication constraints ⋮ New approaches to multi-objective optimization ⋮ The multi-weighted spanning tree problem ⋮ Complexity and approximability of certain bicriteria location problems ⋮ Approximating directed weighted-degree constrained networks ⋮ Network design with weighted degree constraints ⋮ Competitive algorithms for the bicriteria \(k\)-server problem ⋮ Approximating some network design problems with node costs ⋮ Refuting a conjecture of goemans on bounded degree spanning trees ⋮ Approximating Directed Weighted-Degree Constrained Networks ⋮ A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem ⋮ A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees ⋮ Simultaneous approximation of multi-criteria submodular function maximization ⋮ Bi-objective matchings with the triangle inequality ⋮ Binary Steiner trees: structural results and an exact solution approach ⋮ Budgeted matching and budgeted matroid intersection via the gasoline puzzle ⋮ Using Lagrangian dual information to generate degree constrained spanning trees ⋮ On approximating degree-bounded network design problems ⋮ Sublogarithmic approximation for telephone multicast ⋮ Network Design with Weighted Degree Constraints ⋮ Bulk-robust combinatorial optimization ⋮ Data aggregation in sensor networks: Balancing communication and delay costs ⋮ Modifying edges of a network to obtain short subgraphs ⋮ Euclidean bottleneck bounded-degree spanning tree ratios ⋮ Socially fair network design via iterative rounding ⋮ Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal ⋮ Bicriteria Network Design Problems ⋮ Approximating the weight of shallow Steiner trees ⋮ Stack-up algorithms for palletizing at delivery industry ⋮ Efficiently computing succinct trade-off curves

This page was built for publication: Many birds with one stone