Generalized assignment problem: Difference between revisions

Content deleted Content added

Revision as of 12:58, 12 August 2024 edit Citation bot (talk \| contribs) Bots 5,863,667 edits Altered pages. Formatted dashes. \| Use this bot. Report bugs. \| Suggested by Abductive \| Category:NP-complete problems \| #UCB_Category 121/181 ← 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: +*
(2 intermediate revisions by 2 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 34: \| 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}}</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]]