Generalized assignment problem: Difference between revisions

Content deleted Content added

Revision as of 06:37, 11 January 2024 edit Sir Ibee (talk \| contribs) Extended confirmed users 3,978 edits Open access status updates in citations with OAbot #oabot Tag: OAbot [2.1] ← 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: +*
(4 intermediate revisions by 4 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 ~~journal~~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 \|~~date~~conference=~~2006~~Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 \|pages=611–620}}</ref> ==Greedy approximation algorithm== Line 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]]