Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH.
Venkatesan GuruswamiBingkai LinXuandi RenYican SunKewen WuPublished in: Electron. Colloquium Comput. Complex. (2024)
Keyphrases
- lower bound
- optimal solution
- worst case
- upper bound
- np hard
- constraint satisfaction problems
- branch and bound algorithm
- branch and bound
- competitive ratio
- dynamic programming
- optimal cost
- decomposition methods
- objective function
- integer programming
- constraint propagation
- constant factor
- linear programming
- lower and upper bounds
- lower bounding