Generalized assignment problem: Difference between revisions

Content deleted Content added
Open access status updates in citations with OAbot #oabot
Complexity: Fixed CS1 missing journal error
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 journalconference |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 |dateconference=2006Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 |pages=611-620}}</ref>
 
 
==Greedy approximation algorithm==