Vi presenterar en enkel familj av algoritmer för att lösa problemet med generaliserat uppdrag (GAP). Vår teknik är baserad på en ny kombinatorisk översättning av någon algoritm för knapsack problem till en approximation algoritm för GAP. Om approximationsförhållandet för knapsackalgoritmen är α och dess körtid är O(f (N )), garanterar vår algoritm ett (1 + α)-tillnärmningsförhållande, och det körs i O(M · f (N) + M · N), där N är antalet objekt och M är antalet bins. Inte bara vår teknik utgör en allmän intressant ram för GAP-problemet; det matchar också den bästa combinatorial approximation för detta problem, med en mycket enklare algoritm och en bättre körtid.
A (2 + ε) - approximation algoritm med samma garanti som kombinatorial lokal sökning men en bättre körtid ges i REF.
An efficient approximation for the Generalized Assignment Problem
{'venue': 'Information Processing Letters', 'journal': 'Information Processing Letters', 'mag_field_of_study': ['Mathematics', 'Computer Science']}