File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Approximation algorithms for the partial assignment problem

TitleApproximation algorithms for the partial assignment problem
Authors
KeywordsPartial assignment
Value query
General case
Submodular
Issue Date2020
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2020, v. 838, p. 231-237 How to Cite?
AbstractIn the partial assignment problem, a seller has an item set M = {i(1), i(2), ..., i(m)}, the amount of each item is exactly one. There are n buyers N = {b(1), b(2), ..., b(n)}, each buyer b y has a preferred bundle B-p subset of M and a value function f(p)(.). Assume that each item should be sold integrally and thus can be only assigned to at most one buyer. In previous works, buyers are often considered to be single-minded, i.e., a buyer can be either assigned the whole preferred bundle, or nothing. In this paper, we consider a more generalized and realistic model where the buyer can be partially satisfied, i.e., buyer b(p) can have some positive value if the seller assigns a subset of b(p)'s preferred bundle. However, there might be exponential number of subsets, to tackle this situation, a value oracle is implemented. We can get the value f(p) (S-p) for buyer b(p) and S-p subset of B-p by querying the value oracle. The objective is to assign items to buyers such that the total values are maximized, i.e., max Sigma(n)(p=1) f(p)(S-p). We first show that in this model, maximizing the total values is NP-hard. We then propose provably efficient approximation algorithms for general and submodular value functions respectively. If the value function satisfies non-negative, monotone and normalized, an 1/root m-approximation algorithm can be achieved. If the value function is submodular, the total values can be approximated within a factor of (1 -1/e). (C) 2020 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/294278
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.570
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorGao, G-
dc.contributor.authorNing, L-
dc.contributor.authorTing, HF-
dc.contributor.authorXu, Y-
dc.contributor.authorZhang, Y-
dc.contributor.authorZou, Y-
dc.date.accessioned2020-11-23T08:29:04Z-
dc.date.available2020-11-23T08:29:04Z-
dc.date.issued2020-
dc.identifier.citationTheoretical Computer Science, 2020, v. 838, p. 231-237-
dc.identifier.issn0304-3975-
dc.identifier.urihttp://hdl.handle.net/10722/294278-
dc.description.abstractIn the partial assignment problem, a seller has an item set M = {i(1), i(2), ..., i(m)}, the amount of each item is exactly one. There are n buyers N = {b(1), b(2), ..., b(n)}, each buyer b y has a preferred bundle B-p subset of M and a value function f(p)(.). Assume that each item should be sold integrally and thus can be only assigned to at most one buyer. In previous works, buyers are often considered to be single-minded, i.e., a buyer can be either assigned the whole preferred bundle, or nothing. In this paper, we consider a more generalized and realistic model where the buyer can be partially satisfied, i.e., buyer b(p) can have some positive value if the seller assigns a subset of b(p)'s preferred bundle. However, there might be exponential number of subsets, to tackle this situation, a value oracle is implemented. We can get the value f(p) (S-p) for buyer b(p) and S-p subset of B-p by querying the value oracle. The objective is to assign items to buyers such that the total values are maximized, i.e., max Sigma(n)(p=1) f(p)(S-p). We first show that in this model, maximizing the total values is NP-hard. We then propose provably efficient approximation algorithms for general and submodular value functions respectively. If the value function satisfies non-negative, monotone and normalized, an 1/root m-approximation algorithm can be achieved. If the value function is submodular, the total values can be approximated within a factor of (1 -1/e). (C) 2020 Elsevier B.V. All rights reserved.-
dc.languageeng-
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs-
dc.relation.ispartofTheoretical Computer Science-
dc.subjectPartial assignment-
dc.subjectValue query-
dc.subjectGeneral case-
dc.subjectSubmodular-
dc.titleApproximation algorithms for the partial assignment problem-
dc.typeArticle-
dc.identifier.emailTing, HF: hfting@cs.hku.hk-
dc.identifier.emailZhang, Y: yongzh@hku.hk-
dc.identifier.authorityTing, HF=rp00177-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.tcs.2020.07.041-
dc.identifier.scopuseid_2-s2.0-85089256506-
dc.identifier.hkuros319618-
dc.identifier.volume838-
dc.identifier.spage231-
dc.identifier.epage237-
dc.identifier.isiWOS:000566368800017-
dc.publisher.placeNetherlands-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats