Approximation Algorithms for the Bid Construction Problem in Combinatorial Auctions for the Procurement of Freight Transportation Contracts
- Author(s): Song, Jiongjiong
- Regan, A C
- et al.
The bid valuation and construction problem for carriers facing combinatorial auctions for the procurement of freight transportation contracts is very difficult and involves the computation of a number of NP-hard sub problems. In this paper we examine computationally tractable approximation methods for estimating these values and constructing bids. The benefit of our approximation method is that it provides a way for carriers to construct optimal or near optimal bids by solving a single NP-hard problem. This represents a significant improvement in efficiency. In addition, this method can be extended to many other applications.