|
Partition Problem
In number theory and computer science, the partition problem, or number partitioning, is the task of deciding whether a given multiset ''S'' of positive integers can be partitioned into two subsets ''S''1 and ''S''2 such that the sum of the numbers in ''S''1 equals the sum of the numbers in ''S''2. Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest hard problem". There is an optimization version of the partition problem, which is to partition the multiset ''S'' into two subsets ''S''1, ''S''2 such that the difference between the sum of elements in ''S''1 and the sum of elements in ''S''2 is minimized. The optimization version is NP-hard, but can be solved efficiently in practice. The partition problem is a special case of two related problems: * In the subset sum problem ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Number Theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen of mathematics."German original: "Die Mathematik ist die Königin der Wissenschaften, und die Arithmetik ist die Königin der Mathematik." Number theorists study prime numbers as well as the properties of mathematical objects made out of integers (for example, rational numbers) or defined as generalizations of the integers (for example, algebraic integers). Integers can be considered either in themselves or as solutions to equations (Diophantine geometry). Questions in number theory are often best understood through the study of analytical objects (for example, the Riemann zeta function) that encode properties of the integers, primes or other number-theoretic object ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Greedy Number Partitioning
In computer science, greedy number partitioning is a class of greedy algorithms for multiway number partitioning. The input to the algorithm is a set ''S'' of numbers, and a parameter ''k''. The required output is a partition of ''S'' into ''k'' subsets, such that the sums in the subsets are as nearly equal as possible. Greedy algorithms process the numbers sequentially, and insert the next number into a bin in which the sum of numbers is currently smallest. Approximate algorithms The simplest greedy partitioning algorithm is called list scheduling. It just processes the inputs in any order they arrive. It always returns a partition in which the largest sum is at most 2-\frac times the optimal (minimum) largest sum. This heuristic can be used as an online algorithm, when the order in which the items arrive cannot be controlled. An improved greedy algorithm is called LPT scheduling. It processes the inputs by descending order of value, from large to small. Since it needs to pre-o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Anytime Algorithm
In computer science, an anytime algorithm is an algorithm that can return a valid solution to a problem even if it is interrupted before it ends. The algorithm is expected to find better and better solutions the longer it keeps running. Most algorithms run to completion: they provide a single answer after performing some fixed amount of computation. In some cases, however, the user may wish to terminate the algorithm prior to completion. The amount of computation required may be substantial, for example, and computational resources might need to be reallocated. Most algorithms either run to completion or they provide no useful solution information. Anytime algorithms, however, are able to return a partial answer, whose quality depends on the amount of computation they were able to perform. The answer generated by anytime algorithms is an approximation of the correct answer. Names An anytime algorithm may be also called an "interruptible algorithm". They are different from contract ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Significant Figures
Significant figures (also known as the significant digits, ''precision'' or ''resolution'') of a number in positional notation are digits in the number that are reliable and necessary to indicate the quantity of something. If a number expressing the result of a measurement (e.g., length, pressure, volume, or mass) has more digits than the number of digits allowed by the measurement resolution, then only as many digits as allowed by the measurement resolution are reliable, and so only these can be significant figures. For example, if a length measurement gives 114.8 mm while the smallest interval between marks on the ruler used in the measurement is 1 mm, then the first three digits (1, 1, and 4, showing 114 mm) are certain and so they are significant figures. Digits which are uncertain but ''reliable'' are also considered significant figures. In this example, the last digit (8, which adds 0.8 mm) is also considered a significant figure even though ther ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Largest Differencing Method
In computer science, the largest differencing method is an algorithm for solving the partition problem and the multiway number partitioning. It is also called the Karmarkar–Karp algorithm after its inventors, Narendra Karmarkar and Richard M. Karp. It is often abbreviated as LDM. The algorithm The input to the algorithm is a set ''S'' of numbers, and a parameter ''k''. The required output is a partition of ''S'' into ''k'' subsets, such that the sums in the subsets are as nearly equal as possible. The main steps of the algorithm are: # Order the numbers from large to small. #Replace the largest and second-largest numbers by their difference. #If two or more numbers remain, return to step 1. # Using backtracking, compute the partition. Two-way partitioning For ''k''=2, the main step (2) works as follows. * Take the two largest numbers in ''S'', remove them from ''S'', and insert their difference (this represents a decision to put each of these numbers in a different subset ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Greedy Number Partitioning
In computer science, greedy number partitioning is a class of greedy algorithms for multiway number partitioning. The input to the algorithm is a set ''S'' of numbers, and a parameter ''k''. The required output is a partition of ''S'' into ''k'' subsets, such that the sums in the subsets are as nearly equal as possible. Greedy algorithms process the numbers sequentially, and insert the next number into a bin in which the sum of numbers is currently smallest. Approximate algorithms The simplest greedy partitioning algorithm is called list scheduling. It just processes the inputs in any order they arrive. It always returns a partition in which the largest sum is at most 2-\frac times the optimal (minimum) largest sum. This heuristic can be used as an online algorithm, when the order in which the items arrive cannot be controlled. An improved greedy algorithm is called LPT scheduling. It processes the inputs by descending order of value, from large to small. Since it needs to pre-o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Depth-first Search
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph. A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes. Properties The time and space analysis of DFS differs according to its application area. In theoretical computer science, DFS is typically used to traverse an entire graph, and takes time where , V, is the number of vertices and , E, the number of edges. This is linear in the size of the graph. In these applications it also uses space O(, V, ) in the worst case to store the stack of vertices on t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Binary Tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (''L'', ''S'', ''R''), where ''L'' and ''R'' are binary trees or the empty set and ''S'' is a singleton set containing the root. Some authors allow the binary tree to be the empty set as well. From a graph theory perspective, binary (and K-ary) trees as defined here are arborescences. A binary tree may thus be also called a bifurcating arborescence—a term which appears in some very old programming books, before the modern computer science terminology prevailed. It is also possible to interpret a binary tree as an undirected, rather than a directed graph, in which case a binary tree is an ordered, rooted tree. Some authors use rooted binary tree instead of ''binary tree'' to emphasize the fact that the tree is rooted, b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pseudopolynomial Time Number Partitioning
In computer science, pseudopolynomial time number partitioning is a pseudopolynomial time algorithm for solving the partition problem. The problem can be solved using dynamic programming when the size of the set and the size of the sum of the integers in the set are not too big to render the storage requirements infeasible. Suppose the input to the algorithm is a multiset S of cardinality N: : ''S'' = Let ''K'' be the sum of all elements in ''S''. That is: ''K'' = ''x''1 + ... + ''xN''. We will build an algorithm that determines whether there is a subset of ''S'' that sums to \lfloor K/2 \rfloor . If there is a subset, then: : if ''K'' is even, the rest of ''S'' also sums to \lfloor K/2 \rfloor : if ''K'' is odd, then the rest of ''S'' sums to \lceil K/2 \rceil . This is as good a solution as possible. e.g.1 ''S'' = , ''K'' = ''sum(S)'' = 11, ''K/2'' = 5, Find a subset from ''S'' that is closest to ''K/2'' -> = 5, 11 - 5 * 2 = 1 e.g.2 ''S'' = , ''K'' = ''sum(S)'' = 11, ''K/ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Exact Algorithm
In computer science and operations research, exact algorithms are algorithms that always solve an optimization problem to optimality. Unless P = NP, an exact algorithm for an NP-hard optimization problem cannot run in worst-case polynomial time. There has been extensive research on finding exact algorithms whose running time is exponential with a low base. See also * Approximation-preserving reduction * APX is the class of problems with some constant-factor approximation algorithm * Heuristic algorithm In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for solving a problem more quickly when classic methods are too slow for finding an approximate solution, or whe ... * PTAS - a type of approximation algorithm that takes the approximation ratio as a parameter References {{reflist Computational complexity theory Optimization algorithms and methods ... [...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] |
Bin Packing Problem
The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media and technology mapping in FPGA semiconductor chip design. Computationally, the problem is NP-hard, and the corresponding decision problem - deciding if items can fit into a specified number of bins - is NP-complete. Despite its worst-case hardness, optimal solutions to very large instances of the problem can be produced with sophisticated algorithms. In addition, many approximation algorithms exist. For example, the first fit algorithm provides a fast but often non-optimal solution, involving placing each item into the first bin in which it will fit. It requires '' Θ''(''n'' log ''n'') time, where ''n' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
