Statistical Physics and Interdisciplinary Applications

Online optimization problems are characterized by incomplete information. In ordinary (i.e. offline) problems, one is given an instance and is asked to find an 'optimal solution', i.e. an assignment of the variables of the problem that minimizes some cost function. In online problems, the instance of the problem is not fully known in advance, but is instead 'revealed' progressively: as time evolves, new information about the instance is acquired, and some of the variables have to be assigned based on this partial information.

Recently there has been a surge of interest in auctions research triggered on the one hand by auctions of bandwidth and other public assets and on the other by the popularity of Internet auctions and the possibility of new auction formats enabled by e-commerce. Simultaneous auction of items is a popular auction format. We consider the problem of maximizing total revenue in the simultaneous auction of a set of items where the bidders have individual budget constraints. Each bidder is permitted to bid on all the items of his choice and specifies his budget constraint to the auctioneer, who must select bids to maximize the revenue while ensuring that no budget constraints are violated. We show that the problem of maximizing revenue is such a setting is NP-hard, and present a factor-1.62 approximation algorithm for it. We formulate the problem as an integer program and solve a linear relaxation to obtain a fractional optimal solution, which is then deterministically rounded to obtain an integer solution. We argue that the loss in revenue incurred by the rounding procedure is bounded by a factor of 1.62.

References:
[1] R. Garg, V. Kumar and V. Pandit.

Mézard M, Mora T, Zecchina R. Clustering of Solutions in the Random Satisfiability Problem. Physical Review Letters. 2005;94:197205.

Ramezanpour A. {Ising model on the edge-dual of random networks}. Physical Review E. 2004;69:66114.

Mora T, Mézard M, Zecchina R. Pairs of SAT Assignments and Clustering in Random Boolean Formulae. Theoretical Computer Science. 2008;393:260-79.

Ramezanpour A, Karimipour V, Mashaghi A. {Generating correlated networks from uncorrelated ones}. Physical Review E. 2003;67:46107.

Mulet R, Pagnani A, Weigt M, Zecchina R. Coloring Random Graphs. Physical Review Letters. 2002;89:268701.

Karimipour V, Ramezanpour A. {Correlation effects in a simple model of small-world network}. Journal reference: Phys. Rev. E. 2002;65:036122.

Mézard M, Ricci-Tersenghi F, Zecchina R. Two solutions to diluted p-spin models and XORSAT problems. J. Stat. Phys.. 2002;111:505.

Ramezanpour A, Moghimi-Araghi S. Simplifying random satisfiability problems by removing frustrating interactions. Physical Review E. 2006;74:41105.