Content deleted Content added
Citation bot (talk | contribs) Altered pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by Abductive | Category:NP-complete problems | #UCB_Category 121/181 |
→Complexity: −sp |
||
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==
| |||