SOS Lower Bounds with Hard Constraints: Think Global, Act Local.
Pravesh K. KothariRyan O'DonnellTselil SchrammPublished in: ITCS (2019)
Keyphrases
- hard constraints
- lower bound
- soft constraints
- upper bound
- cost function
- constraint satisfaction
- objective function
- graph cuts
- multi objective evolutionary
- constraint satisfaction problems
- constraint violations
- branch and bound
- np hard
- search space
- worst case
- branch and bound algorithm
- efficient computation
- data distribution
- multi criteria
- neural network