Title: Real complex semidefinite programming and its application to circular arrangements
Speaker: Alantha Newman, DIMACS
Date: Wednesday, December 10, 2008 11:00-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We consider the problem of arranging elements on a circle so as to preserve specified pairwise distances. Given a set of equations of the form x_v - x_u = c (mod p), we address the objective of maximizing a linear payoff function depending on how close x_v-x_u actually is to c, rather than the standard payoff function of '1' or '0', if equation is true or false, respectively.
We show that this problem can be approximated to within .854 using semidefinite programming. Since the problem can be viewed as a strict generalization of the Max-Cut problem, this is a near optimal approximation ratio assuming the Unique-Games Conjecture. Our main contribution is that we show how the framework of complex semidefinite programming can be applied to round a ``standard'' semidefinite programming relaxation for our problem, even though we do not know how to model our problem with the complex roots of unity, as is standard in most applications of complex semidefinite programming.
(Joint work with Konstantin Makarychev.)