Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH.
Venkatesan GuruswamiBingkai LinXuandi RenYican SunKewen WuPublished in: CoRR (2024)
Keyphrases
- lower bound
- optimal solution
- upper bound
- worst case
- optimal cost
- np hard
- objective function
- branch and bound
- branch and bound algorithm
- constraint satisfaction problems
- competitive ratio
- optimal strategy
- expected cost
- lower bounding
- dynamic programming
- closed form
- constraint propagation
- asymptotically optimal
- random instances