Approximation Algorithms for the Maximum-Weight Cycle/Path Packing Problems.
Shiming LiWei YuPublished in: Asia Pac. J. Oper. Res. (2023)
Keyphrases
- approximation algorithms
- maximum weight
- packing problem
- np hard
- integer programming
- minimum cost
- bin packing
- special case
- worst case
- disjoint paths
- minimum weight
- bipartite graph
- vertex cover
- scheduling problem
- partial order
- shortest path
- np complete
- weighted graph
- linear programming
- branch and bound algorithm
- lower bound
- optimal solution
- linear program
- computational complexity
- constant factor
- primal dual
- knapsack problem
- cutting plane
- constraint programming
- high dimensional
- constant factor approximation