Abstract
We consider the top-k procurement decision problem in a multi-item auction, where there exists only one prospective buyer and the input consists of (i) a set of items, where each item is partitioned into equal number of shares, (ii) a set of suppliers, and (iii) for each supplier, her bids of selling different shares of each item; our target is to find k procurements with the least total costs. Kelly and Byde [SIGEcom 2006] studied the case where for each item, we may buy from each supplier at most once; this setting is suitable in most of the cases where total cost of a procurement is the primary concern. In this paper, we assume a slightly different version where for any item, we may buy from a supplier multiple times (but each time with a different number of shares). We propose an anytime algorithm which can report successive best procurements until a buyer is satisfied (or terminates the algorithm). Our solution is based on preprocessing a metadata structure (without knowing the actual bids) to speed up the reporting steps. The metadata structure consists of (i) a DAG M local for the valid combination of shares for each item, and (ii) a DAG M global that coordinates the information from all M local . We further show that the metadata structure can be generated on the fly, thereby saving a considerable amount of storage space.