1 ) A method, comprising: receiving bids in a combinatorial auction for a sale of identical units of a good, having m bidders and n bids; computing a fully polynomial-time approximation scheme (FPTAS) for an interval knapsack problem (I-KP) in time O(n log n+n/ε 2 ) to calculate winning bids; displaying the winning bids.