Short Communication: Optimally Solving the Unit-Demand Envy-Free Pricing Problem with Metric Substitutability in Cubic Time
In general, the unit-demand envy-free pricing problem has proven to be APX-hard, but some special cases can be optimally solved in polynomial time. When substitution costs that form a metric space are included, the problem can be solved in <inline-formula><math xmlns="http://www.w3.org...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-09-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/14/10/279 |
| _version_ | 1827680413594681344 |
|---|---|
| author | Marcos M. Salvatierra Mario Salvatierra Juan G. Colonna |
| author_facet | Marcos M. Salvatierra Mario Salvatierra Juan G. Colonna |
| author_sort | Marcos M. Salvatierra |
| collection | DOAJ |
| description | In general, the unit-demand envy-free pricing problem has proven to be APX-hard, but some special cases can be optimally solved in polynomial time. When substitution costs that form a metric space are included, the problem can be solved in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>4</mn></msup><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> time, and when the number of consumers is equal to the number of items—all with a single copy so that each consumer buys an item—a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>3</mn></msup><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> time method is presented to solve it. This work shows that the first case has similarities with the second, and, by exploiting the structural properties of the costs set, it presents a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> time algorithm for solving it when a competitive equilibrium is considered or a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>3</mn></msup><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> time algorithm for more general scenarios. The methods are based on a dynamic programming strategy, which simplifies the calculations of the shortest paths in a network; this simplification is usually adopted in the second case. The theoretical results obtained provide efficiency in the search for optimal solutions to specific revenue management problems. |
| first_indexed | 2024-03-10T06:47:29Z |
| format | Article |
| id | doaj.art-9bbbc9d9157540d98706ff8f719c7d18 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T06:47:29Z |
| publishDate | 2021-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-9bbbc9d9157540d98706ff8f719c7d182023-11-22T17:08:13ZengMDPI AGAlgorithms1999-48932021-09-01141027910.3390/a14100279Short Communication: Optimally Solving the Unit-Demand Envy-Free Pricing Problem with Metric Substitutability in Cubic TimeMarcos M. Salvatierra0Mario Salvatierra1Juan G. Colonna2Institute of Computing, Federal University of Amazonas, Manaus 69067-005, BrazilInstitute of Computing, Federal University of Amazonas, Manaus 69067-005, BrazilInstitute of Computing, Federal University of Amazonas, Manaus 69067-005, BrazilIn general, the unit-demand envy-free pricing problem has proven to be APX-hard, but some special cases can be optimally solved in polynomial time. When substitution costs that form a metric space are included, the problem can be solved in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>4</mn></msup><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> time, and when the number of consumers is equal to the number of items—all with a single copy so that each consumer buys an item—a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>3</mn></msup><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> time method is presented to solve it. This work shows that the first case has similarities with the second, and, by exploiting the structural properties of the costs set, it presents a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> time algorithm for solving it when a competitive equilibrium is considered or a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>3</mn></msup><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> time algorithm for more general scenarios. The methods are based on a dynamic programming strategy, which simplifies the calculations of the shortest paths in a network; this simplification is usually adopted in the second case. The theoretical results obtained provide efficiency in the search for optimal solutions to specific revenue management problems.https://www.mdpi.com/1999-4893/14/10/279combinatorial optimizationenvy-free pricingmetric space |
| spellingShingle | Marcos M. Salvatierra Mario Salvatierra Juan G. Colonna Short Communication: Optimally Solving the Unit-Demand Envy-Free Pricing Problem with Metric Substitutability in Cubic Time Algorithms combinatorial optimization envy-free pricing metric space |
| title | Short Communication: Optimally Solving the Unit-Demand Envy-Free Pricing Problem with Metric Substitutability in Cubic Time |
| title_full | Short Communication: Optimally Solving the Unit-Demand Envy-Free Pricing Problem with Metric Substitutability in Cubic Time |
| title_fullStr | Short Communication: Optimally Solving the Unit-Demand Envy-Free Pricing Problem with Metric Substitutability in Cubic Time |
| title_full_unstemmed | Short Communication: Optimally Solving the Unit-Demand Envy-Free Pricing Problem with Metric Substitutability in Cubic Time |
| title_short | Short Communication: Optimally Solving the Unit-Demand Envy-Free Pricing Problem with Metric Substitutability in Cubic Time |
| title_sort | short communication optimally solving the unit demand envy free pricing problem with metric substitutability in cubic time |
| topic | combinatorial optimization envy-free pricing metric space |
| url | https://www.mdpi.com/1999-4893/14/10/279 |
| work_keys_str_mv | AT marcosmsalvatierra shortcommunicationoptimallysolvingtheunitdemandenvyfreepricingproblemwithmetricsubstitutabilityincubictime AT mariosalvatierra shortcommunicationoptimallysolvingtheunitdemandenvyfreepricingproblemwithmetricsubstitutabilityincubictime AT juangcolonna shortcommunicationoptimallysolvingtheunitdemandenvyfreepricingproblemwithmetricsubstitutabilityincubictime |