Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph (Q5963643): Difference between revisions

Latest revision as of 12:02, 11 July 2024

scientific article; zbMATH DE number 6544331

Language	Label	Description	Also known as
English	Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph	scientific article; zbMATH DE number 6544331

Statements

instance of

scholarly article

0 references

title

Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph (English)

0 references

author

M. Reza Khani

0 references

Mohammad R. Salavatipour

0 references

published in

Journal of Combinatorial Optimization

0 references

publication date

23 February 2016

0 references

zbMATH Keywords

combinatorial optimization

0 references

approximation algorithms

0 references

network design

0 references

Steiner tree

0 references

\(k\)-edge connected

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/s10878-014-9774-5

0 references

cites work

Approximating the Single-Sink Link-Installation Problem in Network Design

0 references

Approximation algorithms for access network design

0 references

Buy-at-Bulk Network Design with Protection

0 references

A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs

0 references

New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen

0 references

Q4542533

0 references

Generalized submodular cover problems and applications

0 references

Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems

0 references

Detecting high log-densities

0 references

A constant-factor approximation algorithm for the \(k\)-MST problem

0 references

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

0 references

Q2768299

0 references

Q2934722

0 references

Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design

0 references

Q2921762

0 references

Min-max tree covers of graphs.

0 references

A tight bound on approximating arbitrary metrics by tree metrics

0 references

Saving an epsilon

0 references

A Constant Factor Approximation for the Single Sink Edge Installation Problem

0 references

Q5417728

0 references

Simpler and better approximation algorithms for network design

0 references

Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees

0 references

Approximation Schemes for the Restricted Shortest Path Problem

0 references

Q4411286

0 references

A factor 2 approximation algorithm for the generalized Steiner network problem

0 references

Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems

0 references

Approximating Some Network Design Problems with Node Costs

0 references

Survivable Network Design with Degree or Order Constraints

0 references

Bicriteria Network Design Problems

0 references

Cost-Distance: Two Metric Network Design

0 references

Spanning Trees—Short or Small

0 references

Combinatorial optimization. Polyhedra and efficiency (3 volumes)

0 references

Nowhere-zero 6-flows

0 references

Identifiers

zbMATH Open document ID

1341.90113

0 references

DOI

10.1007/s10878-014-9774-5

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5963643

@@ Property / cites work @@
+Approximating the Single-Sink Link-Installation Problem in Network Design
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for access network design
+Normal rank
@@ Property / cites work @@
+Buy-at-Bulk Network Design with Protection
@@ Property / cites work: Buy-at-Bulk Network Design with Protection / rank @@
+Normal rank
@@ Property / cites work @@
+A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
+Normal rank
@@ Property / cites work @@
+New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
+Normal rank
@@ Property / cites work @@
+Q4542533
@@ Property / cites work: Q4542533 / rank @@
+Normal rank
@@ Property / cites work @@
+Generalized submodular cover problems and applications
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems
+Normal rank
@@ Property / cites work @@
+Detecting high log-densities
@@ Property / cites work: Detecting high log-densities / rank @@
+Normal rank
@@ Property / cites work @@
+A constant-factor approximation algorithm for the \(k\)-MST problem
+Normal rank
@@ Property / cites work @@
+Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
+Normal rank
@@ Property / cites work @@
+Q2768299
@@ Property / cites work: Q2768299 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2934722
@@ Property / cites work: Q2934722 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design
+Normal rank
@@ Property / cites work @@
+Q2921762
@@ Property / cites work: Q2921762 / rank @@
+Normal rank
@@ Property / cites work @@
+Min-max tree covers of graphs.
@@ Property / cites work: Min-max tree covers of graphs. / rank @@
+Normal rank
@@ Property / cites work @@
+A tight bound on approximating arbitrary metrics by tree metrics
+Normal rank
@@ Property / cites work @@
+Saving an epsilon
@@ Property / cites work: Saving an epsilon / rank @@
+Normal rank
@@ Property / cites work @@
+A Constant Factor Approximation for the Single Sink Edge Installation Problem
+Normal rank
@@ Property / cites work @@
+Q5417728
@@ Property / cites work: Q5417728 / rank @@
+Normal rank
@@ Property / cites work @@
+Simpler and better approximation algorithms for network design
+Normal rank
@@ Property / cites work @@
+Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
+Normal rank
@@ Property / cites work @@
+Approximation Schemes for the Restricted Shortest Path Problem
+Normal rank
@@ Property / cites work @@
+Q4411286
@@ Property / cites work: Q4411286 / rank @@
+Normal rank
@@ Property / cites work @@
+A factor 2 approximation algorithm for the generalized Steiner network problem
+Normal rank
@@ Property / cites work @@
+Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems
+Normal rank
@@ Property / cites work @@
+Approximating Some Network Design Problems with Node Costs
+Normal rank
@@ Property / cites work @@
+Survivable Network Design with Degree or Order Constraints
+Normal rank
@@ Property / cites work @@
+Bicriteria Network Design Problems
@@ Property / cites work: Bicriteria Network Design Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Cost-Distance: Two Metric Network Design
@@ Property / cites work: Cost-Distance: Two Metric Network Design / rank @@
+Normal rank
@@ Property / cites work @@
+Spanning Trees—Short or Small
@@ Property / cites work: Spanning Trees—Short or Small / rank @@
+Normal rank
@@ Property / cites work @@
+Combinatorial optimization. Polyhedra and efficiency (3 volumes)
+Normal rank
@@ Property / cites work @@
+Nowhere-zero 6-flows
@@ Property / cites work: Nowhere-zero 6-flows / rank @@
+Normal rank