kth.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On the configuration LP for maximum budgeted allocation
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Numerisk analys, NA.ORCID-id: 0000-0002-3204-146X
Visa övriga samt affilieringar
2015 (Engelska)Ingår i: Mathematical programming, ISSN 0025-5610, E-ISSN 1436-4646, Vol. 154, nr 1-2, s. 427-462Artikel i tidskrift (Refereegranskat) Published
Resurstyp
Text
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.

Ort, förlag, år, upplaga, sidor
Springer, 2015. Vol. 154, nr 1-2, s. 427-462
Nyckelord [en]
68W25
Nationell ämneskategori
Beräkningsmatematik
Identifikatorer
URN: urn:nbn:se:kth:diva-181857DOI: 10.1007/s10107-015-0928-8ISI: 000364528000018Scopus ID: 2-s2.0-84946401554OAI: oai:DiVA.org:kth-181857DiVA, id: diva2:901542
Anmärkning

QC 20160208

Tillgänglig från: 2016-02-08 Skapad: 2016-02-05 Senast uppdaterad: 2022-06-23Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Poláček, Lukas

Sök vidare i DiVA

Av författaren/redaktören
Poláček, Lukas
Av organisationen
Numerisk analys, NA
I samma tidskrift
Mathematical programming
Beräkningsmatematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 42 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf