|
FPTAS
A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value is at least 1-\epsilon times the correct value, and at most 1 + \epsilon times the correct value. 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 assuming that the problem possesses self reducibility. Importantly, the run-time of an FPTAS is polynomial in the problem size and in 1/ε. This is in contrast to a general polynomial-time approximation scheme (PTAS). The run-time of a general PTAS is polynomial in the problem size for each specific ε, but might be exponent ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Knapsack Problem
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision-makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively. The knapsack problem has been studied for more than a century, with early works dating as far back as 1897. The name "knapsack problem" dates back to the early works of the mathematician Tobias Dantzig (1884–1956), and refers to the commonplace problem of packing the most valuable or useful items without overloading the luggage. Applications Knapsack problems ap ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Multiple Subset Sum
The multiple subset sum problem is an optimization problem in computer science and operations research. It is a generalization of the subset sum problem. The input to the problem is a multiset S of ''n'' integers and a positive integer ''m'' representing the number of subsets. The goal is to construct, from the input integers, some ''m'' subsets. The problem has several variants: * ''Max-sum MSSP'': for each subset ''j'' in 1,...,''m'', there is a capacity ''Cj''. The goal is to make the ''sum'' of all subsets as large as possible, such that the sum in each subset j is at most ''Cj''. * ''Max-min MSSP'' (also called ''bottleneck MSSP'' or ''BMSSP''): again each subset has a capacity, but now the goal is to make the ''smallest'' subset sum as large as possible. * ''Fair SSP'': the subsets have no fixed capacities, but each subset belongs to a different person. The utility of each person is the sum of items in his/her subsets. The goal is to construct subsets that satisfy a given crite ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial-time Approximation Scheme
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an instance of an optimization problem and a parameter and produces a solution that is within a factor of being optimal (or for maximization problems). For example, for the Euclidean traveling salesman problem, a PTAS would produce a tour with length at most , with being the length of the shortest tour. The running time of a PTAS is required to be polynomial in the problem size for every fixed ε, but can be different for different ε. Thus an algorithm running in time or even counts as a PTAS. Variants Deterministic A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is . One way of addressing this is to define the efficient polynomial-time a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Uniform-machines Scheduling
Uniform machine scheduling (also called uniformly-related machine scheduling or related machine scheduling) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We are given ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' of varying processing times, which need to be scheduled on ''m'' different machines. The goal is to minimize the makespan - the total time required to execute the schedule. The time that machine ''i'' needs in order to process job j is denoted by ''pi,j''. In the general case, the times ''pi,j'' are unrelated, and any matrix of positive processing times is possible. In the specific variant called ''uniform machine scheduling'', some machines are ''uniformly'' faster than others. This means that, for each machine ''i'', there is a speed factor ''si'', and the run-time of job ''j'' on machine ''i'' is ''pi,j'' = ''pj'' / ''si''. In the standard three-field notation for optimal job scheduling problems, the uniform-m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Subset Sum Problem
The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum T, and the question is to decide whether any subset of the integers sum to precisely T''.'' The problem is known to be NP. Moreover, some restricted variants of it are NP-complete too, for example: * The variant in which all inputs are positive. * The variant in which inputs may be positive or negative, and T=0. For example, given the set \, the answer is ''yes'' because the subset \ sums to zero. * The variant in which all inputs are positive, and the target sum is exactly half the sum of all inputs, i.e., T = \frac(a_1+\dots+a_n) . This special case of SSP is known as the partition problem. SSP can also be regarded as an optimization problem: find a subset whose sum is at most ''T'', and subject to that, as close as possible to ''T''. It is NP-hard, but there are several algorithms that can solve it reasonably quickly in pra ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Strongly NP-complete
In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness. A general computational problem may have numerical parameters. For example, the input to the bin packing problem is a list of objects of specific sizes and a size for the bins that must contain the objects—these object sizes and bin size are numerical parameters. A problem is said to be strongly NP-complete (NP-complete in the strong sense), if it remains NP-complete even when all of its numerical parameters are bounded by a polynomial in the length of the input. A problem is said to be strongly NP-hard if a strongly NP-complete problem has a polynomial reduction to it; in combinatorial optimization, particularly, the phrase "strongly NP-hard" is reserved for problems that are not known to have a polynomial reduction to another strongly NP-complete problem. Normally numerical parameters to a problem are given in positional notation, so a problem ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
List Of Knapsack Problems
The knapsack problem is one of the most studied problems in combinatorial optimization, with many real-life applications. For this reason, many special cases and generalizations have been examined. Common to all versions are a set of ''n'' items, with each item 1 \leq j \leq n having an associated profit ''pj'' and weight ''wj''. The binary decision variable ''xj'' is used to select the item. The objective is to pick some of the items, with maximal total profit, while obeying that the maximum total weight of the chosen items must not exceed ''W''. Generally, these coefficients are scaled to become integers, and they are almost always assumed to be positive. The knapsack problem in its most basic form: __TOC__ Direct generalizations One common variant is that each item can be chosen multiple times. The bounded knapsack problem specifies, for each item ''j'', an upper bound ''uj'' (which may be a positive integer, or infinity) on the number of times item ''j'' can be selected: T ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Multiway Number Partitioning
In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in the context of the Identical-machines scheduling problem. The problem is parametrized by a positive integer ''k'', and called ''k''-way number partitioning. The input to the problem is a multiset ''S'' of numbers (usually integers), whose sum is ''k*T''. The associated decision problem is to decide whether ''S'' can be partitioned into ''k'' subsets such that the sum of each subset is exactly ''T''. There is also an optimization problem: find a partition of ''S'' into ''k'' subsets, such that the ''k'' sums are "as near as possible". The exact optimization objective can be defined in several ways: * Minimize the difference between the largest sum and the smallest sum. This objective is common in papers about multiway number partitioning, a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Identical-machines Scheduling
Identical-machines scheduling is an optimization problem in computer science and operations research. We are given ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' of varying processing times, which need to be scheduled on ''m'' identical machines, such that a certain objective function is optimized, for example, the makespan is minimized. Identical machine scheduling is a special case of uniform machine scheduling, which is itself a special case of optimal job scheduling. In the general case, the processing time of each job may be different on different machines; in the case of identical machine scheduling, the processing time of each job is the same on each machine. Therefore, identical machine scheduling is equivalent to multiway number partitioning. A special case of identical machine scheduling is single-machine scheduling. In the standard three-field notation for optimal job scheduling problems, the identical-machines variant is denoted by P in the first field. For example, " P, , ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Unrelated-machines Scheduling
Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' on ''m'' different machines, such that a certain objective function is optimized (usually, the makespan should be minimized). The time that machine ''i'' needs in order to process job j is denoted by ''pi,j''. The term ''unrelated'' emphasizes that there is no relation between values of ''pi,j'' for different ''i'' and ''j''. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which ''pi,j'' = ''pi'' / ''sj'' (where ''sj'' is the speed of machine ''j''), and identical-machines scheduling - in which ''pi,j'' = ''pi'' (the same run-time on all machines). In the standard three-field notation for optimal job scheduling problems, the unrelated-machines variant is denoted by R in the first field. For example, the problem denoted by " R, , C_\max" i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can perform automated deductions (referred to as automated reasoning) and use mathematical and logical tests to divert the code execution through various routes (referred to as automated decision-making). Using human characteristics as descriptors of machines in metaphorical ways was already practiced by Alan Turing with terms such as "memory", "search" and "stimulus". In contrast, a Heuristic (computer science), heuristic is an approach to problem solving that may not be fully specified or may not guarantee correct or optimal results, especially in problem domains where there is no well-defined correct or optimal result. As an effective method, an algorithm ca ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Edge Cover
In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time. Definition Formally, an edge cover of a graph ''G'' is a set of edges ''C'' such that each vertex in ''G'' is incident with at least one edge in ''C''. The set ''C'' is said to ''cover'' the vertices of ''G''. The following figure shows examples of edge coverings in two graphs (the set ''C'' is marked with red). : A minimum edge covering is an edge covering of smallest possible size. The edge covering number \rho(G) is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings (again, the set ''C'' is marked with red). : Note that the figure on the right is not only an edge ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
