東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Enhancing techniques in LP based app...

Jain, Kamal.

Linked to FindBook

Google Book

Amazon

博客來

Enhancing techniques in LP based approximation algorithms.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Enhancing techniques in LP based approximation algorithms./
Author:	Jain, Kamal.
Description:	106 p.
Notes:	Source: Dissertation Abstracts International, Volume: 61-07, Section: B, page: 3688.
Contained By:	Dissertation Abstracts International61-07B.
Subject:	Computer science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=9978394
ISBN:	9780599842687

Enhancing techniques in LP based approximation algorithms.
Jain, Kamal.

Enhancing techniques in LP based approximation algorithms. - 106 p.

Source: Dissertation Abstracts International, Volume: 61-07, Section: B, page: 3688.

Thesis (Ph.D.)--Georgia Institute of Technology, 2000.

Over the last decade many new approximation algorithms have been developed for NP-hard optimization problems. A large fraction of these are based on linear programming theory. These algorithms use two basic techniques, rounding and primal dual schema, both of these were enhanced to give new approximation algorithms. The thesis consists of three parts, the first two discussing enhancements of both these techniques, and the third, adapting the technique of Lagrangian relaxation in the context of approximation algorithms.

ISBN: 9780599842687Subjects--Topical Terms:

523869
Computer science.

Enhancing techniques in LP based approximation algorithms.
LDR:03004nmm a2200325 4500 001 2076132
005 20161101084249.5
008 170521s2000 ||||||||||||||||| ||eng d
020 $a 9780599842687
035 $a (MiAaPQ)AAI9978394
035 $a AAI9978394
040 $a MiAaPQ $c MiAaPQ
100 1 $a Jain, Kamal. $3 3191564
245 1 0 $a Enhancing techniques in LP based approximation algorithms.
300 $a 106 p.
500 $a Source: Dissertation Abstracts International, Volume: 61-07, Section: B, page: 3688.
500 $a Director: Vijay V. Vazirani.
502 $a Thesis (Ph.D.)--Georgia Institute of Technology, 2000.
520 $a Over the last decade many new approximation algorithms have been developed for NP-hard optimization problems. A large fraction of these are based on linear programming theory. These algorithms use two basic techniques, rounding and primal dual schema, both of these were enhanced to give new approximation algorithms. The thesis consists of three parts, the first two discussing enhancements of both these techniques, and the third, adapting the technique of Lagrangian relaxation in the context of approximation algorithms.
520 $a The technique of iterative rounding was introduced to obtain a factor 2 approximation algorithm for the Generalized Steiner Network problem, thereby settling a long standing open problem. This problem seeks to build the cheapest cost network connecting every pair of nodes by a specified number of edge disjoint paths. This problem arises in the design of survivable networks.
520 $a In the context of approximation algorithms, the primal dual schema had been applied only when there were no negative coefficients in either the primal or the dual programs. The schema was used for the first time to obtain an approximation algorithm for the metric facility location problem, thereby extending the schema to linear programs with negative coefficients as well. This was also the first practical approximation algorithm for this four decade old problem. This problem seeks the cheapest way of locating facilities (e.g., warehouses or proxy webservers) to serve a given set of clients.
520 $a One limitation of the primal dual schema is that it works locally. So it fails when there is a global constraint, such as a budget constraint. For instance, in the facility location problem, we may be required to open at most k facilities, a special case of which is the k median problem. The classical technique of Lagrangian relaxation from combinatorial optimization was adapted to deal with such situations. This technique was used to obtain a factor 6 approximation algorithm for the k median problem. This has applications in data mining and web searching.
590 $a School code: 0078.
650 4 $a Computer science. $3 523869
650 4 $a Mathematics. $3 515831
650 4 $a Operations research. $3 547123
690 $a 0984
690 $a 0405
690 $a 0796
710 2 $a Georgia Institute of Technology. $3 696730
773 0 $t Dissertation Abstracts International $g 61-07B.
790 $a 0078
791 $a Ph.D.
792 $a 2000
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=9978394