{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:32Z","timestamp":1787340392346,"version":"build-2736575974"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We investigate nonparametric multiproduct pricing problems, in which we want to find revenue maximizing prices for products $\\mathcal{P}$ based on a set of customer samples $\\mathcal{C}$. We mostly focus on the unit-demand case, in which products constitute strict substitutes and each customer aims to purchase a single product. In this setting a customer sample consists of a number of nonzero values for different products and possibly an additional product ranking. Once prices are fixed, each customer chooses to buy one of the products she can afford based on some predefined selection rule. We distinguish between the min-buying, max-buying, and rank-buying models. Some of our results also extend to single-minded pricing, in which case products are strict complements and every customer seeks to buy a single set of products, which she purchases if the sum of prices is below her valuation for that set. For the min-buying model we show that the revenue maximization problem is not approximable within factor $\\mathcal{O}(\\log^{\\varepsilon}|\\mathcal{C}|)$ for some constant $\\varepsilon&gt;0$, unless $\\mathrm{NP}\\subseteq\\mathrm{DTIME}(n^{\\mathcal{O}(\\log\\log n)})$, thereby almost closing the gap between the known algorithmic results and previous lower bounds. We also prove inapproximability within $\\mathcal{O}(\\ell^{\\varepsilon})$, $\\ell$ being an upper bound on the number of nonzero values per customer, and $\\mathcal{O}(|\\mathcal{P}|^{\\varepsilon})$ under slightly stronger assumptions and provide matching upper bounds. Surprisingly, these hardness results hold even if a price ladder constraint, i.e., a predefined order on the prices of all products, is given. Without the price ladder constraint we obtain similar hardness results for the special case of uniform valuations, i.e., the case that every customer has identical values for all the products she is interested in, assuming specific hardness of the balanced bipartite independent set problem in constant degree graphs or hardness of refuting random 3CNF formulas. Introducing a slightly more general problem definition in which customers are given as an explicit probability distribution, we obtain inapproximability within $\\mathcal{O}(|\\mathcal{P}|^{\\varepsilon})$ assuming $\\mathrm{NP}\\nsubseteq\\bigcap_{\\delta&gt;0}\\mathrm{BPTIME}(2^{\\mathcal{O}(n^{\\delta})})$. These results apply to single-minded pricing as well. For the max-buying model a polynomial-time approximation scheme exists if a price ladder is given. We give a matching lower bound by proving strong NP-hardness. Assuming limited product supply, we analyze a generic local search algorithm and prove that it is 2-approximate. Finally, we discuss implications for the rank-buying model.<\/jats:p>","DOI":"10.1137\/090752353","type":"journal-article","created":{"date-parts":[[2011,12,13]],"date-time":"2011-12-13T18:27:16Z","timestamp":1323800836000},"page":"1554-1586","source":"Crossref","is-referenced-by-count":13,"title":["Buying Cheap Is Expensive: Approximability of Combinatorial Pricing Problems"],"prefix":"10.1137","volume":"40","author":[{"given":"Patrick","family":"Briest","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piotr","family":"Krysta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,12,13]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"G. Aggarwal, T. Feder, R. Motwani, and A. Zhu,\n                      Algorithms for multi-product pricing\n                      , in Automata, Languages and Programming, Springer, Berlin, 2004, pp. 72\u201383.","DOI":"10.1007\/978-3-540-27836-8_9"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01277956"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi,\n                      Complexity and Approximation\n                      , Springer, Berlin, 1999.","DOI":"10.1007\/978-3-642-58412-1"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a009"},{"key":"R6","unstructured":"M. Balcan, A. Blum, J. Hartline, and Y. Mansour,\n                      Mechanism design via machine learning\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Balcan, A. Blum, and Y. Mansour,\n                      Item pricing for revenue maximization\n                      , in Proceedings of the 9th ACM Conference on Electronic Commerce, 2008.","DOI":"10.1145\/1386790.1386802"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90056-L"},{"key":"R9","unstructured":"A. Blum,\n                      Algorithms for Approximate Graph Coloring\n                      , Ph.D. thesis, MIT Laboratory for Computer Science, Cambridge, MA, 1991."},{"key":"R10","unstructured":"P. Briest, M. Hoefer, and P. Krysta,\n                      Stackelberg network pricing games\n                      , in Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"P. Briest and P. Krysta,\n                      Single-minded unlimited-supply pricing on sparse instances\n                      , in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006.","DOI":"10.1145\/1109557.1109678"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9299-y"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"S. Chawla, J. Hartline, and R. Kleinberg,\n                      Algorithmic pricing via virtual valuations\n                      , in Proceedings of the 8th ACM Conference on Electronic Commerce, 2007.","DOI":"10.1145\/1250910.1250946"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"N. Chen, A. Ghosh, and S. Vassilvitskii,\n                      Optimal envy-free pricing with metric substitutability\n                      , in Proceedings of the 9th ACM Conference on Electronic Commerce, 2008.","DOI":"10.1145\/1386790.1386803"},{"key":"R15","unstructured":"J. Chuzhoy, S. Kannan, and S. Khanna,\n                      Network Pricing for Multicommodity Flows\n                      , manuscript, 2007."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"W. Cook, W. Cunningham, W. Pulleyblank, and A. Schrijver,\n                      Combinatorial Optimization\n                      , John Wiley & Sons, New York, 1998.","DOI":"10.1002\/9781118033142"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/060656048"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"K. Elbassioni, R. Raman, S. Ray, and R. Sitters,\n                      On profit-maximizing pricing for the highway and tollbooth problems\n                      , in Proceedings of the 2nd International Symposium on Algorithmic Game Theory, 2009.","DOI":"10.1007\/978-3-642-04645-2_25"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"U. Feige,\n                      Relations between average case complexity and approximation complexity\n                      , in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002.","DOI":"10.1145\/509984.509985"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700380754"},{"key":"R21","unstructured":"U. Feige and S. Kogan,\n                      Hardness of Approximation of the Balanced Complete Bipartite Subgraph Problem\n                      , Technical report MCS04-04, Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel, 2004."},{"key":"R22","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, San Francisco, 1979."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1050.0252"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"A. Goldberg and J. Hartline,\n                      Competitive auctions for multiple digital goods\n                      , in Algorithms\u2014ESA 2001, Springer, Berlin, 2001, pp. 416\u2013427.","DOI":"10.1007\/3-540-44676-1_35"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"A. Goldberg, J. Hartline, and A. Wright,\n                      Competitive auctions and digital goods\n                      , in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001.","DOI":"10.1007\/3-540-44676-1_35"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"F. Grandoni and T. Rothvoss,\n                      Pricing and Paths: A PTAS for the highway problem\n                      , in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2011.","DOI":"10.1137\/1.9781611973082.53"},{"key":"R27","unstructured":"V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSherry,\n                      On profit-maximizing envy-free pricing\n                      , in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"J. Hartline and V. Koltun,\n                      Near-optimal pricing in near-linear time\n                      , in Algorithms and Data Structures, Springer, Berlin, 2005, pp. 422\u2013431.","DOI":"10.1007\/11534273_37"},{"key":"R29","unstructured":"S. Khot,\n                      Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique\n                      , in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"R32","unstructured":"N. Nisan and A. Ronen,\n                      Algorithmic mechanism design\n                      , in Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"R34","unstructured":"P. Rusmevichientong,\n                      A Non-Parametric Approach to Multi-Product Pricing: Theory and Application\n                      , Ph.D. thesis, Stanford University, Stanford, CA, 2003."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090752353","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:32:58Z","timestamp":1787337178000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090752353"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/090752353"],"URL":"https:\/\/doi.org\/10.1137\/090752353","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}