Efficient approximation algorithms for some semidefinite programs

مرکز و کتابخانه مطالعات اسلامی به زبان های اروپایی

منو

" Efficient approximation algorithms for some semidefinite programs "
H.-I. Lu P. N. Klein

Document Type	:	Latin Dissertation
Language of Document	:	English
Record Number	:	1113220
Doc. No	:	TLpq304341369
Main Entry	:	H.-I. Lu
	:	P. N. Klein
Title & Author	:	Efficient approximation algorithms for some semidefinite programs\ H.-I. LuP. N. Klein
College	:	Brown University
Date	:	1997
student score	:	1997
Degree	:	Ph.D.
Page No	:	134
Abstract	:	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.
Subject	:	Applied sciences
	:	COLORING
	:	Computer science
	:	Lagrangean relaxation
	:	MAXCUT