Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization.
Fabián A. ChudakKiyohito NaganoPublished in: SODA (2007)
Keyphrases
- convex optimization
- combinatorial problems
- efficient solutions
- submodular functions
- convex relaxation
- constraint programming
- metaheuristic
- combinatorial optimization
- optimal solution
- traveling salesman problem
- branch and bound algorithm
- constraint satisfaction problems
- interior point methods
- constraint satisfaction
- lower bound
- low rank
- phase transition
- total variation
- primal dual
- branch and bound
- heuristic methods
- quadratically constrained quadratic
- semidefinite
- np hard
- convex sets
- objective function
- convex optimization problems
- norm minimization
- global constraints
- greedy algorithm
- constraint propagation
- denoising
- semidefinite program
- tabu search
- cost function
- column generation
- multi objective