Abstrakt. Vi anser att vinstmaximering prisproblem, där vi ges en uppsättning m kunder och en uppsättning n objekt. Varje kund c är associerad med en delmängd Sc  till [n] av poster av intresse, tillsammans med en budget Bc, och vi antar att det finns en obegränsad tillgång på varje post. När priserna är fasta för alla objekt, varje kund c köper en delmängd av objekt i Sc, enligt dess köpregel. Målet är att ställa in posten priser för att maximera den totala vinsten. Vi studerar enhet-efterfrågan min-buying prissättning (UPP MIN ) och den ensinnade prissättning (SMP) problem. I det tidigare problemet, varje kund c köper den billigaste posten i  och Sc, om dess pris inte är högre än budgeten Bc, och köper ingenting annat. I det senare problemet, varje kund c köper hela uppsättningen Sc om dess totala pris är som mest Bc, och köper ingenting annat. Båda problemen är kända för att erkänna O(min {log(m + n), n})-tillnärmning algoritmer. Vi bevisar att de är log 1− (m + n) svårt att approximera för någon konstant, Om inte NP  till DTIME(n log δ n ), där δ är en konstant beroende på. Om vi begränsar vår uppmärksamhet till approximativa faktorer beroende enbart på n, visar vi att dessa problem är 2 log 1−δ nhard till approximation för någon δ > 0 om inte NP  på ZPTIME(n log δ n ), där δ är något konstant beroende på δ. Vi bevisar också att begränsade versioner av UDP MIN och SMP, där storleken på uppsättningarna Sc begränsas av k, är k 1/2-hård till ungefärlig för alla konstant. Vi vänder oss sedan till problemet med avgiftsprissättning, ett specialfall av SMP, där varje objekt motsvarar en kant i inmatningskurvan, och varje uppsättning
Den logaritmiska approximationen är i huvudsak snäv: Chalermsook et al. visa för varje konstant > 0 det finns ingen O(log 1− (m + n))- tillnärmning om inte NP  och DTIME(n polylog(n) ) REF.
Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply
{'venue': 'APPROX-RANDOM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}