Generalized assignment problem: Difference between revisions

Content deleted Content added

Revision as of 16:18, 28 June 2024 edit Straughn (talk \| contribs) Extended confirmed users 3,459 edits →Complexity: Fixed CS1 missing journal error Tag: Visual edit ← Previous edit		Latest revision as of 21:36, 3 October 2024 edit undo Giftlite (talk \| contribs) Autopatrolled, Extended confirmed users, Pending changes reviewers 39,854 edits →Further reading: +*
(3 intermediate revisions by 3 users not shown)
Line 22: == Complexity == The generalized assignment problem is [[NP-hard]],.<ref>{{citation \| last1 = Özbakir \| first1 = Lale \| last2 = Baykasoğlu \| first2 = Adil Line 33: \| volume = 215 \| issue = 11 \| year = 2010}}.</ref> However, there are linear-programming relaxations which give a <math>(1 - 1/e)</math>-approximation.<ref>{{cite conference \|last1=Fleischer \|first1=Lisa \|last2=Goemans \|first2=Michel X. \|last3=Mirrokni \|first3=Vahab S. \|last4=Sviridenko \|first4=Maxim \|date=2006 \|title=Tight approximation algorithms for maximum general assignment problems \|conference=Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 \|pages=~~611-620~~611–620}}</ref> ==Greedy approximation algorithm== Line 59 ⟶ 58: ==Further reading== * {{cite book \|isbn=978-3-540-24777-7\|title=Knapsack Problems\|last1=Kellerer\|first1=Hans\|last2=Pferschy\|first2=Ulrich\|last3=Pisinger\|first3=David\|date=2013-03-19\|publisher=Springer }} [[Category:NP-complete problems]]