Local search approximation algorithms for the k-means problem with penalties.
Dongmei ZhangChunlin HaoChenchen WuDachuan XuZhenning ZhangPublished in: J. Comb. Optim. (2019)
Keyphrases
- approximation algorithms
- k means
- np hard
- special case
- clustering algorithm
- vertex cover
- facility location problem
- worst case
- minimum cost
- search algorithm
- optimal solution
- tabu search
- set cover
- search space
- memetic algorithm
- randomized algorithms
- primal dual
- genetic algorithm
- exact algorithms
- network design problem
- undirected graph
- combinatorial optimization
- precedence constraints
- approximation ratio
- constant factor
- approximation schemes
- np hardness
- simulated annealing
- polynomial time approximation
- open shop
- disjoint paths
- combinatorial auctions
- expectation maximization
- search procedure
- evolutionary algorithm
- dynamic programming