Paper Info
Title
Algorithms Based on Randomization and Linear and Semidefinite Programming
Abstract
We study three methods based on linear programming and generalizations that are often applied to approximate combinatorial optimization problems. We start by describing an approximate method based on linear programming; as an example we consider scheduling of jobs on unrelated machines with costs. The second method presented is based on semidefinite programming; we show how to obtain a reasonable solution for the maximum cut problem. Finally, we analyze the conditional probabilities method in connection with randomized rounding for routing, packing and covering integer linear programming problems.
Year
Venue
Keywords
1998
SOFSEM
unrelated machine,approximate method,maximum cut problem,linear programming,randomized rounding,integer linear programming problem,reasonable solution,approximate combinatorial optimization problem,conditional probabilities method,semidefinite programming,conditional probability,linear program
Field
DocType
Volume
Second-order cone programming,Linear-fractional programming,Combinatorics,Mathematical optimization,Computer science,Branch and price,Algorithm,Integer programming,Randomized rounding,Linear programming,Criss-cross algorithm,Semidefinite programming
Conference
1521
ISSN
ISBN
Citations 
0302-9743
3-540-65260-4
0
PageRank 
References 
Authors
0.34
24
2
Name
Order
Citations
PageRank
Klaus Jansen178982.68
José D. P. Rolim21331181.36