Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet 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
Vise andre og tillknytning
2015 (engelsk)Inngår i: Mathematical programming, ISSN 0025-5610, E-ISSN 1436-4646, Vol. 154, nr 1-2, s. 427-462Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Springer, 2015. Vol. 154, nr 1-2, s. 427-462
Emneord [en]
68W25
HSV kategori
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
Merknad

QC 20160208

Tilgjengelig fra: 2016-02-08 Laget: 2016-02-05 Sist oppdatert: 2022-06-23bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Person

Poláček, Lukas

Søk i DiVA

Av forfatter/redaktør
Poláček, Lukas
Av organisasjonen
I samme tidsskrift
Mathematical programming

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 42 treff
RefereraExporteraLink to record
Permanent link

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