Approximation Algorithms for Capacitated Assignment with Budget Constraints and Applications in Transportation Systems.
Hongyi JiangSamitha SamaranayakePublished in: COCOON (2022)
Keyphrases
- approximation algorithms
- transportation systems
- budget constraints
- network design problem
- np hard
- facility location problem
- special case
- worst case
- vertex cover
- minimum cost
- bidding strategies
- vehicle routing problem
- combinatorial auctions
- multi item
- approximation ratio
- integer programming
- randomized algorithms
- lower bound
- disjoint paths
- optimal solution
- facility location
- decision problems
- lagrangian relaxation
- primal dual
- constant factor
- terrorist networks
- display advertising
- lot sizing
- linear programming
- scheduling problem
- information retrieval