Codes, lower bounds, and phase transitions in the symmetric rendezvous problem.
Varsha DaniThomas P. HayesCristopher MooreAlexander RussellPublished in: Random Struct. Algorithms (2016)
Keyphrases
- phase transition
- lower bound
- rendezvous search
- random instances
- random constraint satisfaction problems
- upper bound
- constraint satisfaction
- np hard
- satisfiability problem
- np complete
- branch and bound
- branch and bound algorithm
- randomly generated
- objective function
- combinatorial problems
- finding optimal
- hard problems
- optimal solution
- sat problem
- vc dimension
- np complete problems
- max sat
- graph coloring
- stochastic local search
- cellular automata
- constraint satisfaction problems
- sample complexity