✦ LIBER ✦

On the integrality ratio for tree augmentation

✍ Scribed by J. Cheriyan; H. Karloff; R. Khandekar; J. Könemann

Publisher: Elsevier Science
Year: 2008
Tongue: English
Weight: 229 KB
Volume: 36
Category: Article
ISSN: 0167-6377
DOI: 10.1016/j.orl.2008.01.009

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the standard linear programming relaxation for the tree augmentation problem in undirected graphs has an integrality ratio that approaches 3 2 . This refutes a conjecture of Cheriyan, Jordán, and Ravi [J. Cheriyan, T. Jordán, R. Ravi, On 2-coverings and 2packings of laminar families, in: Proceedings, European Symposium on Algorithms, 1999, pp. 510-520. A longer version is on the web: http://www.math.uwaterloo.ca/jcheriyan/publications.html] that the integrality ratio is 4 3 .

📜 SIMILAR VOLUMES

Variance to Mean Ratio, R(t), for Poisso

Variance to Mean Ratio, R(t), for Poisson Processes on Phylogenetic Trees

✍ Nick Goldman 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 734 KB

I thank Eddie Holmes for many helpful discussions of \(R(t)\), and Richard Holmquist and three anonymous referees for comments which led to improvements of this paper.

On the ratio of optimal integral and fra

On the ratio of optimal integral and fractional covers

✍ L. Lovász 📂 Article 📅 1975 🏛 Elsevier Science 🌐 English ⚖ 925 KB

A New Approximation Algorithm for the St

A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3

✍ Hans Jürgen Prömel; Angelika Steger 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 100 KB

In this paper we present an RNC approximation algorithm for the Steiner tree problem in graphs with performance ratio 5r3 and RNC approximation algorithms for the Steiner tree problem in networks with performance ratio 5r3 q ⑀ for all ⑀ ) 0. This is achieved by considering a related problem, the min

The j-integral for augmented double cant

The j-integral for augmented double cantilever beams and its application to bonded joints

✍ Shoji E. Yamada 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 726 KB

The J-integral for the double cantilever type specimen is obtained explicitly based on the assumption of a beam on the elastic/plastic foundation. The solution agrees with known solutions as special cases. Also discussed is the path independence of the J-integral for the bonded double cantilever joi

A Criterion for Determining the Monotoni

A Criterion for Determining the Monotonicity of the Ratio of Two Abelian Integrals

✍ Chengzhi Li; Zhi-fen Zhang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 349 KB

A new method to determine the monotonicity of the ratio of two Abelian integrals is given. We find two criterion functions defined directly by the functions which appear in the Abelian integrals. The monotonicities of the criterion functions imply the monotonicity of the ratio of the Abelian integra

On the approximate augmented Lagrangian

On the approximate augmented Lagrangian for nonlinear symmetric cone programming

✍ Yong-Jin Liu; Li-Wei Zhang 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 298 KB

This paper studies the approximate augmented Lagrangian for nonlinear symmetric cone programming. The analysis is based on some results under the framework of Euclidean Jordan algebras. We formulate the approximate Lagrangian dual problem and study conditions for approximate strong duality results a