عنوان

Efficient approximation algorithms for some semidefinite programs

شماره

TLpq304341369

زبان متن نوشتاري يا گفتاري و مانند آن

انگلیسی

عنوان اصلي

Efficient approximation algorithms for some semidefinite programs

نام عام مواد

[Thesis]

نام نخستين پديدآور

H.-I. Lu

نام ساير پديدآوران

P. N. Klein

نام ناشر، پخش کننده و غيره

Brown University

تاریخ نشرو بخش و غیره

1997

نام خاص و کميت اثر

134

جزئيات پايان نامه و نوع درجه آن

Ph.D.

کسي که مدرک را اعطا کرده

Brown University

امتياز متن

1997

متن يادداشت

Linear Programming has been fruitful in designing approximation algorithms for many combinatorial optimization problems. Nonlinear programming did not receive as much attention in this respect until the recent work by Geomans and Williamson. They use semidefinite programs to obtain approximation solutions with much better approximation factors. For example, the best preciously known approximation algorithm for MAXCUT, which was invented twenty years ago, has approximation factor 0.5. The algorithm of Geomans and Williamson dramatically improves the approximation factor to 0.878. Inspired by the work on MAXCUT, Karger, Motwani, and Sudan adapt the same technique and obtain the currently best approximation algorithm for coloring a k-colorable graph with the fewest possible number of colors. The approximation ratio is improved by a factor of usd\Omega(n\sp{2/k}usd) over the best previously known result. Besides MAXCUT and COLORING, the technique of semidefinite programming has been successful in designing approximation algorithms for many other optimization problems. Each of these improved algorithms is based on obtaining a new-optimal solution to a semidefinite program, which is referred as the semidefinite relaxation of the underlining optimization problem. Therefore how to approximately solve these semidefinite relaxations efficiently, in both time and space, is practically important. All the previous work resorts to interior-point methods for this step. In the thesis the framework of Plotkin, Shmoys, and Tardos is adapted to obtain near-optimal solutions to the semidefinite relaxations of MAXCUT and COLORING. The results significantly reduce the work space required by the best known approximation algorithms for MAXCUT and COLORING if the given graph is sparse. As a consequence, the results in the thesis enable the best known approximation algorithms for MAXCUT and COLORING to work on much larger sparse graphs than they did with interior-point methods.

موضوع مستند نشده

Applied sciences

موضوع مستند نشده

COLORING

موضوع مستند نشده

Computer science

موضوع مستند نشده

Lagrangean relaxation

موضوع مستند نشده

MAXCUT

مستند نام اشخاص تاييد نشده

H.-I. Lu

مستند نام اشخاص تاييد نشده

P. N. Klein

نام الکترونيکي

فرمت انتشار

p

نوع ماده

[Thesis]

کد کاربرگه

276903

سطح دسترسي

a

تكميل شده

Y