arXiv
Open Access
2015
On the Greedy Algorithm for Combinatorial Auctions with a Random Order
Shahar Dobzinski
Ami Mor
Abstrak
In this note we study the greedy algorithm for combinatorial auctions with submodular bidders. It is well known that this algorithm provides an approximation ratio of $2$ for every order of the items. We show that if the valuations are vertex cover functions and the order is random then the expected approximation ratio imrpoves to $\frac 7 4$.
Penulis (2)
S
Shahar Dobzinski
A
Ami Mor
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2015
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓