1147:: In some cases, the jobs may be dependent. For example, take the case of reading user credentials from console, then use it to authenticate, then if authentication is successful display some data on the console. Clearly one task is dependent upon another. This is a clear case of where some kind of
1173:
if it is taken at run time. For static scheduling algorithms, a typical approach is to rank the tasks according to their precedence relationships and use a list scheduling technique to schedule them onto the processors.
684:, so it is an FPTAS. They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case. They do not present an algorithm for
858:
1098:. It means that, if a machine reports a higher speed, and all other inputs remain the same, then the total processing time allocated to the machine weakly increases. For this problem:
477:
1004:
902:
682:
316:(Shortest Processing Time First), sorts the jobs by their length, shortest first, and then assigns them to the processor with the earliest end time so far. It runs in time O(
289:
960:
638:
796:
186:" is a uniform machine scheduling problem with no constraints, where the goal is to minimize the maximum completion time. A special case of uniform machine scheduling is
514:
410:
359:
240:
184:
816:
1090:
In some settings, the machine speed is the machine's private information, and we want to incentivize machines to reveal their true speed, that is, we want a
1169:
if the scheduling decisions as to what computational tasks will be allocated to what processors are made before running the program. An algorithm is
738:
completion time on both uniform and unrelated machines. These algorithms run in exponential time (recall that these problems are all NP-hard).
1761:
1006:. They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case.
717:
1691:
Kwok, Yu-Kwong; Ahmad, Ishfaq (1999-12-01). "Static scheduling algorithms for allocating directed task graphs to multiprocessors".
1180:: In various settings, each job might have several operations that must be executed in parallel. Some such settings are handled by
1675:
1638:
1601:
1564:
741:
579:
1201:
1754:
1519:
1129:
presented a 5-approximation monotone algorithm, which runs in polytime even when the number of machines is variable.
821:
1115:
algorithm is monotone whenever the machine speeds are powers of some c ≥ 2, but not when c ≤ 1.78. In contrast,
1414:"A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach"
1914:
1800:
1790:
1014:
187:
1105:
presented a 4-approximation monotone algorithm, which runs in polytime when the number of machines is fixed.
1747:
421:
1909:
965:
863:
643:
97:
are unrelated, and any matrix of positive processing times is possible. In the specific variant called
1785:
1662:. Lecture Notes in Computer Science. Vol. 3669. Berlin, Heidelberg: Springer. pp. 616–627.
1588:. Lecture Notes in Computer Science. Vol. 3351. Berlin, Heidelberg: Springer. pp. 267–280.
1551:. Lecture Notes in Computer Science. Vol. 2996. Berlin, Heidelberg: Springer. pp. 608–619.
254:
1705:
919:
597:
1816:
1625:. Lecture Notes in Computer Science. Vol. 3404. Berlin, Heidelberg: Springer. pp. 69–82.
244:
1888:
1581:
1544:
1112:
759:
242:. More generally, when some jobs are more important than others, it may be desired to minimize a
1618:
489:
385:
334:
215:
1862:
1852:
1770:
1700:
1365:"Using dual approximation algorithms for scheduling problems theoretical and practical results"
162:
149:
43:
1857:
540:
It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the
1826:
1821:
1185:
1181:
31:
1453:"Approximation Schemes for Schedulingon Uniformly Related and Identical Parallel Machines"
1030:
generalized the PTAS for uniform machines to handle more general objective functions. Let
8:
1883:
1831:
1189:
731:
565:
550:
presents an exponential-time algorithm and a polynomial-time approximation algorithm for
39:
1655:
1867:
1726:
1525:
1480:
1394:
1260:
1091:
801:
1730:
1718:
1671:
1634:
1597:
1560:
1515:
1472:
1433:
1386:
1345:
1301:
1252:
710:
541:
1529:
1484:
1264:
1710:
1663:
1626:
1589:
1552:
1507:
1464:
1425:
1398:
1376:
1335:
1291:
1242:
1152:
534:
35:
1739:
248:
of the completion time, where each job has a different weight. This is denoted by
1593:
1556:
1545:"Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines"
1413:
1165:: Machine scheduling algorithms are static or dynamic. A scheduling algorithm is
1156:
1116:
1630:
1543:
Auletta, Vincenzo; De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe (2004).
1499:
1468:
1071:
is any fixed function. Similarly, one can minimize the objective function sum(
1903:
1722:
1511:
1476:
1437:
1390:
1349:
1305:
1256:
1452:
1619:"Truthful Approximation Mechanisms for Scheduling Selfish Related Machines"
1159:. This adds further complication to the multiprocessor scheduling problem.
1151:
exists between the tasks. In fact it is clear that it can be modelled with
1148:
1714:
1340:
1323:
1296:
1279:
1247:
1230:
1656:"Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines"
1231:"Exact and Approximate Algorithms for Scheduling Nonidentical Processors"
79:- the total time required to execute the schedule. The time that machine
1667:
190:, in which all machines have the same speed. This variant is denoted by
1582:"Deterministic Monotone Algorithms for Scheduling on Related Machines"
1381:
1364:
1049:
in a given schedule. Instead of minimizing the objective function max(
1429:
696:
1847:
76:
1504:
Proceedings 42nd IEEE Symposium on
Foundations of Computer Science
520:
1542:
1013:
presented several approximation algorithms for any number of
905:
1280:"Scheduling independent tasks to reduce mean finishing time"
1094:. An important consideration for attaining truthfulness is
197:
In some variants of the problem, instead of minimizing the
71:
of varying processing times, which need to be scheduled on
156:
in the first field. For example, the problem denoted by "
299:
150:
three-field notation for optimal job scheduling problems
1658:. In Brodal, Gerth Stølting; Leonardi, Stefano (eds.).
1202:
Summary of parallel machine problems without preemtion
105:
faster than others. This means that, for each machine
1155:. Then, by definition, the set of tasks constitute a
968:
922:
866:
824:
804:
762:
646:
600:
492:
424:
388:
337:
257:
218:
165:
1584:. In Persiano, Giuseppe; Solis-Oba, Roberto (eds.).
1769:
1412:Hochbaum, Dorit S.; Shmoys, David B. (1988-06-01).
1363:Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01).
1278:Bruno, J.; Coffman, E. G.; Sethi, R. (1974-07-01).
748:>0, attain at most (1+ε)OPT. For minimizing the
716:A constant-factor approximation is attained by the
586:>0, attain at most (1+ε)OPT. For minimizing the
576:
machines. These algorithms run in exponential time.
1617:Andelman, Nir; Azar, Yossi; Sorani, Motti (2005).
1616:
998:
954:
896:
852:
810:
790:
676:
632:
508:
471:
404:
353:
283:
234:
178:
1277:
697:Minimizing the maximum completion time (makespan)
375:), for minimizing the average completion time on
1901:
1085:
479:, for minimizing the average completion time on
431:
324:), and minimizes the average completion time on
308:completion time can be done in polynomial time:
171:
75:different machines. The goal is to minimize the
1579:
1135:presented a 3-approximation monotone algorithm.
1056:), one can minimize the objective function max(
521:Minimizing the weighted-average completion time
201:completion time, it is desired to minimize the
1580:Ambrosio, Pasquale; Auletta, Vincenzo (2005).
1500:"Truthful mechanisms for one-parameter agents"
1411:
1362:
83:needs in order to process job j is denoted by
1755:
1324:"Algorithms for Scheduling Independent Tasks"
1229:Horowitz, Ellis; Sahni, Sartaj (1976-04-01).
1228:
1621:. In Diekert, Volker; Durand, Bruno (eds.).
1547:. In Diekert, Volker; Habib, Michel (eds.).
1497:
1450:
853:{\displaystyle \epsilon \geq 2\cdot 10^{-l}}
367:present an exact algorithm, with run time O(
152:, the uniform-machine variant is denoted by
1762:
1748:
1704:
1690:
1451:Epstein, Leah; Sgall, Jiri (2004-05-01).
1380:
1339:
1295:
1246:
756:machines, their algorithm runs in time
718:Longest-processing-time-first algorithm
1902:
1653:
1103:Auletta, De Prisco, Penna and Persiano
418:present an algorithm, running in time
300:Minimizing the average completion time
1743:
1498:Archer, A.; Tardos, E. (2001-10-01).
1321:
742:Polynomial-time approximation schemes
580:Polynomial-time approximation schemes
472:{\displaystyle O(\max(mn^{2},n^{3}))}
1317:
1315:
1224:
1222:
1220:
1218:
1216:
705:completion time is NP-hard even for
24:uniformly-related machine scheduling
1586:Approximation and Online Algorithms
1020:. Later, they developed a PTAS for
529:completion time is NP-hard even on
205:completion time (averaged over all
13:
1356:
999:{\displaystyle O(n^{2}/\epsilon )}
897:{\displaystyle O(n/\epsilon ^{2})}
818:is the smallest integer for which
677:{\displaystyle O(n^{2}/\epsilon )}
14:
1926:
1312:
1213:
1195:
90:. In the general case, the times
860:. Therefore, the run-time is in
709:machines, by reduction from the
570:weighted-average completion time
533:machines, by reduction from the
1684:
1647:
1610:
1322:Sahni, Sartaj K. (1976-01-01).
284:{\displaystyle \sum w_{i}C_{i}}
1573:
1536:
1491:
1444:
1405:
1271:
993:
972:
955:{\displaystyle O(10^{l}n^{2})}
949:
926:
891:
870:
785:
766:
734:algorithms for minimizing the
671:
650:
633:{\displaystyle O(10^{l}n^{2})}
627:
604:
568:algorithms for minimizing the
466:
463:
434:
428:
1:
1207:
1139:
1086:Monotonicity and Truthfulness
1045:) be the makespan of machine
294:
188:identical-machines scheduling
1594:10.1007/978-3-540-31833-0_22
1557:10.1007/978-3-540-24749-4_53
7:
1631:10.1007/978-3-540-31856-9_6
791:{\displaystyle O(10^{2l}n)}
10:
1931:
1654:Kovács, Annamária (2005).
916:machines, the run-time is
594:machines, the run-time is
509:{\displaystyle \sum C_{i}}
405:{\displaystyle \sum C_{i}}
354:{\displaystyle \sum C_{i}}
235:{\displaystyle \sum C_{i}}
116:, and the run-time of job
109:, there is a speed factor
99:uniform machine scheduling
28:related machine scheduling
20:Uniform machine scheduling
1876:
1840:
1809:
1778:
1469:10.1007/s00453-003-1077-7
1418:SIAM Journal on Computing
1284:Communications of the ACM
1127:Andelman, Azar and Sorani
179:{\displaystyle C_{\max }}
1512:10.1109/SFCS.2001.959924
416:Bruno, Coffman and Sethi
209:jobs); it is denoted by
1889:Truthful job scheduling
1841:Optimization objectives
1113:Longest Processing Time
912:completion time on two
752:completion time on two
590:completion time on two
1771:Optimal job scheduling
1000:
956:
898:
854:
812:
792:
678:
634:
510:
473:
406:
355:
285:
236:
180:
44:optimal job scheduling
1715:10.1145/344588.344618
1693:ACM Computing Surveys
1660:Algorithms – ESA 2005
1341:10.1145/321921.321934
1297:10.1145/361011.361064
1248:10.1145/321941.321951
1163:Static versus Dynamic
1001:
957:
908:. For minimizing the
899:
855:
813:
793:
679:
635:
511:
474:
407:
356:
286:
237:
181:
42:. It is a variant of
1915:NP-complete problems
1506:. pp. 482–491.
1186:flow shop scheduling
1182:open shop scheduling
1119:is not monotone for
1109:Ambrosio and Auletta
966:
920:
864:
822:
802:
760:
644:
598:
490:
422:
386:
335:
255:
216:
194:in the first field.
163:
101:, some machines are
32:optimization problem
16:Optimization prpblem
1884:Interval scheduling
1668:10.1007/11561071_55
1190:job shop scheduling
1011:Hochbaum and Shmoys
732:dynamic programming
688:completion time on
566:dynamic programming
40:operations research
1910:Optimal scheduling
1877:Other requirements
1801:Unrelated machines
1791:Identical machines
1369:Journal of the ACM
1328:Journal of the ACM
1235:Journal of the ACM
1092:truthful mechanism
996:
952:
894:
850:
808:
788:
724:Horowitz and Sahni
674:
630:
558:Horowitz and Sahni
506:
469:
402:
365:Horowitz and Sahni
351:
281:
232:
176:
1897:
1896:
1677:978-3-540-31951-1
1640:978-3-540-31856-9
1603:978-3-540-31833-0
1566:978-3-540-24749-4
1382:10.1145/7531.7535
1157:lattice structure
1028:Epstein and Sgall
811:{\displaystyle l}
711:partition problem
542:partition problem
1922:
1810:Multi-stage jobs
1796:Uniform machines
1764:
1757:
1750:
1741:
1740:
1735:
1734:
1708:
1688:
1682:
1681:
1651:
1645:
1644:
1614:
1608:
1607:
1577:
1571:
1570:
1540:
1534:
1533:
1495:
1489:
1488:
1448:
1442:
1441:
1409:
1403:
1402:
1384:
1360:
1354:
1353:
1343:
1319:
1310:
1309:
1299:
1275:
1269:
1268:
1250:
1226:
1178:Multi-stage jobs
1153:partial ordering
1111:proved that the
1005:
1003:
1002:
997:
989:
984:
983:
961:
959:
958:
953:
948:
947:
938:
937:
903:
901:
900:
895:
890:
889:
880:
859:
857:
856:
851:
849:
848:
817:
815:
814:
809:
797:
795:
794:
789:
781:
780:
744:, which for any
686:weighted-average
683:
681:
680:
675:
667:
662:
661:
639:
637:
636:
631:
626:
625:
616:
615:
588:weighted average
582:, which for any
535:knapsack problem
527:weighted average
515:
513:
512:
507:
505:
504:
478:
476:
475:
470:
462:
461:
449:
448:
411:
409:
408:
403:
401:
400:
360:
358:
357:
352:
350:
349:
290:
288:
287:
282:
280:
279:
270:
269:
245:weighted average
241:
239:
238:
233:
231:
230:
185:
183:
182:
177:
175:
174:
148:In the standard
36:computer science
1930:
1929:
1925:
1924:
1923:
1921:
1920:
1919:
1900:
1899:
1898:
1893:
1872:
1836:
1805:
1774:
1768:
1738:
1706:10.1.1.322.2295
1689:
1685:
1678:
1652:
1648:
1641:
1615:
1611:
1604:
1578:
1574:
1567:
1541:
1537:
1522:
1496:
1492:
1449:
1445:
1430:10.1137/0217033
1410:
1406:
1361:
1357:
1320:
1313:
1276:
1272:
1227:
1214:
1210:
1198:
1142:
1117:List scheduling
1088:
1080:
1065:
1054:
1035:
985:
979:
975:
967:
964:
963:
943:
939:
933:
929:
921:
918:
917:
885:
881:
876:
865:
862:
861:
841:
837:
823:
820:
819:
803:
800:
799:
773:
769:
761:
758:
757:
701:Minimizing the
699:
663:
657:
653:
645:
642:
641:
621:
617:
611:
607:
599:
596:
595:
525:Minimizing the
523:
500:
496:
491:
488:
487:
457:
453:
444:
440:
423:
420:
419:
396:
392:
387:
384:
383:
345:
341:
336:
333:
332:
304:Minimizing the
302:
297:
275:
271:
265:
261:
256:
253:
252:
226:
222:
217:
214:
213:
170:
166:
164:
161:
160:
143:
136:
129:
114:
95:
88:
69:
63:
56:
46:. We are given
17:
12:
11:
5:
1928:
1918:
1917:
1912:
1895:
1894:
1892:
1891:
1886:
1880:
1878:
1874:
1873:
1871:
1870:
1865:
1860:
1855:
1850:
1844:
1842:
1838:
1837:
1835:
1834:
1829:
1824:
1819:
1817:Parallel tasks
1813:
1811:
1807:
1806:
1804:
1803:
1798:
1793:
1788:
1786:Single machine
1782:
1780:
1779:One-stage jobs
1776:
1775:
1767:
1766:
1759:
1752:
1744:
1737:
1736:
1699:(4): 406–471.
1683:
1676:
1646:
1639:
1609:
1602:
1572:
1565:
1535:
1520:
1490:
1443:
1424:(3): 539–551.
1404:
1375:(1): 144–162.
1355:
1334:(1): 116–127.
1311:
1290:(7): 382–387.
1270:
1241:(2): 317–327.
1211:
1209:
1206:
1205:
1204:
1197:
1196:External links
1194:
1145:Dependent jobs
1141:
1138:
1137:
1136:
1130:
1124:
1106:
1087:
1084:
1078:
1063:
1052:
1041:between 1 and
1033:
1008:
1007:
995:
992:
988:
982:
978:
974:
971:
951:
946:
942:
936:
932:
928:
925:
904:, so it is an
893:
888:
884:
879:
875:
872:
869:
847:
844:
840:
836:
833:
830:
827:
807:
787:
784:
779:
776:
772:
768:
765:
739:
698:
695:
694:
693:
673:
670:
666:
660:
656:
652:
649:
629:
624:
620:
614:
610:
606:
603:
577:
522:
519:
518:
517:
503:
499:
495:
468:
465:
460:
456:
452:
447:
443:
439:
436:
433:
430:
427:
413:
399:
395:
391:
362:
348:
344:
340:
301:
298:
296:
293:
278:
274:
268:
264:
260:
229:
225:
221:
173:
169:
141:
134:
127:
112:
93:
86:
67:
61:
54:
15:
9:
6:
4:
3:
2:
1927:
1916:
1913:
1911:
1908:
1907:
1905:
1890:
1887:
1885:
1882:
1881:
1879:
1875:
1869:
1866:
1864:
1861:
1859:
1856:
1854:
1851:
1849:
1846:
1845:
1843:
1839:
1833:
1830:
1828:
1825:
1823:
1820:
1818:
1815:
1814:
1812:
1808:
1802:
1799:
1797:
1794:
1792:
1789:
1787:
1784:
1783:
1781:
1777:
1772:
1765:
1760:
1758:
1753:
1751:
1746:
1745:
1742:
1732:
1728:
1724:
1720:
1716:
1712:
1707:
1702:
1698:
1694:
1687:
1679:
1673:
1669:
1665:
1661:
1657:
1650:
1642:
1636:
1632:
1628:
1624:
1620:
1613:
1605:
1599:
1595:
1591:
1587:
1583:
1576:
1568:
1562:
1558:
1554:
1550:
1546:
1539:
1531:
1527:
1523:
1521:0-7695-1390-5
1517:
1513:
1509:
1505:
1501:
1494:
1486:
1482:
1478:
1474:
1470:
1466:
1462:
1458:
1454:
1447:
1439:
1435:
1431:
1427:
1423:
1419:
1415:
1408:
1400:
1396:
1392:
1388:
1383:
1378:
1374:
1370:
1366:
1359:
1351:
1347:
1342:
1337:
1333:
1329:
1325:
1318:
1316:
1307:
1303:
1298:
1293:
1289:
1285:
1281:
1274:
1266:
1262:
1258:
1254:
1249:
1244:
1240:
1236:
1232:
1225:
1223:
1221:
1219:
1217:
1212:
1203:
1200:
1199:
1193:
1191:
1187:
1183:
1179:
1175:
1172:
1168:
1164:
1160:
1158:
1154:
1150:
1146:
1134:
1131:
1128:
1125:
1122:
1118:
1114:
1110:
1107:
1104:
1101:
1100:
1099:
1097:
1093:
1083:
1081:
1074:
1070:
1066:
1059:
1055:
1048:
1044:
1040:
1036:
1029:
1025:
1023:
1019:
1017:
1012:
990:
986:
980:
976:
969:
944:
940:
934:
930:
923:
915:
911:
907:
886:
882:
877:
873:
867:
845:
842:
838:
834:
831:
828:
825:
805:
782:
777:
774:
770:
763:
755:
751:
747:
743:
740:
737:
733:
729:
728:
727:
725:
721:
719:
714:
712:
708:
704:
691:
687:
668:
664:
658:
654:
647:
622:
618:
612:
608:
601:
593:
589:
585:
581:
578:
575:
571:
567:
563:
562:
561:
559:
555:
553:
549:
545:
543:
539:
536:
532:
528:
501:
497:
493:
486:
482:
458:
454:
450:
445:
441:
437:
425:
417:
414:
397:
393:
389:
382:
378:
374:
370:
366:
363:
346:
342:
338:
331:
327:
323:
319:
315:
314:SPT algorithm
311:
310:
309:
307:
292:
276:
272:
266:
262:
258:
251:
247:
246:
227:
223:
219:
212:
208:
204:
200:
195:
193:
189:
167:
159:
155:
151:
146:
144:
137:
130:
123:
119:
115:
108:
104:
100:
96:
89:
82:
78:
74:
70:
60:
53:
49:
45:
41:
37:
33:
29:
25:
22:(also called
21:
1795:
1696:
1692:
1686:
1659:
1649:
1622:
1612:
1585:
1575:
1548:
1538:
1503:
1493:
1463:(1): 43–57.
1460:
1457:Algorithmica
1456:
1446:
1421:
1417:
1407:
1372:
1368:
1358:
1331:
1327:
1287:
1283:
1273:
1238:
1234:
1177:
1176:
1170:
1166:
1162:
1161:
1144:
1143:
1132:
1126:
1120:
1108:
1102:
1096:monotonicity
1095:
1089:
1076:
1072:
1068:
1061:
1057:
1050:
1046:
1042:
1038:
1031:
1027:
1026:
1021:
1015:
1010:
1009:
913:
909:
753:
749:
745:
735:
723:
722:
715:
706:
702:
700:
689:
685:
591:
587:
583:
573:
569:
557:
556:
551:
547:
546:
538:
530:
526:
524:
484:
480:
415:
380:
376:
372:
368:
364:
329:
325:
321:
317:
313:
305:
303:
249:
243:
210:
206:
202:
198:
196:
191:
157:
153:
147:
139:
132:
125:
121:
117:
110:
106:
102:
98:
91:
84:
80:
72:
65:
58:
51:
47:
27:
23:
19:
18:
726:presented:
560:presented:
483:machines,
379:machines,
120:on machine
1904:Categories
1868:Throughput
1623:Stacs 2005
1549:Stacs 2004
1208:References
1140:Extensions
1067:)), where
1024:machines.
554:machines.
328:machines,
295:Algorithms
1863:Tardiness
1853:Earliness
1827:Flow shop
1822:Open shop
1731:207614150
1723:0360-0300
1701:CiteSeerX
1477:1432-0541
1438:0097-5397
1391:0004-5411
1350:0004-5411
1306:0001-0782
1257:0004-5411
1016:identical
991:ϵ
914:unrelated
883:ϵ
843:−
835:⋅
829:≥
826:ϵ
707:identical
692:machines.
690:unrelated
669:ϵ
552:identical
531:identical
494:∑
481:unrelated
390:∑
339:∑
326:identical
259:∑
220:∑
103:uniformly
1858:Lateness
1848:Makespan
1832:Job shop
1773:problems
1530:11377808
1485:12965369
1265:18693114
1149:ordering
1018:machines
798:, where
77:makespan
30:) is an
1399:9739129
1171:dynamic
1123:> 2.
1022:uniform
910:maximum
754:uniform
750:maximum
736:maximum
720:(LPT).
703:maximum
592:uniform
574:uniform
377:uniform
306:average
203:average
199:maximum
64:, ...,
1729:
1721:
1703:
1674:
1637:
1600:
1563:
1528:
1518:
1483:
1475:
1436:
1397:
1389:
1348:
1304:
1263:
1255:
1167:static
1133:Kovacz
730:Exact
564:Exact
1727:S2CID
1526:S2CID
1481:S2CID
1395:S2CID
1261:S2CID
1037:(for
906:FPTAS
548:Sahni
50:jobs
1719:ISSN
1672:ISBN
1635:ISBN
1598:ISBN
1561:ISBN
1516:ISBN
1473:ISSN
1434:ISSN
1387:ISSN
1346:ISSN
1302:ISSN
1253:ISSN
1188:and
1082:)).
371:log
320:log
312:The
38:and
1711:doi
1664:doi
1627:doi
1590:doi
1553:doi
1508:doi
1465:doi
1426:doi
1377:doi
1336:doi
1292:doi
1243:doi
572:on
485:R||
432:max
381:Q||
373:m n
330:P||
250:Q||
211:Q||
172:max
158:Q||
128:i,j
124:is
94:i,j
87:i,j
34:in
26:or
1906::
1725:.
1717:.
1709:.
1697:31
1695:.
1670:.
1633:.
1596:.
1559:.
1524:.
1514:.
1502:.
1479:.
1471:.
1461:39
1459:.
1455:.
1432:.
1422:17
1420:.
1416:.
1393:.
1385:.
1373:34
1371:.
1367:.
1344:.
1332:23
1330:.
1326:.
1314:^
1300:.
1288:17
1286:.
1282:.
1259:.
1251:.
1239:23
1237:.
1233:.
1215:^
1192:.
1184:,
962:=
931:10
839:10
771:10
713:.
640:=
609:10
544:.
291:.
145:.
138:/
131:=
57:,
1763:e
1756:t
1749:v
1733:.
1713::
1680:.
1666::
1643:.
1629::
1606:.
1592::
1569:.
1555::
1532:.
1510::
1487:.
1467::
1440:.
1428::
1401:.
1379::
1352:.
1338::
1308:.
1294::
1267:.
1245::
1121:c
1079:i
1077:C
1075:(
1073:f
1069:f
1064:i
1062:C
1060:(
1058:f
1053:i
1051:C
1047:i
1043:m
1039:i
1034:i
1032:C
994:)
987:/
981:2
977:n
973:(
970:O
950:)
945:2
941:n
935:l
927:(
924:O
892:)
887:2
878:/
874:n
871:(
868:O
846:l
832:2
806:l
786:)
783:n
778:l
775:2
767:(
764:O
746:ε
672:)
665:/
659:2
655:n
651:(
648:O
628:)
623:2
619:n
613:l
605:(
602:O
584:ε
537:.
516:.
502:i
498:C
467:)
464:)
459:3
455:n
451:,
446:2
442:n
438:m
435:(
429:(
426:O
412:.
398:i
394:C
369:n
361:.
347:i
343:C
322:n
318:n
277:i
273:C
267:i
263:w
228:i
224:C
207:n
192:P
168:C
154:Q
142:i
140:s
135:j
133:p
126:p
122:i
118:j
113:i
111:s
107:i
92:p
85:p
81:i
73:m
68:n
66:J
62:2
59:J
55:1
52:J
48:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.