๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Improving the complexities of approximation algorithms for optimization problems

โœ Scribed by Mikhail Y. Kovalyov

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
177 KB
Volume
17
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Improved Approximation Algorithms for Un
Improved Approximation Algorithms for Uniform Connectivity Problems
โœ Samir Khuller; Balaji Raghavachari ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 174 KB

The problem of finding minimum-weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial time approximation algorithms for various weighted and unweighted connectivity problems are given. Th

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