98:
In the context of optimization problems, the correct value is understood to be the value of the optimal solution, and it is often implied that an FPTAS should produce a valid solution (and not just the value of the solution). Returning a value and finding a solution with that value are equivalent
4498:). But it violates Condition 1 above: quasi-dominance is not preserved by transition functions . So the theorem cannot be used. Indeed, this problem does not have an FPTAS unless P=NP. The same is true for the two-dimensional knapsack problem. The same is true for the
489:: instead of keeping all possible states in each step, keep only a subset of the states; remove states that are "sufficiently close" to other states. Under certain conditions, this trimming can be done in a way that does not change the objective value by too much.
1482:
4460:
5063:
elements, so this is an FPTAS. Note that this particular sum can be represented by another sum in which only O(log(ε)) elements are needed, so the sum can actually be approximated in polynomial time in the encoding length of ε.
1375:
656:
1282:
1607:
4976:
4321:
2728:
5061:
4913:
1946:
3019:) > 0. so the above theorem cannot be applied. Indeed, the problem does not have an FPTAS unless P=NP, since an FPTAS could be used to decide in polytime whether the optimal value is 0.
1214:
2662:
5027:
3197:
4730:
4621:
4578:
3107:
719:
3056:
1387:
93:
67:
1790:
2192:
1993:
1510:
4797:), so the second technical condition is violated. The state-trimming technique is not useful, but another technique - input-rounding - has been used to design an FPTAS.
4771:
4687:
4654:
4341:
3140:
2912:
2882:
2852:
1165:
4208:. The initial state-set is {(0,0)}. The degree vector is (1,1). The dominance relation is trivial. The quasi-dominance relation compares only the weight coordinate:
4923:
A different kind of problem in which FPTAS may be useful is finding rational numbers that approximate some real numbers. For example, consider the infinite series
4824:
136:
optimization problem with a polynomially bounded objective function cannot have an FPTAS unless P=NP. However, the converse fails: e.g. if P does not equal NP,
290:
270:
226:
206:
454:
The run-time of the DP is linear in the number of possible states. In general, this number can be exponential in the size of the input problem: it can be in O(
4462:. We could solve it using a similar DP, where each state is (current weight 1, current weight 2, value). The quasi-dominance relation should be modified to:
4254:
does not have a corresponding successor). A similar algorithm was presented earlier by Ibarra and Kim. The run-time of this FPTAS can be improved to
5818:. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 132. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 76:1–76:14.
1289:
547:
5454:"A "Pseudopolynomial" Algorithm for Sequencing Jobs to Minimize Total Tardiness**Research supported by National Science Foundation Grant GJ-43227X"
6286:
6145:
5955:
5703:
3966:
For every benevolent problem, the dynamic program can be converted into an FPTAS similarly to the one above, with two changes (boldfaced):
107:
1223:
43:. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value which is at least
5169:
Jansen, Thomas (1998), "Introduction to the Theory of
Complexity and Approximation Algorithms", in Mayr, Ernst W.; Prömel, Hans Jürgen;
1515:
5568:
5384:
6432:
5843:
5252:
5190:
4785:(the maximum input size). The same is true for a DP for economic lot-sizing. In these cases, the number of transition functions in
4540:
2. Minimizing the weighted number of tardy jobs, or maximizing the weighted number of early jobs, on a single machine; denoted 1||
3112:
4. Sum of completion time on any fixed number of identical or uniform machines, with time-dependent processing times: Qm|time-dep|
110:(PTAS). The run-time of a general PTAS is polynomial in the problem size for each specific ε, but might be exponential in 1/ε.
5292:"When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?"
5743:
4926:
113:
The term FPTAS may also be used to refer to the class of problems that have an FPTAS. FPTAS is a subset of PTAS, and unless
4257:
2809:
2746:
1384:
is the polynomial from condition 3 (an upper bound on the ln of every value that can appear in a state vector). Note that
4915:, which violates Condition 2, so the theorem cannot be used. But different techniques have been used to design an FPTAS.
2667:
2742:
6437:
2805:
5032:
3023:
2. Sum of cubed job completion time on any fixed number of identical or uniform machines - the latter denoted by Qm||
106:
Importantly, the run-time of an FPTAS is polynomial in the problem size and in 1/ε. This is in contrast to a general
4829:
3069:
3. Sum of weighted completion time on any fixed number of identical or uniform machines - the latter denoted by Qm||
1870:
1172:
6124:
Gopalan, Parikshit; Klivans, Adam; Meka, Raghu; Štefankovic, Daniel; Vempala, Santosh; Vigoda, Eric (2011-10-01).
3234:
maps a pair (state,input) to a
Boolean value. The value should be "true" if and only if activating the transition
137:
126:
2616:
6210:"Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications"
4773:, the dynamic programming formulation of Lawler requires to update all states in the old state space some
475:
5677:
4993:
5112:
3152:
1477:{\displaystyle L\leq \left\lceil \left(1+{\frac {2Gn}{\epsilon }}\right)P_{1}(n,\log {X})\right\rceil }
6170:
6076:
6019:
5980:
5868:
5453:
5452:
Lawler, Eugene L. (1977-01-01), Hammer, P. L.; Johnson, E. L.; Korte, B. H.; Nemhauser, G. L. (eds.),
5157:
Complexity and
Approximation: Combinatorial optimization problems and their approximability properties
6362:
Doerr, Benjamin; Eremeev, Anton; Neumann, Frank; Theile, Madeleine; Thyssen, Christian (2011-10-07).
4695:
4586:
4543:
3072:
672:
148:
133:
40:
5291:
3026:
1144:
For every extremely-benevolent problem, the dynamic program can be converted into an FPTAS. Define:
72:
46:
5681:
5673:
4499:
4455:{\displaystyle \left(\sum _{k\in K}w_{1,k}\right)^{2}+\left(\sum _{k\in K}w_{2,k}\right)^{2}\leq W}
4334:, where each item has two weights and a value, and the goal is to maximize the value such that the
1630:
152:
140:
is not strongly NP-hard, but has no FPTAS even when the optimal objective is polynomially bounded.
5735:
2738:
Here are some examples of extremely-benevolent problems, that have an FPTAS by the above theorem.
6375:
6344:
6292:
6264:
6237:
6151:
6057:
6031:
5961:
5933:
5906:
5880:
5849:
5819:
5796:
5564:"Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems"
5409:
5360:
5101:
2169:
1970:
1487:
4746:
4662:
4629:
3115:
2887:
2857:
2827:
878:
is a polynomial with non-negative coefficients. Convert it to a polynomial of a single variable
5635:
5485:
1150:
6395:
6336:
6282:
6229:
6190:
6141:
6106:
6049:
6000:
5951:
5898:
5839:
5788:
5749:
5739:
5699:
5685:
5655:
5616:
5544:
5505:
5401:
5379:
5352:
5311:
5248:
5186:
4979:
2246:
in the original (untrimmed) DP. The main lemma for proving the correctness of the FPTAS is:
1095:
100:
5197:
5138:
The "benevolent dynamic programs", that admit an FPTAS, also admit an evolutionary algorithm.
6385:
6328:
6274:
6256:
6221:
6182:
6133:
6096:
6088:
6041:
5992:
5943:
5890:
5829:
5780:
5727:
5691:
5647:
5608:
5577:
5536:
5497:
5461:
5434:
5393:
5342:
5303:
5223:
5178:
5074:
4165:=2: each state encodes (current weight, current value). There are two transition functions:
4154:
3149:
5. Weighted earliness-tardiness about a common due-date on any fixed number of machines: m||
36:
5713:
231:
All components of the input vectors are encoded in binary. So the size of the problem is O(
5709:
5170:
5115:: finding a minimum-cost path between two nodes in a graph, subject to a delay constraint.
114:
6125:
5784:
5728:
5155:
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi.
4803:
5636:"An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine"
4740:
Despite the generality of the above result, there are cases in which it cannot be used.
4150:
Here are some examples of benevolent problems, that have an FPTAS by the above theorem.
492:
To formalize this, we assume that the problem at hand has a non-negative integer vector
3257:
2796:= {(0,...,0)}. The conditions for extreme-benevolence are satisfied with degree-vector
2143:
The run-time of the FPTAS is polynomial in the total number of possible states in each
908:
275:
255:
211:
191:
6186:
5596:
5524:
5465:
2929:
between the two part sums. The same DP can be used, but this time with value function
6426:
5965:
5853:
5768:
5690:, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin,
5612:
5540:
3249:
2749:) with the goal of minimizing the largest sum is extremely-benevolent. Here, we have
6348:
6296:
6241:
5800:
5364:
4186:
verifies that the weight with the next input item is at most the knapsack capacity;
6417:
6155:
6061:
5910:
5769:"Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem"
5413:
163:
The scheme handles optimization problems in which the input is defined as follows:
4238:, then the transition functions are allowed to not preserve the proximity between
3391:
if it satisfies the following conditions (which extend conditions 1, 2, 3 above):
6263:, Proceedings, Society for Industrial and Applied Mathematics, pp. 341–348,
5834:
5212:"On Fixed-Parameter Tractability and Approximability of NP Optimization Problems"
5947:
5581:
6278:
6261:
Proceedings of the 2014 Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA)
6092:
5996:
5307:
3207:
Simple dynamic programs add to the above formulation the following components:
6390:
6363:
6332:
6225:
6045:
5981:"Implementing an efficient fptas for the 0–1 multi-objective knapsack problem"
5894:
5695:
5177:, Lecture Notes in Computer Science, vol. 1367, Springer, pp. 5–28,
5122:
4982:. To approximate it by a rational number, we can compute the sum of the first
4583:
3. Batch scheduling for minimizing the weighted number of tardy jobs: 1|batch|
3066:=3, d=(1,1,3). It can be extended to any fixed power of the completion time.
1370:{\displaystyle L:=\left\lceil {\frac {P_{1}(n,\log(X))}{\ln(r)}}\right\rceil }
817:
A sufficient condition for this can be checked as follows. For every function
651:{\displaystyle r^{-d_{j}}\cdot s_{1,j}\leq s_{2,j}\leq r^{d_{j}}\cdot s_{1,j}}
248:
It is assumed that the problem has a dynamic-programming (DP) algorithm using
6399:
6340:
6233:
6194:
6110:
6053:
6004:
5902:
5792:
5659:
5620:
5548:
5509:
5428:
5405:
5356:
5315:
6316:
6209:
5753:
2757:= the number of bins (which is considered fixed). Each state is a vector of
32:
5460:, Studies in Integer Programming, vol. 1, Elsevier, pp. 331–342,
5331:"Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems"
5228:
5211:
1833:)) singleton intervals - an interval for each possible value of coordinate
6077:"A strongly polynomial FPTAS for the symmetric quadratic knapsack problem"
5651:
5501:
5347:
5330:
6137:
5525:"A fully polynomial approximation scheme for the total tardiness problem"
5397:
5438:
4536:), but it is not preserved by transitions, by the same example as above.
6101:
5597:"Minimization of agreeably weighted variance in single machine systems"
5182:
5932:. Lecture Notes in Computer Science. Vol. 12755. pp. 79–95.
4179:
corresponds to not adding it. The corresponding filter functions are:
5979:
Bazgan, Cristina; Hugot, Hadrien; Vanderpooten, Daniel (2009-10-01).
5875:. Combinatorial Algorithms, Dedicated to the Memory of Mirka Miller.
4626:
4. Makespan of deteriorating jobs on a single machine: 1|deteriorate|
314:. Each state encodes a partial solution to the problem, using inputs
17:
6036:
5938:
5885:
5824:
5430:
Faster fully polynomial approximation schemes for
Knapsack problems
2812:
whenever the number of machines is fixed (this is required because
2420:. Since proximity is preserved by transitions (Condition 1 above),
1616:, every integer that can appear in a state-vector is in the range .
1277:{\displaystyle {\frac {1}{\ln {r}}}\leq 1+{\frac {2Gn}{\epsilon }}}
6380:
6269:
6130:
2011 IEEE 52nd Annual
Symposium on Foundations of Computer Science
5086:
Multi-dimensional knapsack problem with Delta-modular constraints.
3252:
on states (no indifferences, not all pairs are comparable), and a
1602:{\displaystyle r^{L}=e^{\ln {r}}\cdot L\geq e^{P_{1}(n,\log {x})}}
5563:
5484:
Florian, M.; Lenstra, J. K.; Rinnooy Kan, A. H. G. (1980-07-01).
5104:) - finding the number of distinct subsets with a sum of at most
4161:=2: each input is a 2-vector (weight, value). There is a DP with
4323:
operations on integers. The exponent was later improved to 2.5.
4076:
is the filter function corresponding to the transition function
3364:
is the filter function corresponding to the transition function
478:, since it is exponential in the problem size which is in O(log
3802:
The quasi-dominance relation can be decided in polynomial time.
5486:"Deterministic Production Planning: Algorithms and Complexity"
151:
presented a general scheme for converting a certain class of
3260:
on states (indifferences allowed, all pairs are comparable).
5175:
1847:
Note that every possible state is contained in exactly one
5128:
Vector subset search problem where the dimension is fixed.
5924:
Gribanov, D. V. (2021-05-10). "An FPTAS for the $ $ \var
2001:
The FPTAS runs similarly to the DP, but in each step, it
890:=(1,...,1). If the degree of the resulting polynomial in
5930:
5433:(Thesis thesis). Massachusetts Institute of Technology.
4990:. One can show that the error in approximation is about
1072:
of initial states can be computed in time polynomial in
239:)), where X is the sum of all components in all vectors.
6255:
Lin, Chengyu; Liu, Jingcheng; Lu, Pinyan (2013-12-18),
6208:
Tsaggouris, George; Zaroliagis, Christos (2009-06-01).
6169:
Ergun, Funda; Sinha, Rakesh; Zhang, Lisa (2002-09-15).
4971:{\displaystyle \sum _{i=1}^{\infty }{\frac {1}{i^{3}}}}
2730:. A similar argument works for a minimization problem.
2593:. Since proximity is preserved by the value function,
1090:
be the set of all values that can appear in coordinate
6126:"An FPTAS for #Knapsack and Related Counting Problems"
4316:{\displaystyle O(n\log {1/\epsilon }+1/\epsilon ^{4})}
2562:, which corresponds to the optimal solution (that is,
1484:, so it is polynomial in the size of the input and in
462:
is the largest integer than can appear in a state. If
365:
An objective function g, mapping a state to its value.
5380:"Fast Approximation Algorithms for Knapsack Problems"
5035:
4996:
4929:
4832:
4806:
4749:
4698:
4665:
4632:
4589:
4546:
4344:
4260:
3155:
3118:
3075:
3029:
2890:
2860:
2830:
2670:
2619:
2172:
1973:
1873:
1633:
1518:
1490:
1390:
1292:
1226:
1175:
1153:
1016:
A sufficient condition for this is that the function
675:
550:
278:
258:
214:
194:
75:
49:
4692:
6. Total weighted late work on a single machine: 1||
6315:Kel’manov, A. V.; Romanchenko, S. M. (2014-07-01).
6018:Holzhauser, Michael; Krumke, Sven O. (2017-10-01).
5869:"A faster FPTAS for the Unbounded Knapsack Problem"
5687:
Geometric algorithms and combinatorial optimization
2723:{\displaystyle g(t^{*})\geq (1-\epsilon )\cdot OPT}
5562:van Hoesel, C. P. M.; Wagelmans, A. P. M. (2001).
5055:
5021:
4970:
4907:
4818:
4765:
4724:
4681:
4648:
4615:
4572:
4454:
4315:
3396:Proximity is preserved by the transition functions
3191:
3134:
3101:
3050:
2906:
2876:
2846:
2722:
2656:
2186:
1987:
1940:
1784:
1601:
1504:
1476:
1369:
1276:
1208:
1159:
733:Proximity is preserved by the transition functions
713:
650:
284:
264:
220:
200:
87:
61:
29:fully polynomial-time approximation scheme (FPTAS)
6364:"Evolutionary algorithms and dynamic programming"
5928:$ $ -Modular Multidimensional Knapsack Problem".
5867:Jansen, Klaus; Kraft, Stefan E. J. (2018-02-01).
5029:. Therefore, to get an error of ε, we need about
4502:problem: the quasi-dominance relation should be:
2331:,1)-close to itself. Suppose the lemma holds for
6171:"An improved FPTAS for Restricted Shortest Path"
4633:
2891:
2861:
2831:
2388:. By the induction assumption, there is a state
728:if it satisfies the following three conditions:
5767:Kellerer, Hans; Pferschy, Ulrich (2004-03-01).
5056:{\displaystyle {\sqrt {\frac {1}{2\epsilon }}}}
4172:corresponds to adding the next input item, and
2609:) for a maximization problem. By definition of
917:≥ 0 (which is a function of the value function
129:with respect to the standard parameterization.
6020:"An FPTAS for the parametric knapsack problem"
5268:H. Kellerer; U. Pferschy; D. Pisinger (2004).
5196:. See discussion following Definition 1.30 on
4908:{\displaystyle g(s)=s_{5}-(s_{4}-s_{3})^{2}/n}
1967:is polynomial in the size of the input and in
1941:{\displaystyle R:=(L+1+P_{2}(n,\log {X}))^{b}}
6321:Journal of Applied and Industrial Mathematics
6317:"An FPTAS for a vector subset search problem"
5329:Ibarra, Oscar H.; Kim, Chul E. (1975-10-01).
3606:Proximity is preserved by the value function:
2951:). Now, condition 2 is violated: the states (
2773:represents inserting the next input into bin
2570:)=OPT). By the lemma above, there is a state
1209:{\displaystyle r:=1+{\frac {\epsilon }{2Gn}}}
292:is independent of the input. The DP works in
8:
4230:. The implication of this is that, if state
1220:is the constant from condition 2. Note that
4800:2. In the variance minimization problem 1||
4659:5. Total late work on a single machine: 1||
4113:that quasi-dominates all other elements in
1844:is the polynomial from condition 3 above).
1054:| of transition functions is polynomial in
2012:, that contains exactly one state in each
1167: := the required approximation ratio.
1024:variables) with non-negative coefficients.
6389:
6379:
6268:
6257:"A Simple FPTAS for Counting Edge Covers"
6100:
6035:
5937:
5884:
5833:
5823:
5346:
5227:
5118:Shortest paths and non-linear objectives.
5036:
5034:
5010:
4997:
4995:
4960:
4951:
4945:
4934:
4928:
4897:
4891:
4881:
4868:
4852:
4831:
4805:
4757:
4748:
4716:
4706:
4697:
4673:
4664:
4640:
4631:
4607:
4597:
4588:
4564:
4554:
4545:
4440:
4423:
4407:
4388:
4371:
4355:
4343:
4304:
4295:
4280:
4276:
4259:
4104:-box that contains one or more states of
3241:on this pair would lead to a valid state.
3184:
3178:
3169:
3163:
3154:
3126:
3117:
3093:
3083:
3074:
3042:
3037:
3028:
2898:
2889:
2868:
2859:
2838:
2829:
2681:
2669:
2657:{\displaystyle r^{-Gn}\geq (1-\epsilon )}
2624:
2618:
2176:
2171:
2113:-box that contains one or more states of
1977:
1972:
1932:
1920:
1899:
1872:
1814:+1 intervals above; each coordinate with
1773:
1754:
1738:
1716:
1694:
1663:
1638:
1632:
1589:
1568:
1563:
1543:
1536:
1523:
1517:
1494:
1489:
1461:
1440:
1413:
1389:
1310:
1303:
1291:
1256:
1239:
1227:
1225:
1188:
1174:
1152:
699:
680:
674:
636:
621:
616:
597:
578:
563:
555:
549:
362:maps a pair (state,input) to a new state.
277:
257:
213:
193:
74:
48:
6081:European Journal of Operational Research
5985:European Journal of Operational Research
5601:European Journal of Operational Research
4193:always returns True. The value function
3264:The original DP is modified as follows:
144:Converting a dynamic program to an FPTAS
5216:Journal of Computer and System Sciences
5210:Cai, Liming; Chen, Jianer (June 1997).
5148:
2496:. After the trimming, there is a state
2150:, which is at most the total number of
5068:Some other problems that have an FPTAS
3612:≥ 0 (a function of the value function
2925:=2, where the goal is to minimize the
2761:integers representing the sums of the
863:can be seen as an integer function in
514:of the problem. For every real number
252:. Each state is a vector made of some
5773:Journal of Combinatorial Optimization
5095:Symmetric quadratic knapsack problem.
5089:Multi-objective 0-1 knapsack problem.
4743:1. In the total tardiness problem 1||
3624:>1, and for any two state-vectors
2016:-box. The algorithm of the FPTAS is:
929:>1, and for any two state-vectors
518:>1, we say that two state-vectors
69:times the correct value, and at most
35:for finding approximate solutions to
7:
5634:Woeginger, Gerhard J. (1999-05-01).
5290:Woeginger, Gerhard J. (2000-02-01).
5285:
5283:
5281:
5279:
4919:FPTAS for approximating real numbers
1851:-box; if two states are in the same
485:The way to make it polynomial is to
121:Relation to other complexity classes
108:polynomial-time approximation scheme
99:assuming that the problem possesses
5247:. Berlin: Springer. Corollary 8.6.
5077:, as well as some of its variants:
5022:{\displaystyle {\frac {1}{2k^{2}}}}
4338:is at most the knapsack capacity:
4336:sum of squares of the total weights
4246:(it is possible, for example, that
3402:>1, for any transition function
3275: := the set of initial states.
871:variables. Suppose that every such
739:>1, for any transition function
380: := the set of initial states.
5816:An Improved FPTAS for 0-1 Knapsack
5785:10.1023/B:JOCO.0000021934.29833.6b
5569:Mathematics of Operations Research
5385:Mathematics of Operations Research
4946:
4793:, which is exponential in the log(
3808:Conditions on the filter functions
2753:= 1 (the inputs are integers) and
188:Each input vector is made of some
25:
5873:European Journal of Combinatorics
3192:{\displaystyle \sum w_{j}|C_{j}|}
2005:the state set into a smaller set
307:, and constructs a set of states
5378:Lawler, Eugene L. (1979-11-01).
3826:, and for any two state-vectors
3414:, and for any two state-vectors
901:, then condition 1 is satisfied.
751:, and for any two state-vectors
328:. The components of the DP are:
244:Extremely-simple dynamic program
4725:{\displaystyle \sum w_{j}V_{j}}
4616:{\displaystyle \sum w_{j}U_{j}}
4573:{\displaystyle \sum w_{j}U_{j}}
4234:has a higher weight than state
3814:>1, for any filter function
3769:) (in minimization problems);
3704:) (in minimization problems);
3102:{\displaystyle \sum w_{j}C_{j}}
2785:) picks the largest element of
1795:Partition the state space into
987:) (in minimization problems);
714:{\displaystyle s_{1,j}=s_{2,j}}
6175:Information Processing Letters
6024:Information Processing Letters
5458:Annals of Discrete Mathematics
4888:
4861:
4842:
4836:
4310:
4264:
3185:
3170:
3051:{\displaystyle \sum C_{j}^{3}}
2705:
2693:
2687:
2674:
2651:
2639:
2356:be one of its predecessors in
1929:
1925:
1905:
1880:
1779:
1747:
1722:
1703:
1684:
1672:
1653:
1647:
1594:
1574:
1466:
1446:
1357:
1351:
1340:
1337:
1331:
1316:
1013:) (in maximization problems).
907:Proximity is preserved by the
88:{\displaystyle 1+\varepsilon }
62:{\displaystyle 1-\varepsilon }
1:
6187:10.1016/S0020-0190(02)00205-3
5734:. Berlin: Springer. pp.
5466:10.1016/S0167-5060(08)70742-8
4826:, the objective function is
4157:is benevolent. Here, we have
3791:) (in maximization problems).
3730:) (in maximization problems).
3219:, of the same cardinality as
2810:Unrelated-machines scheduling
2747:Identical-machines scheduling
2305:The proof is by induction on
1785:{\displaystyle I_{0}=;I_{1}=}
1047:can be evaluated in polytime.
1020:is a polynomial function (of
470:), then the run-time is in O(
272:non-negative integers, where
208:non-negative integers, where
138:knapsack with two constraints
6368:Theoretical Computer Science
5835:10.4230/LIPIcs.ICALP.2019.76
5640:INFORMS Journal on Computing
5613:10.1016/0377-2217(93)E0367-7
5541:10.1016/0167-6377(82)90022-0
5523:Lawler, E. L. (1982-12-01).
5296:INFORMS Journal on Computing
5092:Parametric knapsack problem.
4134:Output min/max {g(s) | s in
3984:= the set of initial states.
3799:(in addition to the above):
3376:Output min/max {g(s) | s in
2921:: consider the special case
2743:Multiway number partitioning
2218:contains at least one state
2132:Output min/max {g(s) | s in
2120:, keep exactly one state in
2034:= the set of initial states.
1810:≥ 1 is partitioned into the
443:Output min/max {g(s) | s in
369:The algorithm of the DP is:
6214:Theory of Computing Systems
5948:10.1007/978-3-030-77876-7_6
5582:10.1287/moor.26.2.339.10552
5529:Operations Research Letters
5243:Vazirani, Vijay V. (2003).
5083:Unbounded knapsack problem.
4332:2-weighted knapsack problem
4093: := a trimmed copy of
2820:-boxes - is exponential in
2806:Uniform-machines scheduling
2187:{\displaystyle 1/\epsilon }
2102: := a trimmed copy of
1988:{\displaystyle 1/\epsilon }
1505:{\displaystyle 1/\epsilon }
833:, and for every coordinate
6454:
6279:10.1137/1.9781611973402.25
6093:10.1016/j.ejor.2011.10.049
5997:10.1016/j.ejor.2008.07.047
5308:10.1287/ijoc.12.1.57.11901
5272:. Springer. Theorem 9.4.1.
4986:elements, for some finite
4766:{\displaystyle \sum T_{j}}
4682:{\displaystyle \sum V_{j}}
4649:{\displaystyle \max C_{j}}
4111:, choose a single element
3135:{\displaystyle \sum C_{j}}
2907:{\displaystyle \max C_{j}}
2877:{\displaystyle \max C_{j}}
2847:{\displaystyle \max C_{j}}
2804:=1. The result extends to
2197:Note that, for each state
1963:is a fixed constant, this
1619:Partition the range into
943:, the following holds: if
765:, the following holds: if
125:All problems in FPTAS are
6391:10.1016/j.tcs.2011.07.024
6333:10.1134/S1990478914030041
6226:10.1007/s00224-007-9096-4
6046:10.1016/j.ipl.2017.06.006
5895:10.1016/j.ejc.2017.07.016
5696:10.1007/978-3-642-78240-4
2769:functions: each function
2158:, which is polynomial in
2154:-boxes, which is at most
1821:= 0 is partitioned into P
1160:{\displaystyle \epsilon }
1126:is at most a polynomial P
1105:is at most a polynomial P
1035:All transition functions
300:, it processes the input
127:fixed-parameter tractable
117:, it is a strict subset.
95:times the correct value.
6433:Approximation algorithms
5730:Approximation algorithms
5726:Vazirani, Vijay (2001).
5245:Approximation Algorithms
5159:, Springer-Verlag, 1999.
3608:There exists an integer
3254:quasi-dominance relation
3146:sum of completion time.
3058:- is ex-benevolent with
2927:square of the difference
1951:Note that the number of
913:There exists an integer
536:if, for each coordinate
228:may depend on the input.
6075:Xu, Zhou (2012-04-16).
3840:, the following holds:
3822:, for any input-vector
3638:, the following holds:
3428:, the following holds:
3410:, for any input-vector
2551:Consider now the state
2225:that is (d,r)-close to
1119:=0, the cardinality of
1043:and the value function
747:, for any input-vector
5595:Cai, X. (1995-09-21).
5229:10.1006/jcss.1997.1490
5057:
5023:
4972:
4950:
4909:
4820:
4767:
4726:
4683:
4650:
4617:
4574:
4456:
4317:
3616:and the degree vector
3203:Simple dynamic program
3193:
3142:. This holds even for
3136:
3103:
3052:
2908:
2878:
2848:
2724:
2658:
2303:
2188:
1989:
1942:
1786:
1609:, so by definition of
1603:
1506:
1478:
1371:
1278:
1210:
1161:
1094:in a state. Then, the
921:and the degree vector
715:
652:
476:pseudo-polynomial time
286:
266:
222:
202:
89:
63:
5652:10.1287/ijoc.11.2.211
5502:10.1287/mnsc.26.7.669
5427:Rhee, Donguk (2015).
5348:10.1145/321906.321909
5080:0-1 knapsack problem.
5058:
5024:
4973:
4930:
4910:
4821:
4768:
4727:
4684:
4651:
4618:
4575:
4457:
4318:
3620:), such that for any
3194:
3137:
3104:
3053:
2909:
2879:
2849:
2725:
2659:
2248:
2189:
1990:
1943:
1855:-box, then they are (
1787:
1604:
1507:
1479:
1372:
1279:
1211:
1162:
925:), such that for any
716:
653:
352:transition functions.
287:
267:
223:
203:
167:The input is made of
90:
64:
41:optimization problems
6138:10.1109/FOCS.2011.32
6132:. pp. 817–826.
5682:Schrijver, Alexander
5398:10.1287/moor.4.4.339
5033:
4994:
4927:
4830:
4804:
4747:
4696:
4663:
4630:
4587:
4544:
4342:
4258:
4250:has a successor and
3797:Technical conditions
3387:A problem is called
3153:
3116:
3073:
3027:
2888:
2858:
2828:
2668:
2617:
2335:-1. For every state
2170:
1971:
1871:
1631:
1516:
1488:
1388:
1290:
1224:
1173:
1151:
1030:Technical conditions
726:extremely-benevolent
724:A problem is called
673:
548:
487:trim the state-space
296:steps. At each step
276:
256:
212:
192:
73:
47:
5100:Count-subset-sum (#
4819:{\displaystyle CTV}
4781:is of the order of
4500:multiple subset sum
4122:and insert it into
3217:filtering functions
3047:
2272:, there is a state
2239:is a subset of the
658:(in particular, if
6438:Complexity classes
5490:Management Science
5335:Journal of the ACM
5183:10.1007/BFb0053011
5053:
5019:
4968:
4905:
4816:
4763:
4722:
4679:
4646:
4613:
4570:
4452:
4418:
4366:
4330:: consider In the
4313:
3515:) quasi-dominates
3468:, then either (a)
3246:dominance relation
3189:
3132:
3099:
3048:
3033:
2904:
2874:
2844:
2720:
2654:
2327:; every state is (
2258:, for every state
2184:
1985:
1955:-boxes is at most
1938:
1799:: each coordinate
1782:
1599:
1502:
1474:
1367:
1274:
1206:
1157:
1098:of every value in
882:, by substituting
852:-th coordinate of
711:
648:
282:
262:
218:
198:
85:
59:
6374:(43): 6020–6035.
6288:978-1-61197-338-9
6147:978-0-7695-4571-4
5957:978-3-030-77875-0
5705:978-3-642-78242-8
5674:Grötschel, Martin
5270:Knapsack Problems
5051:
5050:
5017:
4980:irrational number
4966:
4403:
4351:
1429:
1361:
1272:
1245:
1204:
474:), which is only
285:{\displaystyle b}
265:{\displaystyle b}
221:{\displaystyle a}
201:{\displaystyle a}
101:self reducibility
37:function problems
16:(Redirected from
6445:
6416:Complexity Zoo:
6404:
6403:
6393:
6383:
6359:
6353:
6352:
6312:
6306:
6305:
6304:
6303:
6272:
6252:
6246:
6245:
6205:
6199:
6198:
6166:
6160:
6159:
6121:
6115:
6114:
6104:
6072:
6066:
6065:
6039:
6015:
6009:
6008:
5976:
5970:
5969:
5941:
5921:
5915:
5914:
5888:
5864:
5858:
5857:
5837:
5827:
5814:Jin, Ce (2019).
5811:
5805:
5804:
5764:
5758:
5757:
5733:
5723:
5717:
5716:
5670:
5664:
5663:
5631:
5625:
5624:
5592:
5586:
5585:
5559:
5553:
5552:
5520:
5514:
5513:
5481:
5475:
5474:
5473:
5472:
5449:
5443:
5442:
5424:
5418:
5417:
5375:
5369:
5368:
5350:
5326:
5320:
5319:
5287:
5274:
5273:
5265:
5259:
5258:
5240:
5234:
5233:
5231:
5207:
5201:
5195:
5171:Steger, Angelika
5166:
5160:
5153:
5075:knapsack problem
5062:
5060:
5059:
5054:
5052:
5049:
5038:
5037:
5028:
5026:
5025:
5020:
5018:
5016:
5015:
5014:
4998:
4978:. The sum is an
4977:
4975:
4974:
4969:
4967:
4965:
4964:
4952:
4949:
4944:
4914:
4912:
4911:
4906:
4901:
4896:
4895:
4886:
4885:
4873:
4872:
4857:
4856:
4825:
4823:
4822:
4817:
4772:
4770:
4769:
4764:
4762:
4761:
4731:
4729:
4728:
4723:
4721:
4720:
4711:
4710:
4688:
4686:
4685:
4680:
4678:
4677:
4655:
4653:
4652:
4647:
4645:
4644:
4622:
4620:
4619:
4614:
4612:
4611:
4602:
4601:
4579:
4577:
4576:
4571:
4569:
4568:
4559:
4558:
4506:quasi-dominates
4466:quasi-dominates
4461:
4459:
4458:
4453:
4445:
4444:
4439:
4435:
4434:
4433:
4417:
4393:
4392:
4387:
4383:
4382:
4381:
4365:
4322:
4320:
4319:
4314:
4309:
4308:
4299:
4288:
4284:
4212:quasi-dominates
4155:knapsack problem
3872:quasi-dominates
3667:quasi-dominates
3460:quasi-dominates
3223:. Each function
3198:
3196:
3195:
3190:
3188:
3183:
3182:
3173:
3168:
3167:
3141:
3139:
3138:
3133:
3131:
3130:
3108:
3106:
3105:
3100:
3098:
3097:
3088:
3087:
3057:
3055:
3054:
3049:
3046:
3041:
2913:
2911:
2910:
2905:
2903:
2902:
2883:
2881:
2880:
2875:
2873:
2872:
2853:
2851:
2850:
2845:
2843:
2842:
2816:- the number of
2765:bins. There are
2729:
2727:
2726:
2721:
2686:
2685:
2663:
2661:
2660:
2655:
2635:
2634:
2193:
2191:
2190:
2185:
2180:
1994:
1992:
1991:
1986:
1981:
1947:
1945:
1944:
1939:
1937:
1936:
1924:
1904:
1903:
1791:
1789:
1788:
1783:
1778:
1777:
1765:
1764:
1743:
1742:
1721:
1720:
1699:
1698:
1668:
1667:
1643:
1642:
1608:
1606:
1605:
1600:
1598:
1597:
1593:
1573:
1572:
1549:
1548:
1547:
1528:
1527:
1511:
1509:
1508:
1503:
1498:
1483:
1481:
1480:
1475:
1473:
1469:
1465:
1445:
1444:
1435:
1431:
1430:
1425:
1414:
1376:
1374:
1373:
1368:
1366:
1362:
1360:
1343:
1315:
1314:
1304:
1283:
1281:
1280:
1275:
1273:
1268:
1257:
1246:
1244:
1243:
1228:
1215:
1213:
1212:
1207:
1205:
1203:
1189:
1166:
1164:
1163:
1158:
720:
718:
717:
712:
710:
709:
691:
690:
657:
655:
654:
649:
647:
646:
628:
627:
626:
625:
608:
607:
589:
588:
570:
569:
568:
567:
291:
289:
288:
283:
271:
269:
268:
263:
227:
225:
224:
219:
207:
205:
204:
199:
153:dynamic programs
134:strongly NP-hard
94:
92:
91:
86:
68:
66:
65:
60:
21:
6453:
6452:
6448:
6447:
6446:
6444:
6443:
6442:
6423:
6422:
6413:
6408:
6407:
6361:
6360:
6356:
6314:
6313:
6309:
6301:
6299:
6289:
6254:
6253:
6249:
6207:
6206:
6202:
6168:
6167:
6163:
6148:
6123:
6122:
6118:
6074:
6073:
6069:
6017:
6016:
6012:
5978:
5977:
5973:
5958:
5923:
5922:
5918:
5866:
5865:
5861:
5846:
5813:
5812:
5808:
5766:
5765:
5761:
5746:
5725:
5724:
5720:
5706:
5672:
5671:
5667:
5633:
5632:
5628:
5594:
5593:
5589:
5561:
5560:
5556:
5522:
5521:
5517:
5483:
5482:
5478:
5470:
5468:
5451:
5450:
5446:
5426:
5425:
5421:
5377:
5376:
5372:
5328:
5327:
5323:
5289:
5288:
5277:
5267:
5266:
5262:
5255:
5242:
5241:
5237:
5209:
5208:
5204:
5193:
5168:
5167:
5163:
5154:
5150:
5145:
5135:
5070:
5042:
5031:
5030:
5006:
5002:
4992:
4991:
4956:
4925:
4924:
4921:
4887:
4877:
4864:
4848:
4828:
4827:
4802:
4801:
4753:
4745:
4744:
4738:
4712:
4702:
4694:
4693:
4669:
4661:
4660:
4636:
4628:
4627:
4603:
4593:
4585:
4584:
4560:
4550:
4542:
4541:
4535:
4529:
4522:
4516:
4497:
4490:
4483:
4476:
4419:
4402:
4398:
4397:
4367:
4350:
4346:
4345:
4340:
4339:
4300:
4256:
4255:
4229:
4222:
4207:
4192:
4185:
4178:
4171:
4148:
4139:
4128:
4118:
4109:
4098:
4091:
4081:
4074:
4065:
4054:
4047:
4043:
4028:
4021:
4010:
4004:
3983:
3976:
3955:
3940:
3928:
3922:
3906:
3891:
3877:
3871:
3860:
3850:
3839:
3832:
3789:
3779:
3767:
3757:
3745:
3739:
3728:
3714:
3702:
3688:
3672:
3666:
3658:
3648:
3637:
3630:
3597:
3583:
3571:
3565:
3553:
3539:
3524:
3510:
3497:
3479:
3465:
3459:
3448:
3438:
3427:
3420:
3381:
3369:
3362:
3353:
3342:
3335:
3331:
3316:
3309:
3298:
3292:
3274:
3239:
3228:
3205:
3174:
3159:
3151:
3150:
3122:
3114:
3113:
3089:
3079:
3071:
3070:
3025:
3024:
3018:
3011:
3000:
2993:
2978:
2971:
2964:
2957:
2950:
2943:
2894:
2886:
2885:
2864:
2856:
2855:
2834:
2826:
2825:
2824:). Denoted Pm||
2800:=(1,...,1) and
2795:
2777:. The function
2745:(equivalently,
2736:
2677:
2666:
2665:
2620:
2615:
2614:
2579:
2560:
2546:
2531:
2523:
2508:
2501:
2494:
2484:
2480:
2469:
2459:
2455:
2433:
2429:
2419:
2415:
2400:
2393:
2386:
2376:
2372:
2361:
2354:
2347:
2340:
2325:
2318:
2299:
2284:
2277:
2270:
2263:
2250:For every step
2244:
2237:
2230:
2223:
2216:
2209:
2202:
2168:
2167:
2148:
2137:
2126:
2118:
2107:
2100:
2091:
2087:
2068:
2053:
2033:
2026:
2010:
1969:
1968:
1928:
1895:
1869:
1868:
1843:
1824:
1819:
1808:
1769:
1750:
1734:
1712:
1690:
1659:
1634:
1629:
1628:
1615:
1564:
1559:
1532:
1519:
1514:
1513:
1486:
1485:
1436:
1415:
1406:
1402:
1401:
1397:
1386:
1385:
1383:
1344:
1306:
1305:
1299:
1288:
1287:
1258:
1232:
1222:
1221:
1193:
1171:
1170:
1149:
1148:
1129:
1124:
1117:
1108:
1103:
1088:
1071:
1011:
997:
985:
971:
959:
949:
942:
935:
899:
886:=(z,...,z) and
876:
861:
846:
811:
793:
781:
771:
764:
757:
695:
676:
671:
670:
663:
632:
617:
612:
593:
574:
559:
551:
546:
545:
531:
524:
508:
502:
448:
437:
433:
414:
399:
379:
338:
326:
320:
312:
305:
274:
273:
254:
253:
246:
210:
209:
190:
189:
183:
177:
161:
146:
123:
71:
70:
45:
44:
23:
22:
15:
12:
11:
5:
6451:
6449:
6441:
6440:
6435:
6425:
6424:
6421:
6420:
6412:
6411:External links
6409:
6406:
6405:
6354:
6327:(3): 329–336.
6307:
6287:
6247:
6220:(1): 162–186.
6200:
6181:(5): 287–291.
6161:
6146:
6116:
6087:(2): 377–381.
6067:
6010:
5971:
5956:
5916:
5859:
5844:
5806:
5759:
5744:
5718:
5704:
5678:Lovász, László
5665:
5646:(2): 211–216.
5626:
5607:(3): 576–592.
5587:
5576:(2): 339–357.
5554:
5535:(6): 207–208.
5515:
5496:(7): 669–679.
5476:
5444:
5419:
5392:(4): 339–356.
5370:
5341:(4): 463–468.
5321:
5275:
5260:
5253:
5235:
5222:(3): 465–474.
5202:
5191:
5161:
5147:
5146:
5144:
5141:
5140:
5139:
5134:
5131:
5130:
5129:
5126:
5119:
5116:
5109:
5098:
5097:
5096:
5093:
5090:
5087:
5084:
5081:
5069:
5066:
5048:
5045:
5041:
5013:
5009:
5005:
5001:
4963:
4959:
4955:
4948:
4943:
4940:
4937:
4933:
4920:
4917:
4904:
4900:
4894:
4890:
4884:
4880:
4876:
4871:
4867:
4863:
4860:
4855:
4851:
4847:
4844:
4841:
4838:
4835:
4815:
4812:
4809:
4760:
4756:
4752:
4737:
4734:
4719:
4715:
4709:
4705:
4701:
4676:
4672:
4668:
4643:
4639:
4635:
4610:
4606:
4600:
4596:
4592:
4567:
4563:
4557:
4553:
4549:
4538:
4537:
4533:
4527:
4520:
4514:
4495:
4488:
4481:
4474:
4451:
4448:
4443:
4438:
4432:
4429:
4426:
4422:
4416:
4413:
4410:
4406:
4401:
4396:
4391:
4386:
4380:
4377:
4374:
4370:
4364:
4361:
4358:
4354:
4349:
4312:
4307:
4303:
4298:
4294:
4291:
4287:
4283:
4279:
4275:
4272:
4269:
4266:
4263:
4227:
4220:
4205:
4190:
4183:
4176:
4169:
4147:
4144:
4143:
4142:
4137:
4132:
4131:
4130:
4126:
4116:
4107:
4096:
4089:
4084:
4079:
4072:
4063:
4052:
4045:
4041:
4026:
4019:
4008:
4002:
3985:
3981:
3974:
3964:
3963:
3962:
3961:
3953:
3938:
3926:
3920:
3914:
3904:
3889:
3875:
3869:
3858:
3848:
3837:
3830:
3805:
3804:
3803:
3794:
3793:
3792:
3787:
3777:
3765:
3755:
3743:
3737:
3731:
3726:
3712:
3700:
3686:
3670:
3664:
3656:
3646:
3635:
3628:
3603:
3602:
3601:
3595:
3581:
3569:
3563:
3557:
3551:
3537:
3522:
3508:
3495:
3477:
3463:
3457:
3446:
3436:
3425:
3418:
3385:
3384:
3379:
3374:
3373:
3372:
3367:
3360:
3351:
3340:
3333:
3329:
3314:
3307:
3296:
3290:
3276:
3272:
3262:
3261:
3258:total preorder
3242:
3237:
3226:
3204:
3201:
3187:
3181:
3177:
3172:
3166:
3162:
3158:
3129:
3125:
3121:
3096:
3092:
3086:
3082:
3078:
3045:
3040:
3036:
3032:
3021:
3020:
3016:
3009:
2998:
2991:
2976:
2969:
2962:
2955:
2948:
2941:
2901:
2897:
2893:
2871:
2867:
2863:
2841:
2837:
2833:
2793:
2735:
2732:
2719:
2716:
2713:
2710:
2707:
2704:
2701:
2698:
2695:
2692:
2689:
2684:
2680:
2676:
2673:
2653:
2650:
2647:
2644:
2641:
2638:
2633:
2630:
2627:
2623:
2577:
2558:
2544:
2529:
2521:
2506:
2499:
2492:
2482:
2478:
2467:
2457:
2453:
2431:
2427:
2417:
2413:
2398:
2391:
2384:
2374:
2370:
2359:
2352:
2345:
2338:
2323:
2316:
2297:
2282:
2275:
2268:
2261:
2242:
2235:
2228:
2221:
2214:
2207:
2200:
2183:
2179:
2175:
2146:
2141:
2140:
2135:
2130:
2129:
2128:
2124:
2116:
2105:
2098:
2093:
2089:
2085:
2066:
2051:
2035:
2031:
2024:
2008:
1999:
1998:
1997:
1996:
1984:
1980:
1976:
1935:
1931:
1927:
1923:
1919:
1916:
1913:
1910:
1907:
1902:
1898:
1894:
1891:
1888:
1885:
1882:
1879:
1876:
1866:
1865:
1864:
1841:
1822:
1817:
1806:
1793:
1781:
1776:
1772:
1768:
1763:
1760:
1757:
1753:
1749:
1746:
1741:
1737:
1733:
1730:
1727:
1724:
1719:
1715:
1711:
1708:
1705:
1702:
1697:
1693:
1689:
1686:
1683:
1680:
1677:
1674:
1671:
1666:
1662:
1658:
1655:
1652:
1649:
1646:
1641:
1637:
1617:
1613:
1596:
1592:
1588:
1585:
1582:
1579:
1576:
1571:
1567:
1562:
1558:
1555:
1552:
1546:
1542:
1539:
1535:
1531:
1526:
1522:
1501:
1497:
1493:
1472:
1468:
1464:
1460:
1457:
1454:
1451:
1448:
1443:
1439:
1434:
1428:
1424:
1421:
1418:
1412:
1409:
1405:
1400:
1396:
1393:
1381:
1365:
1359:
1356:
1353:
1350:
1347:
1342:
1339:
1336:
1333:
1330:
1327:
1324:
1321:
1318:
1313:
1309:
1302:
1298:
1295:
1285:
1271:
1267:
1264:
1261:
1255:
1252:
1249:
1242:
1238:
1235:
1231:
1202:
1199:
1196:
1192:
1187:
1184:
1181:
1178:
1168:
1156:
1142:
1141:
1140:
1139:
1127:
1122:
1115:
1110:
1106:
1101:
1086:
1081:
1069:
1063:
1048:
1027:
1026:
1025:
1009:
995:
983:
969:
957:
947:
940:
933:
909:value function
904:
903:
902:
897:
874:
859:
844:
809:
791:
779:
769:
762:
755:
708:
705:
702:
698:
694:
689:
686:
683:
679:
661:
645:
642:
639:
635:
631:
624:
620:
615:
611:
606:
603:
600:
596:
592:
587:
584:
581:
577:
573:
566:
562:
558:
554:
529:
522:
510:), called the
506:
500:
452:
451:
446:
441:
440:
439:
435:
431:
412:
397:
381:
377:
367:
366:
363:
354:Each function
344:
341:initial states
336:
324:
318:
310:
303:
281:
261:
245:
242:
241:
240:
229:
217:
197:
186:
181:
175:
160:
157:
145:
142:
122:
119:
84:
81:
78:
58:
55:
52:
24:
14:
13:
10:
9:
6:
4:
3:
2:
6450:
6439:
6436:
6434:
6431:
6430:
6428:
6419:
6415:
6414:
6410:
6401:
6397:
6392:
6387:
6382:
6377:
6373:
6369:
6365:
6358:
6355:
6350:
6346:
6342:
6338:
6334:
6330:
6326:
6322:
6318:
6311:
6308:
6298:
6294:
6290:
6284:
6280:
6276:
6271:
6266:
6262:
6258:
6251:
6248:
6243:
6239:
6235:
6231:
6227:
6223:
6219:
6215:
6211:
6204:
6201:
6196:
6192:
6188:
6184:
6180:
6176:
6172:
6165:
6162:
6157:
6153:
6149:
6143:
6139:
6135:
6131:
6127:
6120:
6117:
6112:
6108:
6103:
6098:
6094:
6090:
6086:
6082:
6078:
6071:
6068:
6063:
6059:
6055:
6051:
6047:
6043:
6038:
6033:
6029:
6025:
6021:
6014:
6011:
6006:
6002:
5998:
5994:
5990:
5986:
5982:
5975:
5972:
5967:
5963:
5959:
5953:
5949:
5945:
5940:
5935:
5931:
5927:
5920:
5917:
5912:
5908:
5904:
5900:
5896:
5892:
5887:
5882:
5878:
5874:
5870:
5863:
5860:
5855:
5851:
5847:
5845:9783959771092
5841:
5836:
5831:
5826:
5821:
5817:
5810:
5807:
5802:
5798:
5794:
5790:
5786:
5782:
5778:
5774:
5770:
5763:
5760:
5755:
5751:
5747:
5741:
5737:
5732:
5731:
5722:
5719:
5715:
5711:
5707:
5701:
5697:
5693:
5689:
5688:
5683:
5679:
5675:
5669:
5666:
5661:
5657:
5653:
5649:
5645:
5641:
5637:
5630:
5627:
5622:
5618:
5614:
5610:
5606:
5602:
5598:
5591:
5588:
5583:
5579:
5575:
5571:
5570:
5565:
5558:
5555:
5550:
5546:
5542:
5538:
5534:
5530:
5526:
5519:
5516:
5511:
5507:
5503:
5499:
5495:
5491:
5487:
5480:
5477:
5467:
5463:
5459:
5455:
5448:
5445:
5440:
5436:
5432:
5431:
5423:
5420:
5415:
5411:
5407:
5403:
5399:
5395:
5391:
5387:
5386:
5381:
5374:
5371:
5366:
5362:
5358:
5354:
5349:
5344:
5340:
5336:
5332:
5325:
5322:
5317:
5313:
5309:
5305:
5301:
5297:
5293:
5286:
5284:
5282:
5280:
5276:
5271:
5264:
5261:
5256:
5254:3-540-65367-8
5250:
5246:
5239:
5236:
5230:
5225:
5221:
5217:
5213:
5206:
5203:
5199:
5194:
5192:9783540642015
5188:
5184:
5180:
5176:
5172:
5165:
5162:
5158:
5152:
5149:
5142:
5137:
5136:
5132:
5127:
5124:
5120:
5117:
5114:
5113:shortest path
5110:
5107:
5103:
5099:
5094:
5091:
5088:
5085:
5082:
5079:
5078:
5076:
5072:
5071:
5067:
5065:
5046:
5043:
5039:
5011:
5007:
5003:
4999:
4989:
4985:
4981:
4961:
4957:
4953:
4941:
4938:
4935:
4931:
4918:
4916:
4902:
4898:
4892:
4882:
4878:
4874:
4869:
4865:
4858:
4853:
4849:
4845:
4839:
4833:
4813:
4810:
4807:
4798:
4796:
4792:
4788:
4784:
4780:
4777:times, where
4776:
4758:
4754:
4750:
4741:
4735:
4733:
4717:
4713:
4707:
4703:
4699:
4690:
4674:
4670:
4666:
4657:
4641:
4637:
4624:
4608:
4604:
4598:
4594:
4590:
4581:
4565:
4561:
4555:
4551:
4547:
4532:
4526:
4519:
4513:
4509:
4505:
4501:
4494:
4487:
4480:
4473:
4469:
4465:
4449:
4446:
4441:
4436:
4430:
4427:
4424:
4420:
4414:
4411:
4408:
4404:
4399:
4394:
4389:
4384:
4378:
4375:
4372:
4368:
4362:
4359:
4356:
4352:
4347:
4337:
4333:
4329:
4326:
4325:
4324:
4305:
4301:
4296:
4292:
4289:
4285:
4281:
4277:
4273:
4270:
4267:
4261:
4253:
4249:
4245:
4241:
4237:
4233:
4226:
4219:
4215:
4211:
4204:
4200:
4196:
4189:
4182:
4175:
4168:
4164:
4160:
4156:
4151:
4145:
4140:
4133:
4125:
4121:
4119:
4110:
4103:
4099:
4092:
4085:
4082:
4075:
4068:
4066:
4059:
4055:
4044:
4037:
4033:
4029:
4022:
4015:
4011:
4001:
3997:
3996:
3994:
3990:
3986:
3980:
3973:
3969:
3968:
3967:
3959:
3952:
3948:
3944:
3937:
3933:
3929:
3919:
3915:
3912:
3910:
3903:
3899:
3895:
3888:
3884:
3879:
3878:
3868:
3863:
3861:
3854:
3847:
3842:
3841:
3836:
3829:
3825:
3821:
3817:
3813:
3809:
3806:
3801:
3800:
3798:
3795:
3790:
3783:
3776:
3772:
3768:
3761:
3754:
3750:
3746:
3736:
3732:
3729:
3722:
3718:
3711:
3707:
3703:
3696:
3692:
3685:
3681:
3677:
3674:
3673:
3663:
3659:
3652:
3645:
3640:
3639:
3634:
3627:
3623:
3619:
3615:
3611:
3607:
3604:
3599:
3591:
3587:
3580:
3576:
3572:
3562:
3558:
3555:
3547:
3543:
3536:
3532:
3528:
3526:
3518:
3514:
3507:
3503:
3499:
3491:
3487:
3483:
3476:
3472:
3467:
3466:
3456:
3451:
3449:
3442:
3435:
3430:
3429:
3424:
3417:
3413:
3409:
3405:
3401:
3397:
3394:
3393:
3392:
3390:
3382:
3375:
3370:
3363:
3356:
3354:
3347:
3343:
3332:
3325:
3321:
3317:
3310:
3303:
3299:
3288:
3287:
3285:
3281:
3277:
3271:
3267:
3266:
3265:
3259:
3255:
3251:
3250:partial order
3248:, which is a
3247:
3243:
3240:
3233:
3229:
3222:
3218:
3214:
3210:
3209:
3208:
3202:
3200:
3179:
3175:
3164:
3160:
3156:
3147:
3145:
3127:
3123:
3119:
3110:
3094:
3090:
3084:
3080:
3076:
3067:
3065:
3061:
3043:
3038:
3034:
3030:
3015:
3008:
3004:
2997:
2990:
2986:
2983:)-close, but
2982:
2975:
2968:
2961:
2954:
2947:
2940:
2936:
2932:
2928:
2924:
2920:
2917:
2916:
2915:
2899:
2895:
2869:
2865:
2839:
2835:
2823:
2819:
2815:
2811:
2807:
2803:
2799:
2792:
2788:
2784:
2780:
2776:
2772:
2768:
2764:
2760:
2756:
2752:
2748:
2744:
2739:
2733:
2731:
2717:
2714:
2711:
2708:
2702:
2699:
2696:
2690:
2682:
2678:
2671:
2648:
2645:
2642:
2636:
2631:
2628:
2625:
2621:
2612:
2608:
2604:
2600:
2596:
2592:
2588:
2584:
2580:
2573:
2569:
2565:
2561:
2554:
2549:
2547:
2540:
2536:
2532:
2525:
2517:
2513:
2509:
2502:
2495:
2488:
2481:
2474:
2470:
2463:
2456:
2449:
2445:
2441:
2437:
2430:
2423:
2416:
2409:
2405:
2401:
2394:
2387:
2380:
2373:
2366:
2362:
2355:
2348:
2341:
2334:
2330:
2326:
2319:
2312:
2308:
2302:
2300:
2293:
2289:
2285:
2278:
2271:
2264:
2257:
2253:
2247:
2245:
2238:
2232:. Also, each
2231:
2224:
2217:
2211:, its subset
2210:
2203:
2195:
2181:
2177:
2173:
2165:
2161:
2157:
2153:
2149:
2138:
2131:
2123:
2119:
2112:
2108:
2101:
2094:
2088:
2081:
2077:
2073:
2069:
2062:
2058:
2054:
2047:
2046:
2044:
2040:
2036:
2030:
2023:
2019:
2018:
2017:
2015:
2011:
2004:
1982:
1978:
1974:
1966:
1962:
1958:
1954:
1950:
1949:
1933:
1921:
1917:
1914:
1911:
1908:
1900:
1896:
1892:
1889:
1886:
1883:
1877:
1874:
1867:
1862:
1858:
1854:
1850:
1846:
1845:
1840:
1836:
1832:
1828:
1820:
1813:
1809:
1802:
1798:
1794:
1774:
1770:
1766:
1761:
1758:
1755:
1751:
1744:
1739:
1735:
1731:
1728:
1725:
1717:
1713:
1709:
1706:
1700:
1695:
1691:
1687:
1681:
1678:
1675:
1669:
1664:
1660:
1656:
1650:
1644:
1639:
1635:
1626:
1622:
1618:
1612:
1590:
1586:
1583:
1580:
1577:
1569:
1565:
1560:
1556:
1553:
1550:
1544:
1540:
1537:
1533:
1529:
1524:
1520:
1499:
1495:
1491:
1470:
1462:
1458:
1455:
1452:
1449:
1441:
1437:
1432:
1426:
1422:
1419:
1416:
1410:
1407:
1403:
1398:
1394:
1391:
1380:
1363:
1354:
1348:
1345:
1334:
1328:
1325:
1322:
1319:
1311:
1307:
1300:
1296:
1293:
1286:
1269:
1265:
1262:
1259:
1253:
1250:
1247:
1240:
1236:
1233:
1229:
1219:
1200:
1197:
1194:
1190:
1185:
1182:
1179:
1176:
1169:
1154:
1147:
1146:
1145:
1137:
1133:
1125:
1118:
1111:
1104:
1097:
1093:
1089:
1082:
1079:
1075:
1068:
1064:
1061:
1057:
1053:
1049:
1046:
1042:
1038:
1034:
1033:
1031:
1028:
1023:
1019:
1015:
1014:
1012:
1005:
1001:
994:
990:
986:
979:
975:
968:
964:
960:
953:
946:
939:
932:
928:
924:
920:
916:
912:
910:
905:
900:
893:
889:
885:
881:
877:
870:
866:
862:
855:
851:
847:
840:
836:
832:
828:
824:
820:
816:
815:
813:
805:
801:
797:
790:
786:
782:
775:
768:
761:
754:
750:
746:
742:
738:
734:
731:
730:
729:
727:
722:
706:
703:
700:
696:
692:
687:
684:
681:
677:
668:
664:
643:
640:
637:
633:
629:
622:
618:
613:
609:
604:
601:
598:
594:
590:
585:
582:
579:
575:
571:
564:
560:
556:
552:
543:
539:
535:
528:
521:
517:
513:
512:degree vector
509:
499:
495:
490:
488:
483:
481:
477:
473:
469:
465:
461:
457:
449:
442:
434:
427:
423:
419:
415:
408:
404:
400:
393:
392:
390:
386:
382:
376:
372:
371:
370:
364:
361:
357:
353:
349:
345:
342:
335:
331:
330:
329:
327:
317:
313:
306:
299:
295:
279:
259:
251:
243:
238:
234:
230:
215:
195:
187:
184:
174:
170:
166:
165:
164:
158:
156:
155:to an FPTAS.
154:
150:
143:
141:
139:
135:
130:
128:
120:
118:
116:
111:
109:
104:
102:
96:
82:
79:
76:
56:
53:
50:
42:
39:, especially
38:
34:
30:
19:
6371:
6367:
6357:
6324:
6320:
6310:
6300:, retrieved
6260:
6250:
6217:
6213:
6203:
6178:
6174:
6164:
6129:
6119:
6084:
6080:
6070:
6027:
6023:
6013:
5991:(1): 47–56.
5988:
5984:
5974:
5929:
5925:
5919:
5876:
5872:
5862:
5815:
5809:
5776:
5772:
5762:
5729:
5721:
5686:
5668:
5643:
5639:
5629:
5604:
5600:
5590:
5573:
5567:
5557:
5532:
5528:
5518:
5493:
5489:
5479:
5469:, retrieved
5457:
5447:
5439:1721.1/98564
5429:
5422:
5389:
5383:
5373:
5338:
5334:
5324:
5302:(1): 57–74.
5299:
5295:
5269:
5263:
5244:
5238:
5219:
5215:
5205:
5174:
5164:
5156:
5151:
5105:
4987:
4983:
4922:
4799:
4794:
4790:
4786:
4782:
4778:
4774:
4742:
4739:
4736:Non-examples
4691:
4658:
4625:
4582:
4539:
4530:
4524:
4517:
4511:
4507:
4503:
4492:
4485:
4478:
4471:
4467:
4463:
4335:
4331:
4327:
4251:
4247:
4243:
4239:
4235:
4231:
4224:
4217:
4213:
4209:
4202:
4198:
4194:
4187:
4180:
4173:
4166:
4162:
4158:
4152:
4149:
4135:
4123:
4114:
4112:
4105:
4101:
4094:
4087:
4077:
4070:
4061:
4057:
4050:
4049:
4039:
4035:
4031:
4024:
4017:
4013:
4006:
3999:
3992:
3988:
3978:
3971:
3965:
3957:
3950:
3946:
3942:
3935:
3931:
3924:
3917:
3908:
3901:
3897:
3893:
3886:
3882:
3881:
3873:
3866:
3864:
3856:
3852:
3845:
3844:
3834:
3827:
3823:
3819:
3815:
3811:
3807:
3796:
3785:
3781:
3774:
3770:
3763:
3759:
3752:
3748:
3741:
3734:
3724:
3720:
3716:
3709:
3705:
3698:
3694:
3690:
3683:
3679:
3675:
3668:
3661:
3654:
3650:
3643:
3642:
3632:
3625:
3621:
3617:
3613:
3609:
3605:
3593:
3589:
3588:) dominates
3585:
3578:
3574:
3567:
3560:
3549:
3545:
3544:) dominates
3541:
3534:
3530:
3520:
3516:
3512:
3505:
3501:
3493:
3489:
3485:
3481:
3474:
3470:
3469:
3461:
3454:
3452:
3444:
3440:
3433:
3432:
3422:
3415:
3411:
3407:
3403:
3399:
3395:
3388:
3386:
3377:
3365:
3358:
3349:
3345:
3338:
3337:
3327:
3323:
3319:
3312:
3305:
3301:
3294:
3283:
3279:
3269:
3263:
3253:
3245:
3235:
3231:
3224:
3220:
3216:
3212:
3206:
3148:
3143:
3111:
3068:
3063:
3059:
3022:
3013:
3006:
3002:
3001:) = 0 while
2995:
2988:
2984:
2980:
2973:
2966:
2959:
2952:
2945:
2938:
2934:
2930:
2926:
2922:
2918:
2821:
2817:
2813:
2801:
2797:
2790:
2786:
2782:
2778:
2774:
2770:
2766:
2762:
2758:
2754:
2750:
2740:
2737:
2610:
2606:
2602:
2598:
2594:
2590:
2586:
2582:
2581:, which is (
2575:
2571:
2567:
2563:
2556:
2552:
2550:
2542:
2538:
2534:
2527:
2519:
2515:
2511:
2504:
2497:
2490:
2486:
2476:
2472:
2465:
2461:
2451:
2447:
2443:
2439:
2435:
2425:
2421:
2411:
2407:
2403:
2396:
2389:
2382:
2378:
2368:
2364:
2357:
2350:
2343:
2336:
2332:
2328:
2321:
2314:
2310:
2306:
2304:
2295:
2291:
2287:
2280:
2273:
2266:
2259:
2255:
2251:
2249:
2240:
2233:
2226:
2219:
2212:
2205:
2198:
2196:
2163:
2159:
2155:
2151:
2144:
2142:
2133:
2121:
2114:
2110:
2103:
2096:
2083:
2079:
2075:
2071:
2064:
2060:
2056:
2049:
2042:
2038:
2028:
2021:
2013:
2006:
2002:
2000:
1964:
1960:
1956:
1952:
1860:
1856:
1852:
1848:
1838:
1834:
1830:
1826:
1815:
1811:
1804:
1803:with degree
1800:
1796:
1627:-intervals:
1624:
1620:
1610:
1378:
1217:
1143:
1135:
1131:
1120:
1113:
1099:
1091:
1084:
1077:
1073:
1066:
1059:
1055:
1051:
1050:The number |
1044:
1040:
1036:
1029:
1021:
1017:
1007:
1003:
999:
992:
988:
981:
977:
973:
966:
962:
955:
951:
944:
937:
930:
926:
922:
918:
914:
906:
895:
891:
887:
883:
879:
872:
868:
864:
857:
853:
849:
842:
841:, denote by
838:
834:
830:
826:
822:
818:
807:
803:
799:
795:
788:
784:
777:
773:
766:
759:
752:
748:
744:
740:
736:
732:
725:
723:
666:
665:=0 for some
659:
541:
537:
533:
526:
519:
515:
511:
504:
497:
493:
491:
486:
484:
479:
471:
467:
463:
459:
455:
453:
444:
429:
425:
421:
417:
410:
406:
402:
395:
388:
384:
374:
368:
359:
355:
351:
347:
340:
333:
322:
315:
308:
301:
297:
293:
249:
247:
236:
232:
179:
172:
168:
162:
147:
131:
124:
112:
105:
97:
28:
26:
6102:10397/24376
5879:: 148–174.
5779:(1): 5–11.
5123:edge-covers
5111:Restricted
4153:1. The 0-1
4100:: for each
3855:)-close to
3653:)-close to
3488:)-close to
3443:)-close to
3256:which is a
2589:)-close to
2541:)-close to
2518:)-close to
2446:)-close to
2410:)-close to
2402:, that is (
2313:=0 we have
2294:)-close to
2109:: for each
1109:(n,log(X)).
954:)-close to
894:is at most
802:)-close to
776:)-close to
534:(d,r)-close
6427:Categories
6302:2021-12-13
6037:1701.07822
5939:2103.07257
5886:1504.04650
5825:1904.09562
5745:3540653678
5471:2021-12-17
5198:p. 20
5143:References
4201:) returns
4005: := {
3923:dominates
3810:: For any
3740:dominates
3566:dominates
3398:: For any
3389:benevolent
3293: := {
2979:) may be (
2363:, so that
2055: := {
848:(s,x) the
735:: For any
401: := {
6400:0304-3975
6381:1301.4096
6341:1990-4797
6270:1309.6115
6234:1433-0490
6195:0020-0190
6111:0377-2217
6054:0020-0190
6030:: 43–47.
6005:0377-2217
5966:232222954
5903:0195-6698
5854:128317990
5793:1573-2886
5660:1091-9856
5621:0377-2217
5549:0167-6377
5510:0025-1909
5406:0364-765X
5357:0004-5411
5316:1091-9856
5121:Counting
5102:SubsetSum
5047:ϵ
4947:∞
4932:∑
4875:−
4859:−
4751:∑
4700:∑
4667:∑
4591:∑
4548:∑
4447:≤
4412:∈
4405:∑
4360:∈
4353:∑
4302:ϵ
4286:ϵ
4274:
4069:}, where
3977: :=
3529:, or (b)
3357:}, where
3157:∑
3120:∑
3077:∑
3031:∑
2709:⋅
2703:ϵ
2700:−
2691:≥
2683:∗
2649:ϵ
2646:−
2637:≥
2626:−
2510:that is (
2286:that is (
2254:in 0,...,
2182:ϵ
2027: :=
1983:ϵ
1918:
1759:−
1729:…
1587:
1557:≥
1551:⋅
1541:
1500:ϵ
1459:
1427:ϵ
1395:≤
1349:
1329:
1270:ϵ
1248:≤
1237:
1191:ϵ
1155:ϵ
837:in 1,...,
630:⋅
610:≤
591:≤
572:⋅
557:−
540:in 1,...,
458:), where
171:vectors,
149:Woeginger
83:ε
57:ε
54:−
33:algorithm
6349:96437935
6297:14598468
6242:13010023
5801:36474745
5754:47097680
5684:(1993),
5365:14619586
5173:(eds.),
5133:See also
4523:) ≤ max(
4510:iff max(
4146:Examples
3144:weighted
2734:Examples
2489:) is in
2471:. This
1959:. Since
1863:)-close.
1512:. Also,
1471:⌉
1399:⌈
1377:, where
1364:⌉
1301:⌈
1216:, where
1076:and log(
1065:The set
1058:and log(
961:, then:
466:is in O(
6156:5691574
6062:1013794
5911:9557898
5714:1261419
5414:7655435
3991:= 1 to
3930:, then
3880:, then
3747:, then
3573:, then
3500:), and
3282:= 1 to
2965:) and (
2884:or Rm||
2854:or Qm||
2597:(t*) ≥
2526:. This
2166:), and
2041:= 1 to
1837:(where
1797:r-boxes
856:. This
783:, then
669:, then
387:= 1 to
6398:
6347:
6339:
6295:
6285:
6240:
6232:
6193:
6154:
6144:
6109:
6060:
6052:
6003:
5964:
5954:
5909:
5901:
5852:
5842:
5799:
5791:
5752:
5742:
5712:
5702:
5658:
5619:
5547:
5508:
5412:
5404:
5363:
5355:
5314:
5251:
5189:
4067:)=True
3678:then:
3660:, and
3484:) is (
3355:)=True
3211:A set
2438:) is (
2349:, let
2309:. For
2162:, log(
798:) is (
346:A set
332:A set
250:states
115:P = NP
31:is an
6418:FPTAS
6376:arXiv
6345:S2CID
6293:S2CID
6265:arXiv
6238:S2CID
6152:S2CID
6058:S2CID
6032:arXiv
5962:S2CID
5934:arXiv
5926:Delta
5907:S2CID
5881:arXiv
5850:S2CID
5820:arXiv
5797:S2CID
5738:–70.
5410:S2CID
5361:S2CID
4484:) ≤ (
4470:iff (
3289:Let S
2937:) = (
2664:. So
2574:* in
2003:trims
1829:,log(
1134:,log(
829:) in
503:,...,
321:,...,
235:+log(
178:,...,
159:Input
18:FPTAS
6396:ISSN
6337:ISSN
6283:ISBN
6230:ISSN
6191:ISSN
6142:ISBN
6107:ISSN
6050:ISSN
6001:ISSN
5952:ISBN
5899:ISSN
5840:ISBN
5789:ISSN
5750:OCLC
5740:ISBN
5700:ISBN
5656:ISSN
5617:ISSN
5545:ISSN
5506:ISSN
5402:ISSN
5353:ISSN
5312:ISSN
5249:ISBN
5187:ISBN
5073:The
4328:Note
4242:and
4216:iff
4086:Let
4023:) |
3998:Let
3995:do:
3987:For
3970:Let
3945:) ≥
3896:) ≥
3865:and
3851:is (
3780:) ≥
3758:) ≤
3715:) ≥
3689:) ≤
3649:is (
3453:and
3439:is (
3311:) |
3286:do:
3278:For
3268:Let
3062:=1,
2919:Note
2808:and
2533:is (
2301:.
2095:Let
2070:) |
2048:Let
2045:do:
2037:For
2020:Let
1083:Let
998:) ≥
972:) ≤
950:is (
772:is (
532:are
416:) |
394:Let
391:do:
383:For
373:Let
132:Any
6386:doi
6372:412
6329:doi
6275:doi
6222:doi
6183:doi
6134:doi
6097:hdl
6089:doi
6085:218
6042:doi
6028:126
5993:doi
5989:198
5944:doi
5891:doi
5830:doi
5781:doi
5692:doi
5648:doi
5609:doi
5578:doi
5537:doi
5498:doi
5462:doi
5435:hdl
5394:doi
5343:doi
5304:doi
5224:doi
5179:doi
4789:is
4634:max
4271:log
4038:in
4030:in
3916:if
3853:d,r
3843:if
3818:in
3733:if
3651:d,r
3641:if
3559:if
3486:d,r
3441:d,r
3431:if
3406:in
3326:in
3318:in
3230:in
3215:of
2981:d,r
2892:max
2862:max
2832:max
2741:1.
2555:in
2524:,x)
2520:f(s
2503:in
2399:k-1
2395:in
2360:k-1
2342:in
2279:in
2265:in
2204:in
2082:in
2074:in
1915:log
1623:+1
1584:log
1456:log
1326:log
1138:)).
1112:If
1039:in
952:d,r
814:).
800:d,r
774:d,r
743:in
721:).
544::
496:= (
482:).
472:n X
456:n V
428:in
420:in
358:in
350:of
339:of
6429::
6394:.
6384:.
6370:.
6366:.
6343:.
6335:.
6323:.
6319:.
6291:,
6281:,
6273:,
6259:,
6236:.
6228:.
6218:45
6216:.
6212:.
6189:.
6179:83
6177:.
6173:.
6150:.
6140:.
6128:.
6105:.
6095:.
6083:.
6079:.
6056:.
6048:.
6040:.
6026:.
6022:.
5999:.
5987:.
5983:.
5960:.
5950:.
5942:.
5905:.
5897:.
5889:.
5877:68
5871:.
5848:.
5838:.
5828:.
5795:.
5787:.
5775:.
5771:.
5748:.
5736:69
5710:MR
5708:,
5698:,
5680:;
5676:;
5654:.
5644:11
5642:.
5638:.
5615:.
5605:85
5603:.
5599:.
5574:26
5572:.
5566:.
5543:.
5531:.
5527:.
5504:.
5494:26
5492:.
5488:.
5456:,
5408:.
5400:.
5388:.
5382:.
5359:.
5351:.
5339:22
5337:.
5333:.
5310:.
5300:12
5298:.
5294:.
5278:^
5220:54
5218:.
5214:.
5185:,
4732:.
4689:.
4656:.
4623:.
4580:.
4528:1,
4515:1,
4491:+
4477:+
4223:≤
4141:}.
4048:,
4046:−1
4034:,
3960:).
3719:·
3693:·
3600:).
3598:,x
3556:).
3554:,x
3525:,x
3498:,x
3383:}.
3336:,
3334:−1
3322:,
3244:A
3199:.
3109:.
2914:.
2789:.
2613:,
2607:s*
2601:·
2568:s*
2548:.
2522:t-
2464:)=
2392:t-
2381:)=
2353:s-
2194:.
2139:}.
2090:−1
2078:,
1948:.
1878::=
1538:ln
1346:ln
1297::=
1234:ln
1180::=
1096:ln
1080:).
1062:).
1032::
1002:·
976:·
812:,x
450:}.
436:−1
424:,
103:.
27:A
6402:.
6388::
6378::
6351:.
6331::
6325:8
6277::
6267::
6244:.
6224::
6197:.
6185::
6158:.
6136::
6113:.
6099::
6091::
6064:.
6044::
6034::
6007:.
5995::
5968:.
5946::
5936::
5913:.
5893::
5883::
5856:.
5832::
5822::
5803:.
5783::
5777:8
5756:.
5694::
5662:.
5650::
5623:.
5611::
5584:.
5580::
5551:.
5539::
5533:1
5512:.
5500::
5464::
5441:.
5437::
5416:.
5396::
5390:4
5367:.
5345::
5318:.
5306::
5257:.
5232:.
5226::
5200:.
5181::
5125:.
5108:.
5106:C
5044:2
5040:1
5012:2
5008:k
5004:2
5000:1
4988:k
4984:k
4962:3
4958:i
4954:1
4942:1
4939:=
4936:i
4903:n
4899:/
4893:2
4889:)
4883:3
4879:s
4870:4
4866:s
4862:(
4854:5
4850:s
4846:=
4843:)
4840:s
4837:(
4834:g
4814:V
4811:T
4808:C
4795:X
4791:B
4787:F
4783:X
4779:B
4775:B
4759:j
4755:T
4718:j
4714:V
4708:j
4704:w
4675:j
4671:V
4642:j
4638:C
4609:j
4605:U
4599:j
4595:w
4566:j
4562:U
4556:j
4552:w
4534:2
4531:t
4525:t
4521:2
4518:s
4512:s
4508:t
4504:s
4496:2
4493:t
4489:1
4486:t
4482:2
4479:s
4475:1
4472:s
4468:t
4464:s
4450:W
4442:2
4437:)
4431:k
4428:,
4425:2
4421:w
4415:K
4409:k
4400:(
4395:+
4390:2
4385:)
4379:k
4376:,
4373:1
4369:w
4363:K
4357:k
4348:(
4311:)
4306:4
4297:/
4293:1
4290:+
4282:/
4278:1
4268:n
4265:(
4262:O
4252:t
4248:s
4244:s
4240:t
4236:s
4232:t
4228:1
4225:t
4221:1
4218:s
4214:t
4210:s
4206:2
4203:s
4199:s
4197:(
4195:g
4191:2
4188:h
4184:1
4181:h
4177:2
4174:f
4170:1
4167:f
4163:b
4159:a
4138:n
4136:T
4129:.
4127:k
4124:T
4120:,
4117:k
4115:U
4108:k
4106:U
4102:r
4097:k
4095:U
4090:k
4088:T
4083:.
4080:j
4078:f
4073:j
4071:h
4064:k
4062:x
4060:,
4058:s
4056:(
4053:j
4051:h
4042:k
4040:T
4036:s
4032:F
4027:j
4025:f
4020:k
4018:x
4016:,
4014:s
4012:(
4009:j
4007:f
4003:k
4000:U
3993:n
3989:k
3982:0
3979:S
3975:0
3972:T
3958:x
3956:,
3954:2
3951:s
3949:(
3947:h
3943:x
3941:,
3939:1
3936:s
3934:(
3932:h
3927:2
3925:s
3921:1
3918:s
3913:.
3911:)
3909:x
3907:,
3905:2
3902:s
3900:(
3898:h
3894:x
3892:,
3890:1
3887:s
3885:(
3883:h
3876:2
3874:s
3870:1
3867:s
3862:,
3859:2
3857:s
3849:1
3846:s
3838:2
3835:s
3833:,
3831:1
3828:s
3824:x
3820:H
3816:h
3812:r
3788:2
3786:s
3784:(
3782:g
3778:1
3775:s
3773:(
3771:g
3766:2
3764:s
3762:(
3760:g
3756:1
3753:s
3751:(
3749:g
3744:2
3742:s
3738:1
3735:s
3727:2
3725:s
3723:(
3721:g
3717:r
3713:1
3710:s
3708:(
3706:g
3701:2
3699:s
3697:(
3695:g
3691:r
3687:1
3684:s
3682:(
3680:g
3676:,
3671:2
3669:s
3665:1
3662:s
3657:2
3655:s
3647:1
3644:s
3636:2
3633:s
3631:,
3629:1
3626:s
3622:r
3618:d
3614:g
3610:G
3596:2
3594:s
3592:(
3590:f
3586:x
3584:,
3582:1
3579:s
3577:(
3575:f
3570:2
3568:s
3564:1
3561:s
3552:2
3550:s
3548:(
3546:f
3542:x
3540:,
3538:1
3535:s
3533:(
3531:f
3527:)
3523:2
3521:s
3519:(
3517:f
3513:x
3511:,
3509:1
3506:s
3504:(
3502:f
3496:2
3494:s
3492:(
3490:f
3482:x
3480:,
3478:1
3475:s
3473:(
3471:f
3464:2
3462:s
3458:1
3455:s
3450:,
3447:2
3445:s
3437:1
3434:s
3426:2
3423:s
3421:,
3419:1
3416:s
3412:x
3408:F
3404:f
3400:r
3380:n
3378:S
3371:.
3368:j
3366:f
3361:j
3359:h
3352:k
3350:x
3348:,
3346:s
3344:(
3341:j
3339:h
3330:k
3328:S
3324:s
3320:F
3315:j
3313:f
3308:k
3306:x
3304:,
3302:s
3300:(
3297:j
3295:f
3291:k
3284:n
3280:k
3273:0
3270:S
3238:i
3236:f
3232:H
3227:i
3225:h
3221:F
3213:H
3186:|
3180:j
3176:C
3171:|
3165:j
3161:w
3128:j
3124:C
3095:j
3091:C
3085:j
3081:w
3064:b
3060:a
3044:3
3039:j
3035:C
3017:2
3014:s
3012:,
3010:1
3007:s
3005:(
3003:g
2999:1
2996:s
2994:,
2992:1
2989:s
2987:(
2985:g
2977:2
2974:s
2972:,
2970:1
2967:s
2963:1
2960:s
2958:,
2956:1
2953:s
2949:2
2946:s
2944:-
2942:1
2939:s
2935:s
2933:(
2931:g
2923:b
2900:j
2896:C
2870:j
2866:C
2840:j
2836:C
2822:b
2818:r
2814:R
2802:G
2798:d
2794:0
2791:S
2787:s
2783:s
2781:(
2779:g
2775:j
2771:j
2767:b
2763:b
2759:b
2755:b
2751:a
2718:T
2715:P
2712:O
2706:)
2697:1
2694:(
2688:)
2679:t
2675:(
2672:g
2652:)
2643:1
2640:(
2632:n
2629:G
2622:r
2611:r
2605:(
2603:g
2599:r
2595:g
2591:s
2587:r
2585:,
2583:d
2578:n
2576:T
2572:t
2566:(
2564:g
2559:n
2557:S
2553:s
2545:s
2543:s
2539:r
2537:,
2535:d
2530:t
2528:s
2516:r
2514:,
2512:d
2507:k
2505:T
2500:t
2498:s
2493:k
2491:U
2487:x
2485:,
2483:−
2479:t
2477:s
2475:(
2473:f
2468:s
2466:s
2462:x
2460:,
2458:−
2454:s
2452:s
2450:(
2448:f
2444:r
2442:,
2440:d
2436:x
2434:,
2432:−
2428:t
2426:s
2424:(
2422:f
2418:−
2414:s
2412:s
2408:r
2406:,
2404:d
2397:T
2390:s
2385:s
2383:s
2379:x
2377:,
2375:−
2371:s
2369:s
2367:(
2365:f
2358:S
2351:s
2346:k
2344:S
2339:s
2337:s
2333:k
2329:d
2324:k
2322:S
2320:=
2317:k
2315:T
2311:k
2307:k
2298:s
2296:s
2292:r
2290:,
2288:d
2283:k
2281:T
2276:t
2274:s
2269:k
2267:S
2262:s
2260:s
2256:n
2252:k
2243:k
2241:S
2236:k
2234:U
2229:u
2227:s
2222:t
2220:s
2215:k
2213:T
2208:k
2206:U
2201:u
2199:s
2178:/
2174:1
2164:X
2160:n
2156:R
2152:r
2147:i
2145:T
2136:n
2134:T
2127:.
2125:k
2122:T
2117:k
2115:U
2111:r
2106:k
2104:U
2099:k
2097:T
2092:}
2086:k
2084:T
2080:s
2076:F
2072:f
2067:k
2065:x
2063:,
2061:s
2059:(
2057:f
2052:k
2050:U
2043:n
2039:k
2032:0
2029:S
2025:0
2022:T
2014:r
2009:k
2007:T
1995:.
1979:/
1975:1
1965:R
1961:b
1957:R
1953:r
1934:b
1930:)
1926:)
1922:X
1912:,
1909:n
1906:(
1901:2
1897:P
1893:+
1890:1
1887:+
1884:L
1881:(
1875:R
1861:r
1859:,
1857:d
1853:r
1849:r
1842:2
1839:P
1835:k
1831:X
1827:n
1825:(
1823:2
1818:k
1816:d
1812:L
1807:k
1805:d
1801:k
1792:.
1780:]
1775:L
1771:r
1767:,
1762:1
1756:L
1752:r
1748:[
1745:=
1740:L
1736:I
1732:;
1726:;
1723:)
1718:2
1714:r
1710:,
1707:r
1704:[
1701:=
1696:2
1692:I
1688:;
1685:)
1682:r
1679:,
1676:1
1673:[
1670:=
1665:1
1661:I
1657:;
1654:]
1651:0
1648:[
1645:=
1640:0
1636:I
1625:r
1621:L
1614:1
1611:P
1595:)
1591:x
1581:,
1578:n
1575:(
1570:1
1566:P
1561:e
1554:L
1545:r
1534:e
1530:=
1525:L
1521:r
1496:/
1492:1
1467:)
1463:X
1453:,
1450:n
1447:(
1442:1
1438:P
1433:)
1423:n
1420:G
1417:2
1411:+
1408:1
1404:(
1392:L
1382:1
1379:P
1358:)
1355:r
1352:(
1341:)
1338:)
1335:X
1332:(
1323:,
1320:n
1317:(
1312:1
1308:P
1294:L
1284:.
1266:n
1263:G
1260:2
1254:+
1251:1
1241:r
1230:1
1218:G
1201:n
1198:G
1195:2
1186:+
1183:1
1177:r
1136:X
1132:n
1130:(
1128:2
1123:j
1121:V
1116:j
1114:d
1107:1
1102:j
1100:V
1092:j
1087:j
1085:V
1078:X
1074:n
1070:0
1067:S
1060:X
1056:n
1052:F
1045:g
1041:F
1037:f
1022:b
1018:g
1010:2
1008:s
1006:(
1004:g
1000:r
996:1
993:s
991:(
989:g
984:2
982:s
980:(
978:g
974:r
970:1
967:s
965:(
963:g
958:2
956:s
948:1
945:s
941:2
938:s
936:,
934:1
931:s
927:r
923:d
919:g
915:G
911::
898:j
896:d
892:z
888:x
884:s
880:z
875:j
873:f
869:a
867:+
865:b
860:j
858:f
854:f
850:j
845:j
843:f
839:b
835:j
831:F
827:x
825:,
823:s
821:(
819:f
810:2
808:s
806:(
804:f
796:x
794:,
792:1
789:s
787:(
785:f
780:2
778:s
770:1
767:s
763:2
760:s
758:,
756:1
753:s
749:x
745:F
741:f
737:r
707:j
704:,
701:2
697:s
693:=
688:j
685:,
682:1
678:s
667:j
662:j
660:d
644:j
641:,
638:1
634:s
623:j
619:d
614:r
605:j
602:,
599:2
595:s
586:j
583:,
580:1
576:s
565:j
561:d
553:r
542:b
538:j
530:2
527:s
525:,
523:1
520:s
516:r
507:b
505:d
501:1
498:d
494:d
480:X
468:X
464:V
460:V
447:n
445:S
438:}
432:k
430:S
426:s
422:F
418:f
413:k
411:x
409:,
407:s
405:(
403:f
398:k
396:S
389:n
385:k
378:0
375:S
360:F
356:f
348:F
343:.
337:0
334:S
325:i
323:x
319:1
316:x
311:i
309:S
304:i
302:x
298:i
294:n
280:b
260:b
237:X
233:n
216:a
196:a
185:.
182:n
180:x
176:1
173:x
169:n
80:+
77:1
51:1
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.