A method turning a solution of a continuous optimization relaxation into a random feasible solution of a discrete problem. An expected objective bound can give an approximation guarantee. Gaussian hyperplane rounding and Rademacher rounding for a semidefinite relaxation are different examples.
Given a real unit-vector Gram matrix , draw a standard Gaussian random vector and set . Each coordinate is almost surely a sign; zero projections have probability zero. The same random separating hyperplane is used for every coordinate, so the signs need not be independent. Their pair expectations follow the Gaussian sign-correlation identity.
For a bipartite elliptope matrix , put and apply within the two diagonal blocks and across them. Matching absolute power series coefficients give a positive semidefinite matrix by coefficient-dominated entrywise positivity, while gives unit diagonal. Gaussian hyperplane rounding then turns each cross-block correlation coefficient into because . The zero diagonal blocks of the bipartite objective eliminate every other contribution.
For bipartite binary quadratic optimization, if is the sign optimum and its semidefinite relaxation of binary quadratic optimization value, then . The upper bound follows from rank-one lifting. For the lower bound, Krivine rounding scheme preprocessing followed by Gaussian hyperplane rounding has expected objective exactly , and every rounded vector is feasible. Some outcome reaches at least this expectation. No independence of rounded coordinates or positive semidefiniteness of the original bipartite objective is needed.
The Krivine rounding scheme yields as its guaranteed objective factor. It is obtained by normalizing , so and . This proof gives a valid universal factor for the bipartite sign problem, not a proof that it is optimal.
Articles by others on the same topic
Randomized rounding is an algorithmic technique often used in the context of approximation algorithms and integer programming. It is particularly useful for dealing with problems where one needs to convert a fractional solution (obtained from solving a linear relaxation of an integer programming problem) into a feasible integer solution, while maintaining a certain level of optimality. ### Overview: 1. **Linear Relaxation**: In integer programming, the objective is to find integer solutions to certain optimization problems.