Greed is slow on sparse graphs of oriented valued constraints
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915341559398400 |
|---|---|
| author | Kaznatcheev, Artem Alferez, Sofia Vazquez |
| author_facet | Kaznatcheev, Artem Alferez, Sofia Vazquez |
| contents | Greedy local search is especially popular for solving valued constraint satisfaction problems (VCSPs). Since any method will be slow for some VCSPs, we ask: what is the simplest VCSP on which greedy local search is slow? We construct a VCSP on 6n Boolean variables for which greedy local search takes 7(2^n - 1) steps to find the unique peak. Our VCSP is simple in two ways. First, it is very sparse: its constraint graph has pathwidth 2 and maximum degree 3. This is the simplest VCSP on which some local search could be slow. Second, it is "oriented" - there is an ordering on the variables such that later variables are conditionally-independent of earlier ones. Being oriented allows many non-greedy local search methods to find the unique peak in a quadratic number of steps. Thus, we conclude that - among local search methods - greed is particularly slow. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_11662 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Greed is slow on sparse graphs of oriented valued constraints Kaznatcheev, Artem Alferez, Sofia Vazquez Discrete Mathematics Greedy local search is especially popular for solving valued constraint satisfaction problems (VCSPs). Since any method will be slow for some VCSPs, we ask: what is the simplest VCSP on which greedy local search is slow? We construct a VCSP on 6n Boolean variables for which greedy local search takes 7(2^n - 1) steps to find the unique peak. Our VCSP is simple in two ways. First, it is very sparse: its constraint graph has pathwidth 2 and maximum degree 3. This is the simplest VCSP on which some local search could be slow. Second, it is "oriented" - there is an ordering on the variables such that later variables are conditionally-independent of earlier ones. Being oriented allows many non-greedy local search methods to find the unique peak in a quadratic number of steps. Thus, we conclude that - among local search methods - greed is particularly slow. |
| title | Greed is slow on sparse graphs of oriented valued constraints |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2506.11662 |