Revision as of 20:42, 25 December 2019 edit BernardoSulzbach (talk \| contribs) Extended confirmed users 1,533 edits Reorganized citations and changed them to use the {{cite}} templates; moved the book to further reading as it is not used in the text; added small paragraphs about what the cited papers actually did ← Previous edit		Revision as of 14:57, 26 February 2020 edit undo TPape (talk \| contribs) 27 edits →Complexity: Removed APX hard, as the terminology is less well known and it's meaning is better explained by the subsequent sentence Next edit →
Line 35: \| volume = 215 \| issue = 11 ~~There~~ \| isyear = 2010}}.</ref> However, there are linear-programming ~~relaxation algorithm~~relaxations which ~~gives~~give a <math>(1 - 1/e)</math>-approximation.<ref>{{cite journal \|last=Fleischer \|first=Lisa \|last2=Goemans \|first2=Michel X. \|last3=Mirrokni \|first3=Vahab S. \|last4=Sviridenko \|first4=Maxim \|title=Tight approximation algorithms for maximum general assignment problems \|date=2006}}</ref>▼ ~~\| year = 2010}}.</ref> and it is even [[APX-hard]] to approximate it.~~ ▲There is linear-programming relaxation algorithm which gives a <math>(1 - 1/e)</math>-approximation.<ref>{{cite journal \|last=Fleischer \|first=Lisa \|last2=Goemans \|first2=Michel X. \|last3=Mirrokni \|first3=Vahab S. \|last4=Sviridenko \|first4=Maxim \|title=Tight approximation algorithms for maximum general assignment problems \|date=2006}}</ref> ==Greedy approximation algorithm==

Generalized assignment problem: Difference between revisions