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
نام شخص به منزله سر شناسه - (مسئولیت معنوی درجه اول )