Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the configuration LP for maximum budgeted allocation
Show others and affiliations
2014 (English)In: 17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014, 2014, 333-344 p.Conference paper, Published paper (Refereed)
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, 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, 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 5/6 to 2√2 2 ≈ 0.828 and also prove hardness of approximation results for both cases.

Place, publisher, year, edition, pages
2014. 333-344 p.
Keyword [en]
Approximation algorithms, Combinatorial optimization, Integer programming, Polynomial approximation, Allocation problems, Hardness of approximation, Indivisible good, Integrality gaps, LP relaxation, Polynomial-time, Upper Bound, Budget control
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-167893DOI: 10.1007/s10107-015-0928-8Scopus ID: 2-s2.0-84958539576ISBN: 9783319075563 (print)OAI: oai:DiVA.org:kth-167893DiVA: diva2:820865
Conference
23 June 2014 through 25 June 2014, Bonn
Note

QC 20150612

Available from: 2015-06-12 Created: 2015-05-22 Last updated: 2017-06-02Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Poláček, Lukas

Search in DiVA

By author/editor
Poláček, Lukas
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 10 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf