✦ LIBER ✦

The expected relative error of the polyhedral approximation of the max-cut problem

✍ Scribed by Svatopluk Poljak; Zsolt Tuza

Book ID: 107918301
Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 376 KB
Volume: 16
Category: Article
ISSN: 0167-6377
DOI: 10.1016/0167-6377(94)90068-x

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Combinatorial Properties and the Complex

Combinatorial Properties and the Complexity of a Max-cut Approximation

✍ Charles Delorme; Svatopluk Poljak 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 667 KB

We study various properties of an eigenvalue upper bound on the max-cut problem. We show that the bound behaves in a manner similar to the max-cut for the operations of switching, vertex splitting, contraction and decomposition. It can also be adjusted for branch and bound techniques. We introduce a

Node and edge relaxations of the Max-cut

Node and edge relaxations of the Max-cut problem

✍ S. Poljak; F. Rendl 📂 Article 📅 1994 🏛 Springer Vienna 🌐 English ⚖ 801 KB

A Tight Semidefinite Relaxation of the M

A Tight Semidefinite Relaxation of the MAX CUT Problem

✍ Hongwei Liu; Sanyang Liu; Fengmin Xu 📂 Article 📅 2003 🏛 Springer US 🌐 English ⚖ 66 KB

A note on the approximation of the max c

A note on the approximation of the max clique problem

✍ P. Crescenzi; C. Fiorini; R. Silvestri 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 312 KB

The Relative Complexity of Approximate C

The Relative Complexity of Approximate Counting Problems

✍ Martin Dyer; Leslie Ann Goldberg; Catherine Greenhill; Mark Jerrum 📂 Article 📅 2003 🏛 Springer 🌐 English ⚖ 295 KB

Combinatorial and geometric properties o

Combinatorial and geometric properties of the Max-Cut and Min-Cut problems

✍ Bondarenko, V. A.; Nikolaev, A. V. 📂 Article 📅 2013 🏛 SP MAIK Nauka/Interperiodica 🌐 English ⚖ 146 KB