Embodiments are directed to systems, methods, and apparatus for allocating goods to bidders in combinatorial auctions. In one embodiment, bids are received in a combinatorial auction and the winner determination problem is modeled as an interval knapsack problem (I-KP) or an interval multiple-choice knapsack problem (I-MCKP), efficient algorithms (both pseudo-polynomial-time exact algorithms and FPTAS) for I-KP (and I-MCKP) are used to compute an allocation of goods to winning bidders.