How Far From a Worst Solution a Random Solution of a k CSP Instance Can Be? - Université des Antilles Access content directly
Conference Papers Year : 2018

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.
Fichier principal
Vignette du fichier
IWOCA_2018_paper_73.pdf (375.81 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02350145 , version 1 (05-11-2019)

Identifiers

  • HAL Id : hal-02350145 , version 1

Cite

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⟩
102 View
144 Download

Share

Gmail Facebook X LinkedIn More