Approximation algorithms for the max-buying problem with limited supply

DOI10.1007/S00453-017-0364-7MaRDI QIDQ1755724zbMATH OpenOpenAlexWikidataFDO

Authors Cristina G. Fernandes, Rafael C. S. Schouery

Publication date 11 January 2019

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.7955

zbMATH Keywords

randomized algorithmsapproximation algorithmseconomicspricing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25) Consumer behavior, demand theory (91B42) Microeconomic theory (price theory and economic markets) (91B24)

Abstract: We consider the Max-Buying Problem with Limited Supply, in which there are $n$ items, with $C_i$ copies of each item $i$, and $m$ bidders such that every bidder $b$ has valuation $v_{ib}$ for item $i$. The goal is to find a pricing $p$ and an allocation of items to bidders that maximizes the profit, where every item is allocated to at most $C_i$ bidders, every bidder receives at most one item and if a bidder $b$ receives item $i$ then $p_{i}leq{v}_{ib}$. Briest and Krysta presented a 2-approximation for this problem and Aggarwal et al. presented a 4-approximation for the Price Ladder variant where the pricing must be non-increasing (that is, $p_{1}geq{p}_{2}geqcdotsgeq{p}_n$). We present an $e/(e-1)$-approximation for the Max-Buying Problem with Limited Supply and, for every $varepsilon>0$, a $(2+varepsilon)$-approximation for the Price Ladder variant.

Recommendations

• Approximation algorithms for the max-buying problem with limited supply
• Approximation Algorithms for the Max-Min Allocation Problem
• Approximation algorithms for a generalization of the maximum budget allocation
• scientific article; zbMATH DE number 1833405
• Approximation algorithms for the selling with preference
• scientific article; zbMATH DE number 1002206
• Approximation algorithms for the maximum satisfiability problem
• Approximation algorithms for nonuniform buy-at-bulk network design

Cites work

• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• scientific article; zbMATH DE number 3069630 (Why is no real title available?)
• A Nonparametric Approach to Multiproduct Pricing
• Algorithms for the Assignment and Transportation Problems
• Approximation algorithms for the max-buying problem with limited supply
• Automata, Languages and Programming
• Buying cheap is expensive: hardness of non-parametric multi-product pricing
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Geometric algorithms and combinatorial optimization
• Heuristics for the fixed cost median problem
• Improved hardness results for profit maximization pricing problems with unlimited supply
• On a combinatorial game
• On profit-maximizing envy-free pricing
• The envy-free pricing problem, unit-demand markets and connections with the network pricing problem
• Uniform Budgets and the Envy-Free Pricing Problem

Cited in

(3)

• Buying cheap is expensive: approximability of combinatorial pricing problems
• Approximation algorithms for the max-buying problem with limited supply
• Buying cheap is expensive: hardness of non-parametric multi-product pricing

This page was built for publication: Approximation algorithms for the max-buying problem with limited supply

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1755724)