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