How Far From a Worst Solution a Random Solution of a k CSP Instance Can Be?

摘要

Given an instance I of an optimization constraint satisfaction problem (CSP), finding solutions with value at least the expected value of a random solution is easy. We wonder how good such solutions can be. Namely, we initiate the study of ratio ρE(I) = (E_X[v(I,X)] - wor(I))/(opt(I) - wor(I)) where opt(I), wor(I) and E_X [v(I, X)} refer to respectively the optimal, the worst, and the average solution values on I. We here focus on the case when the variables have a domain of size q ≥ 2 and the constraint arity is at most k ≥ 2, where k,q are two constant integers. Connecting this ratio to the highest frequency in orthogonal arrays with specified parameters, we prove that it is Ω(1/n~(k/2)) if q = 2, n(1/n~(k-1-「log_pk(k-1))」 where p~k is the smallest prime power such that p~k ≥ q otherwise, and Ω(1/q~k ) in (max{q, k} + 1})-partite instances.