Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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) = (EX [v(I, X)] − wor(I))/(opt(I) − wor(I)) where opt(I), wor(I) and EX [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, Ω(1/n k−1− log p κ (k−1)) where p κ is the smallest prime power such that p κ ≥ q otherwise, and Ω(1/q k) in (max{q, k} + 1})-partite instances.
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Jean-François CULUS Connect in order to contact the contributor
Submitted on : Tuesday, November 5, 2019 - 11:20:35 PM
Last modification on : Friday, January 21, 2022 - 3:29:09 AM
Long-term archiving on: : Friday, February 7, 2020 - 11:59:37 AM


Files produced by the author(s)


  • HAL Id : hal-02350145, version 1


Jean-François Culus, Sophie Toulouse. How Far From a Worst Solution a Random Solution of a k CSP Instance Can Be?. International Workshop on Combinatorial Algorithms, Jul 2018, Singapore, Singapore. ⟨hal-02350145⟩



Record views


Files downloads