𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An improved approximation algorithm for requirement cut

✍ Scribed by Anupam Gupta; Viswanath Nagarajan; R. Ravi

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
506 KB
Volume
38
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

An Improved Approximation Algorithm for
An Improved Approximation Algorithm for MULTIWAY CUT
✍ Gruia CΔƒlinescu; Howard Karloff; Yuval Rabani πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 132 KB

Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the problem of finding a multiway cut of minimum cost. Previously, a very simple combinatorial algorithm due

An improved approximation algorithm for
An improved approximation algorithm for the partial Latin square extension problem
✍ Carla P. Gomes; Rommel G. Regis; David B. Shmoys πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 203 KB

The problem of completing partial latin squares arises in a number of applications, including conflict-free wavelength routing in wide-area optical networks, statistical designs, and error-correcting codes. A partial latin square is an n by n array such that each cell is either empty or contains exa

Improved Approximation Algorithms for MA
Improved Approximation Algorithms for MAX SAT
✍ Takao Asano; David P. Williamson πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 215 KB

MAX SAT (the maximum s~tisfiability problem) is stated as follows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. In this paper, we consider approxima~ tion algorithms for MAX SAT proposed by Goemans and Williamson and pze