A3, AOC, CALIN, LCR, MERCRED, RCLN

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Deriving differential approximation results for k-CSPs from combinatorial designs
Description:	Sophie Toulouse Given two integers q, k ? 2, k-CSP?q is the unconstrained optimization problem in which variables have domain Z_q and the goal is to optimize a weighted sum of constraints, each acting on at most k of the variables. Standard inapproximability results for Max-k-CSP?q often involve balanced k-wise independent distributions over Z_q or rather equivalently, orthogonal arrays of strength k over Z_q. We here illustrate how combinatorial designs are a relevant tool in order to establish approximation results for k-CSP?q with respect to the differential approximation measure, which compares the distance between the approximate value and the worst solution value to the instance diameter. First, connecting the average differential ratio to orthogonal arrays, we deduce that this ratio is ?(1/n^(k/2)) when q = 2, ?(1/n^(k-1)) when q is a prime power and 1/q^k on (k+1)-partite instances. We also consider pairs of arrays that can be viewed as some constrained decomposition of balanced k-wise independent functions. We exhibit such pairs that allow when q > k to reduce k-CSP?q to k-CSP?k with an expansion 1/(q?k/2)^k on the approximation guarantee. This implies together with the result of [Yuri Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software, 9 (1998), pp. 141160] a lower approximability bound of 0.429/(q ? 1)^2 for 2-CSP?q. Similar designs also allow to establish that every Hamming ball with radius k provides a ?(1/n^k)-approximation of the instance diameter.

Mardi 18 Avril