Content deleted Content added
m -fix typo Tag: Reverted |
m iff means "if and only if" so not a typo |
||
Line 37:
== Linear programming formulation ==
A natural way to formulate the problem as a linear program is called the ''Lenstra–Shmoys–Tardos<ref name=":2">{{Cite journal|last1=Lenstra|first1=Jan Karel|last2=Shmoys|first2=David B.|last3=Tardos|first3=Éva|date=1990-01-01|title=Approximation algorithms for scheduling unrelated parallel machines|url=https://doi.org/10.1007/BF01585745|journal=Mathematical Programming|language=en|volume=46|issue=1|pages=259–271|doi=10.1007/BF01585745|issn=1436-4646|s2cid=206799898}}</ref> linear program (LST LP)''. For each machine ''i'' and job ''j<sub>,</sub>'' define a variable <math>z_{i,j}</math>, which equals 1
* <math>\sum_{i=1}^m z_{i,j} = 1</math> for every job ''j'' in 1,...,''n;''
Line 45:
Relaxing the integer constraints gives a linear program with size polynomial in the input. Solving the relaxed problem can be rounded to obtain a 2-approximation to the problem.''<ref name=":2" />''
Another LP formulation is the [[configuration linear program]]. For each machine ''i'', there are finitely many subsets of jobs that can be processed by machine ''i'' in time at most ''T''. Each such subset is called a ''configuration'' for machine ''i''. Denote by ''C<sub>i</sub>''(''T'') the set of all configurations for machine ''i''. For each machine ''i'' and configuration ''c'' in ''C<sub>i</sub>''(''T''), define a variable <math>x_{i,c}</math> which equals 1
* <math>\sum_{c\in C_i(T)}x_{i,c} = 1</math> for every machine ''i'' in 1,...,''m;''
| |||