Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
LP-relaxations for tree augmentation - MaRDI portal

LP-relaxations for tree augmentation (Q1706120)

From MaRDI portal

Jump to:navigation, search

This is the item page for this Wikibase entity, intended for internal use and editing purposes.

Please use this page instead for the normal view: LP-relaxations for tree augmentation

scientific article; zbMATH DE number 6851661

Language	Label	Description	Also known as
English	LP-relaxations for tree augmentation	scientific article; zbMATH DE number 6851661

Statements

scholarly article

0 references

LP-relaxations for tree augmentation (English)

0 references

0 references

0 references

Discrete Applied Mathematics

0 references

publication date

21 March 2018

0 references

full work available at URL

https://drops.dagstuhl.de/opus/volltexte/2016/6636/

0 references

zbMATH Keywords

tree augmentation

0 references

LP-relaxation

0 references

Laminar family

0 references

approximation algorithm

0 references

MaRDI profile type

0 references

Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs

0 references

Approximating (unweighted) tree augmentation via lift-and-project. II

0 references

0 references

On the integrality ratio for tree augmentation

0 references

A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius

0 references

0 references

A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

0 references

0 references

Approximation Algorithms for Several Graph Augmentation Problems

0 references

On the relationship between the biconnectivity augmentation and traveling salesman problems

0 references

A factor 2 approximation algorithm for the generalized Steiner network problem

0 references

0 references

Approximation Algorithms for Graph Augmentation

0 references

A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2

0 references

Iterative Methods in Combinatorial Optimization

0 references

Covering a laminar family by leaf to leaf links

0 references

An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree

0 references

0 references

Combinatorial Optimization. Polyhedra and efficiency. CD-ROM

0 references

Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs

0 references

A primal-dual approximation algorithm for generalized Steiner network problems

0 references

Recommended article

LP-Relaxations for Tree Augmentation.

Similarity Score

0.9999998

Recommender Run

Recommender Run 3

0 references

On the tree augmentation problem

Similarity Score

0.8791313

Recommender Run

Recommender Run 3

0 references

Similarity Score

0.8791313

Recommender Run

Recommender Run 3

0 references

Improved approximation for tree augmentation: saving by rewiring

Similarity Score

0.8700768

Recommender Run

Recommender Run 3

0 references

On the integrality ratio for tree augmentation

Similarity Score

0.8656528

Recommender Run

Recommender Run 3

0 references

On small-depth tree augmentations

Similarity Score

0.8518634

Recommender Run

Recommender Run 3

0 references

LP Relaxation and Tree Packing for Minimum $k$-Cut

Similarity Score

0.8466547

Recommender Run

Recommender Run 3

0 references

Approximating (unweighted) tree augmentation via lift-and-project. II

Similarity Score

0.84563076

Recommender Run

Recommender Run 3

0 references

Algorithms for radius-optimally augmenting trees in a metric space

Similarity Score

0.8442423

Recommender Run

Recommender Run 3

0 references

Algorithms for radius-optimally augmenting trees in a metric space

Similarity Score

0.84424216

Recommender Run

Recommender Run 3

0 references

Identifiers

zbMATH Open document ID

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

10.1016/J.DAM.2017.12.033

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1706120

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q1706120&oldid=43287023"