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 metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.univ-antilles.fr/hal-02350145
Contributor : Jean-François Culus <>
Submitted on : Tuesday, November 5, 2019 - 11:20:35 PM
Last modification on : Tuesday, March 24, 2020 - 1:11:48 AM
Document(s) archivé(s) le : Friday, February 7, 2020 - 11:59:37 AM

File

IWOCA_2018_paper_73.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02350145, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

63

Files downloads

127