Premium
Randomized metarounding
Author(s) -
Carr Robert,
Vempala Santosh
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10033
Subject(s) - extreme point , rounding , randomized rounding , integer (computer science) , mathematics , linear programming relaxation , combinatorics , generalization , polytope , constructive , relaxation (psychology) , heuristic , point (geometry) , function (biology) , randomized algorithm , discrete mathematics , integer programming , mathematical optimization , approximation algorithm , computer science , mathematical analysis , psychology , social psychology , geometry , process (computing) , evolutionary biology , biology , programming language , operating system
Let P be a linear relaxation of an integer polytope Z such that the integrality gap of P with respect to Z is at most r, as verified by a polytime heuristic A, which on any positive cost function c returns an integer solution (an extreme point of Z) whose cost is at most r times the optimal cost over P. Then for any point x* in P (a fractional solution), rx* dominates some convex combination of extreme points of Z. A constructive version of this theorem is presented here, with applications to approximation algorithms, and can be viewed as a generalization of randomized rounding. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:343–352, 2002