Greed is slow on sparse graphs of oriented valued constraints

Artem Kaznatcheev, Sofia Vazquez Alferez

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 VC…