Improved approximation algorithms for broadcast scheduling
Nikhil Bansal, Don Coppersmith, et al.
SODA 2006
The complex quadratic form z′ Pz, where z is a fixed vector in Cn and z′ is its transpose, and P is any permutation matrix, is shown to be a convex combination of the quadratic forms z′ Pσz, where Pσ denotes the symmetric permutation matrices. We deduce that the optimal probability density associated to the chiral index of a sample from a bivariate distribution is symmetric. This result is used to locate the upper bound of the chiral index of any bivariate distribution in the interval [1 - 1/π, 1 - 1/2π]. © 2005 Académie de sciences. Published by Elsevier SAS. All rights reserved.
Nikhil Bansal, Don Coppersmith, et al.
SODA 2006
Roy L. Adler, Don Coppersmith, et al.
IEEE Trans. Inf. Theory
Nikhil Bansal, Danny Z. Chen, et al.
Algorithmica (New York)
Don Coppersmith, Uriel Feige, et al.
SIAM Journal on Discrete Mathematics