{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T00:00:25Z","timestamp":1740182425933,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,11,1]],"date-time":"2024-11-01T00:00:00Z","timestamp":1730419200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,1]],"date-time":"2024-11-01T00:00:00Z","timestamp":1730419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100015067","name":"Universidade do Estado do Amazonas","doi-asserted-by":"publisher","award":["01.02.011304.026190\/2022-07"],"award-info":[{"award-number":["01.02.011304.026190\/2022-07"]}],"id":[{"id":"10.13039\/501100015067","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004916","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado do Amazonas","doi-asserted-by":"publisher","award":["POSGRAD 22-23"],"award-info":[{"award-number":["POSGRAD 22-23"]}],"id":[{"id":"10.13039\/501100004916","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["001"],"award-info":[{"award-number":["001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper. Res. Forum"],"DOI":"10.1007\/s43069-024-00373-1","type":"journal-article","created":{"date-parts":[[2024,11,1]],"date-time":"2024-11-01T11:05:39Z","timestamp":1730459139000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Complexity Classes of Envy-Free Pricing Problems: A Short Survey"],"prefix":"10.1007","volume":"5","author":[{"given":"Marcos","family":"Salvatierra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan G.","family":"Colonna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mario","family":"Salvatierra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alcides","family":"de C. Amorim Neto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,1]]},"reference":[{"key":"373_CR1","doi-asserted-by":"publisher","unstructured":"Alimonti P, Kann V (1997) Hardness of approximating problems on cubic graphs. In: Bongiovanni GC, Bovet DP, Battista GD (eds) Algorithms and complexity, third Italian conference, CIAC \u201997, Rome, Italy, March 12-14, 1997, Proceedings, Lecture Notes in Computer Science, vol 1203. Springer, pp 288\u2013298. https:\/\/doi.org\/10.1007\/3-540-62592-5_80","DOI":"10.1007\/3-540-62592-5_80"},{"issue":"1","key":"373_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti P, Kann V (2000) Some apx-completeness results for cubic graphs. Theoret Comput Sci 237(1):123\u2013134. https:\/\/doi.org\/10.1016\/S0304-3975(98)00158-3","journal-title":"Theoret Comput Sci"},{"issue":"3","key":"373_CR3","doi-asserted-by":"publisher","first-page":"16:1","DOI":"10.1145\/3105786","volume":"5","author":"E Anshelevich","year":"2017","unstructured":"Anshelevich E, Kar K, Sekar S (2017) Envy-free pricing in large markets: approximating revenue and welfare. ACM Trans Econ Comput 5(3):16:1-16:42. https:\/\/doi.org\/10.1145\/3105786","journal-title":"ACM Trans Econ Comput"},{"key":"373_CR4","doi-asserted-by":"publisher","unstructured":"Arbib C, Kara\u015fan O, Pinar M (2019) On envy-free perfect matching. Discret Appl Math 261:22\u201327. https:\/\/doi.org\/10.1016\/j.dam.2018.03.034, gO X Meeting, Rigi Kaltbad (CH), July 10-14, 2016","DOI":"10.1016\/j.dam.2018.03.034"},{"key":"373_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","author":"G Ausiello","year":"1999","unstructured":"Ausiello G, Marchetti-Spaccamela A, Crescenzi P et al (1999) Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer. https:\/\/doi.org\/10.1007\/978-3-642-58412-1","journal-title":"Springer"},{"issue":"1","key":"373_CR6","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman R (1958) On a routing problem. Q Appl Math 16(1):87\u201390. https:\/\/doi.org\/10.1090\/qam\/102435","journal-title":"Q Appl Math"},{"key":"373_CR7","unstructured":"Berge C (2001) The theory of graphs. Courier Corporation"},{"key":"373_CR8","doi-asserted-by":"publisher","unstructured":"Berman P, Karpinski M (1999) On some tighter inapproximability results (extended abstract). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 1644 LNCS:200\u2013209. https:\/\/doi.org\/10.1007\/3-540-48523-6_17","DOI":"10.1007\/3-540-48523-6_17"},{"issue":"1","key":"373_CR9","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P Berman","year":"1992","unstructured":"Berman P, Schnitger G (1992) On the complexity of approximating the independent set problem. Inf Comput 96(1):77\u201394. https:\/\/doi.org\/10.1016\/0890-5401(92)90056-L","journal-title":"Inf Comput"},{"issue":"1\u20132","key":"373_CR10","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/s10107-020-01495-0","volume":"187","author":"T B\u00f6hnlein","year":"2021","unstructured":"B\u00f6hnlein T, Kratsch S, Schaudt O (2021) Revenue maximization in stackelberg pricing games: beyond the combinatorial setting. Math Program 187(1\u20132):653\u2013695. https:\/\/doi.org\/10.1007\/s10107-020-01495-0","journal-title":"Math Program"},{"key":"373_CR11","doi-asserted-by":"publisher","unstructured":"Bouhtou M, Grigoriev A, Hoesel Sv et al (2007a) Pricing bridges to cross a river. Naval Research Logistics (NRL) 54(4):411\u2013420. https:\/\/doi.org\/10.1002\/nav.20216","DOI":"10.1002\/nav.20216"},{"issue":"3","key":"373_CR12","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1287\/ijoc.1060.0177","volume":"19","author":"M Bouhtou","year":"2007","unstructured":"Bouhtou M, van Hoesel S, van der Kraaij AF et al (2007b) Tariff optimization in networks. INFORMS J Comput 19(3):458\u2013469. https:\/\/doi.org\/10.1287\/ijoc.1060.0177","journal-title":"INFORMS J Comput"},{"key":"373_CR13","doi-asserted-by":"publisher","unstructured":"Briest P, Krysta P (2006) Single-minded unlimited supply pricing on sparse instances. In: Proceedings of the annual ACM-SIAM symposium on discrete algorithms, pp 1093\u20131102. https:\/\/doi.org\/10.1145\/1109557.1109678","DOI":"10.1145\/1109557.1109678"},{"issue":"6","key":"373_CR14","doi-asserted-by":"publisher","first-page":"1554","DOI":"10.1137\/090752353","volume":"40","author":"P Briest","year":"2011","unstructured":"Briest P, Krysta P (2011) Buying cheap is expensive: approximability of combinatorial pricing problems. SIAM J Comput 40(6):1554\u20131586. https:\/\/doi.org\/10.1137\/090752353","journal-title":"SIAM J Comput"},{"issue":"2","key":"373_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","volume":"70","author":"RE Burkard","year":"1996","unstructured":"Burkard RE, Klinz B, Rudolf R (1996) Perspectives of monge properties in optimization. Discret Appl Math 70(2):95\u2013161. https:\/\/doi.org\/10.1016\/0166-218X(95)00103-X","journal-title":"Discret Appl Math"},{"issue":"2","key":"373_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2567923","volume":"10","author":"N Chen","year":"2014","unstructured":"Chen N, Deng X (2014) Envy-free pricing in multi-item markets. ACM Transactions on Algorithms (TALG) 10(2):1\u201315. https:\/\/doi.org\/10.1145\/2567923","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"3","key":"373_CR17","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1137\/080740970","volume":"40","author":"N Chen","year":"2011","unstructured":"Chen N, Ghosh A, Vassilvitskii S (2011) Optimal envy-free pricing with metric substitutability. SIAM J Comput 40(3):623\u2013645. https:\/\/doi.org\/10.1137\/080740970","journal-title":"SIAM J Comput"},{"issue":"3","key":"373_CR18","doi-asserted-by":"publisher","first-page":"1174","DOI":"10.1007\/s10878-014-9817-y","volume":"31","author":"N Chen","year":"2016","unstructured":"Chen N, Deng X, Goldberg PW et al (2016) On revenue maximization with sharp multi-unit demands. J Comb Optim 31(3):1174\u20131205. https:\/\/doi.org\/10.1007\/s10878-014-9817-y","journal-title":"J Comb Optim"},{"key":"373_CR19","doi-asserted-by":"publisher","unstructured":"Chudnovsky M, Robertson N, Seymour P et al (2006) The strong perfect graph theorem. Ann Math 164(1):51\u2013229. https:\/\/doi.org\/10.4007\/annals.2006.164.51, cited by: 718; All Open Access, Bronze Open Access, Green Open Access","DOI":"10.4007\/annals.2006.164.51"},{"key":"373_CR20","unstructured":"Cormen TH, Leiserson CE, Rivest RL et\u00a0al (2022) Introduction to algorithms. MIT press"},{"key":"373_CR21","doi-asserted-by":"publisher","unstructured":"Deng X, Goldberg P, Sun Y et al (2017) Pricing ad slots with consecutive multi-unit demand. Auton Agent Multi-Agent Syst 31(3):584\u2013605. https:\/\/doi.org\/10.1007\/s10458-016-9335-7, cited by: 1; All Open Access, Green Open Access","DOI":"10.1007\/s10458-016-9335-7"},{"key":"373_CR22","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.tcs.2012.07.028","volume":"460","author":"K Elbassioni","year":"2012","unstructured":"Elbassioni K, Raman R, Ray S et al (2012) On the complexity of the highway problem. Theoret Comput Sci 460:70\u201377. https:\/\/doi.org\/10.1016\/j.tcs.2012.07.028","journal-title":"Theoret Comput Sci"},{"key":"373_CR23","doi-asserted-by":"publisher","unstructured":"Fazli M, Nikparto N, Saghafian M (2011) Envy free chain store pricing. In: 2011 CSI international symposium on Computer Science and Software Engineering (CSSE), pp 44\u201347. https:\/\/doi.org\/10.1109\/CSICSSE.2011.5963991","DOI":"10.1109\/CSICSSE.2011.5963991"},{"key":"373_CR24","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U Feige","year":"2001","unstructured":"Feige U, Peleg D, Kortsarz G (2001) The dense k-subgraph problem. Algorithmica 29:410\u2013421. https:\/\/doi.org\/10.1007\/s004530010050","journal-title":"Algorithmica"},{"issue":"1","key":"373_CR25","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1137\/13094339X","volume":"45","author":"M Feldman","year":"2016","unstructured":"Feldman M, Gravin N, Lucier B (2016) Combinatorial walrasian equilibrium. SIAM J Comput 45(1):29\u201348","journal-title":"SIAM J Comput"},{"key":"373_CR26","doi-asserted-by":"publisher","unstructured":"Flammini M, Mauro M, Tonelli M (2021) On fair price discrimination in multi-unit markets. Artif Intell 290. https:\/\/doi.org\/10.1016\/j.artint.2020.103388","DOI":"10.1016\/j.artint.2020.103388"},{"issue":"3","key":"373_CR27","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M Garey","year":"1976","unstructured":"Garey M, Johnson D, Stockmeyer L (1976) Some simplified np-complete graph problems. Theoret Comput Sci 1(3):237\u2013267. https:\/\/doi.org\/10.1016\/0304-3975(76)90059-1","journal-title":"Theoret Comput Sci"},{"key":"373_CR28","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman"},{"issue":"2","key":"373_CR29","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1016\/j.disopt.2006.06.005","volume":"5","author":"O G\u00fcnl\u00fck","year":"2008","unstructured":"G\u00fcnl\u00fck O (2008) A pricing problem under monge property. Discret Optim 5(2):328\u2013336. https:\/\/doi.org\/10.1016\/j.disopt.2006.06.005","journal-title":"Discret Optim"},{"issue":"5","key":"373_CR30","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1016\/j.orl.2008.04.008","volume":"36","author":"A Grigoriev","year":"2008","unstructured":"Grigoriev A, van Loon J, Sviridenko M et al (2008) Optimal bundle pricing with monotonicity constraint. Oper Res Lett 36(5):609\u2013614. https:\/\/doi.org\/10.1016\/j.orl.2008.04.008","journal-title":"Oper Res Lett"},{"issue":"1","key":"373_CR31","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1002\/net.20260","volume":"53","author":"A Grigoriev","year":"2009","unstructured":"Grigoriev A, van Loon J, Sitters R et al (2009) Optimal pricing of capacitated networks. Networks 53(1):79\u201387. https:\/\/doi.org\/10.1002\/net.20260","journal-title":"Networks"},{"issue":"2","key":"373_CR32","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169\u2013197. https:\/\/doi.org\/10.1007\/BF02579273","journal-title":"Combinatorica"},{"key":"373_CR33","unstructured":"Guruswami V, Hartline JD, Karlin AR et\u00a0al (2005) On profit-maximizing envy-free pricing. In: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, SODA \u201905, pp 1164\u20131173. http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070598"},{"issue":"5","key":"373_CR34","doi-asserted-by":"publisher","first-page":"1194","DOI":"10.1137\/0913069","volume":"13","author":"P Hansen","year":"1992","unstructured":"Hansen P, Jaumard B, Savard G (1992) New branch-and-bound rules for linear bilevel programming. SIAM J Sci Stat Comput 13(5):1194\u20131217. https:\/\/doi.org\/10.1137\/0913069","journal-title":"SIAM J Sci Stat Comput"},{"key":"373_CR35","doi-asserted-by":"publisher","unstructured":"Hartline JD, Koltun V (2005) Near-optimal pricing in near-linear time. In: Dehne F, L\u00f3pez-Ortiz A, Sack JR (eds) Algorithms and data structures. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 422\u2013431. https:\/\/doi.org\/10.1007\/11534273_37","DOI":"10.1007\/11534273_37"},{"key":"373_CR36","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2023.05.006","author":"Q Jacquet","year":"2023","unstructured":"Jacquet Q, van Ackooij W, Alasseur C et al (2023) Quadratic regularization of bilevel pricing problems and application to electricity retail markets. Eur J Oper Res. https:\/\/doi.org\/10.1016\/j.ejor.2023.05.006","journal-title":"Eur J Oper Res"},{"issue":"2004","key":"373_CR37","first-page":"1","volume":"33","author":"B Kitchenham","year":"2004","unstructured":"Kitchenham B (2004) Procedures for performing systematic reviews. Keele, UK, Keele University 33(2004):1\u201326","journal-title":"Keele, UK, Keele University"},{"key":"373_CR38","doi-asserted-by":"crossref","unstructured":"Koopmans TC, Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica 25(1):53\u201376. http:\/\/www.jstor.org\/stable\/1907742","DOI":"10.2307\/1907742"},{"key":"373_CR39","unstructured":"Monaco G, Sankowski P, Zhang Q (2015) Revenue maximization envy-free pricing for homogeneous resources. In: Proceedings of the 24th international conference on artificial intelligence, IJCAI\u201915, pp 90\u2013960. http:\/\/dl.acm.org\/citation.cfm?id=2832249.2832262"},{"key":"373_CR40","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic game theory","author":"N Nisan","year":"2007","unstructured":"Nisan N, Roughgarden T, Tardos E et al (2007) Algorithmic game theory. Cambridge University Press, New York, NY, USA"},{"key":"373_CR41","unstructured":"Ortega-Arranz H, Gonzalez-Escribano A, Llanos DR (2022) The shortest-path problem: analysis and comparison of methods. Springer Nature"},{"key":"373_CR42","unstructured":"O\u2019Searcoid M (2006) Metric spaces. Springer Science & Business Media"},{"key":"373_CR43","doi-asserted-by":"publisher","unstructured":"Salvatierra MM, Salvatierra M, Colonna JG (2021) Short communication: optimally solving the unit-demand envy-free pricing problem with metric substitutability in cubic time. Algorithms 14(10). https:\/\/doi.org\/10.3390\/a14100279","DOI":"10.3390\/a14100279"},{"key":"373_CR44","unstructured":"Trudeau RJ (2013) Introduction to graph theory. Courier Corporation"},{"key":"373_CR45","doi-asserted-by":"publisher","unstructured":"Wohlin C (2014) Guidelines for snowballing in systematic literature studies and a replication in software engineering. In: Proceedings of the 18th international conference on evaluation and assessment in software engineering. Association for Computing Machinery, New York, NY, USA, EASE \u201914. https:\/\/doi.org\/10.1145\/2601248.2601268","DOI":"10.1145\/2601248.2601268"},{"key":"373_CR46","volume-title":"Integer and combinatorial optimization,","author":"LA Wolsey","year":"1999","unstructured":"Wolsey LA, Nemhauser GL (1999) Integer and combinatorial optimization, vol 55. John Wiley & Sons"}],"container-title":["Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-024-00373-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-024-00373-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-024-00373-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T16:03:37Z","timestamp":1734710617000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-024-00373-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,1]]},"references-count":46,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["373"],"URL":"https:\/\/doi.org\/10.1007\/s43069-024-00373-1","relation":{},"ISSN":["2662-2556"],"issn-type":[{"type":"electronic","value":"2662-2556"}],"subject":[],"published":{"date-parts":[[2024,11,1]]},"assertion":[{"value":"29 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics Approval"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to Participate"}},{"value":"The authors declare no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"103"}}