File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.tcs.2020.03.017
- Scopus: eid_2-s2.0-85082431571
- WOS: WOS:000528250200002
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Offline and online algorithms for single-minded selling problem
Title | Offline and online algorithms for single-minded selling problem |
---|---|
Authors | |
Keywords | NP-hard Approximation ratio Competitive ratio Single-minded selling |
Issue Date | 2020 |
Publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs |
Citation | Theoretical Computer Science, 2020, v. 821, p. 15-22 How to Cite? |
Abstract | Given a seller with k types of items and n single-minded buyers, i.e., each buyer is only interested in a particular bundle of items, to maximize the revenue, the seller must assign some amount of bundles to each buyer with respect to the buyer's accepted price. Each buyer is associated with a value function such that is the accepted unit bundle price is willing to pay for x bundles. In this paper, we assume that bundles can be sold fractionally. The single-minded item selling problem is proved to be NP-hard. Moreover, we give an -approximation algorithm. For the online version, i.e., buyers come one by one and the decision must be made immediately on the arrival of each buyer, an -competitive algorithm is given, where h is the highest unit item price among all buyers. |
Persistent Identifier | http://hdl.handle.net/10722/294277 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 0.570 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Zhang, Y | - |
dc.contributor.author | Chin, FYL | - |
dc.contributor.author | Poon, SH | - |
dc.contributor.author | Ting, HF | - |
dc.contributor.author | Xu, D | - |
dc.contributor.author | Yu, D | - |
dc.date.accessioned | 2020-11-23T08:29:03Z | - |
dc.date.available | 2020-11-23T08:29:03Z | - |
dc.date.issued | 2020 | - |
dc.identifier.citation | Theoretical Computer Science, 2020, v. 821, p. 15-22 | - |
dc.identifier.issn | 0304-3975 | - |
dc.identifier.uri | http://hdl.handle.net/10722/294277 | - |
dc.description.abstract | Given a seller with k types of items and n single-minded buyers, i.e., each buyer is only interested in a particular bundle of items, to maximize the revenue, the seller must assign some amount of bundles to each buyer with respect to the buyer's accepted price. Each buyer is associated with a value function such that is the accepted unit bundle price is willing to pay for x bundles. In this paper, we assume that bundles can be sold fractionally. The single-minded item selling problem is proved to be NP-hard. Moreover, we give an -approximation algorithm. For the online version, i.e., buyers come one by one and the decision must be made immediately on the arrival of each buyer, an -competitive algorithm is given, where h is the highest unit item price among all buyers. | - |
dc.language | eng | - |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs | - |
dc.relation.ispartof | Theoretical Computer Science | - |
dc.subject | NP-hard | - |
dc.subject | Approximation ratio | - |
dc.subject | Competitive ratio | - |
dc.subject | Single-minded selling | - |
dc.title | Offline and online algorithms for single-minded selling problem | - |
dc.type | Article | - |
dc.identifier.email | Zhang, Y: yongzh@hku.hk | - |
dc.identifier.email | Chin, FYL: chin@cs.hku.hk | - |
dc.identifier.email | Ting, HF: hfting@cs.hku.hk | - |
dc.identifier.authority | Chin, FYL=rp00105 | - |
dc.identifier.authority | Ting, HF=rp00177 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/j.tcs.2020.03.017 | - |
dc.identifier.scopus | eid_2-s2.0-85082431571 | - |
dc.identifier.hkuros | 319617 | - |
dc.identifier.volume | 821 | - |
dc.identifier.spage | 15 | - |
dc.identifier.epage | 22 | - |
dc.identifier.isi | WOS:000528250200002 | - |
dc.publisher.place | Netherlands | - |