Change search
ReferencesLink to record
Permanent link

Direct link
On the configuration LP for maximum budgeted allocation
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Numerical Analysis, NA.ORCID iD: 0000-0002-3204-146X
Show others and affiliations
2015 (English)In: Mathematical programming, ISSN 0025-5610, E-ISSN 1436-4646, Vol. 154, no 1-2, 427-462 p.Article in journal (Refereed) PublishedText
Abstract [en]

We study the maximum budgeted allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integrality gap of (Formula presented.), which matches the best known approximation algorithms, our main focus is to improve our understanding of the stronger configuration LP relaxation. In this direction, we prove that the integrality gap of the configuration LP is strictly better than (Formula presented.), and provide corresponding polynomial time roundings, in the following restrictions of the problem: (i) the restricted budgeted allocation problem, in which all the players have the same budget and every item has the same value for any player it can be sold to, and (ii) the graph MBA problem, in which an item can be assigned to at most 2 players. Finally, we improve the best known upper bound on the integrality gap for the general case from (Formula presented.) and also prove hardness of approximation results for both cases.

Place, publisher, year, edition, pages
Springer, 2015. Vol. 154, no 1-2, 427-462 p.
Keyword [en]
68W25
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-181857DOI: 10.1007/s10107-015-0928-8ISI: 000364528000018ScopusID: 2-s2.0-84946401554OAI: oai:DiVA.org:kth-181857DiVA: diva2:901542
Note

QC 20160208

Available from: 2016-02-08 Created: 2016-02-05 Last updated: 2016-02-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Poláček, Lukas
By organisation
Numerical Analysis, NA
In the same journal
Mathematical programming
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link