Misplaced Pages

#648351

85-428: Combinatorial optimization is related to operations research , algorithm theory , and computational complexity theory . It has important applications in several fields, including artificial intelligence , machine learning , auction theory , software engineering , VLSI , applied mathematics and theoretical computer science . Basic applications of combinatorial optimization include, but are not limited to: There

170-449: A distinct vertex to cover each edge that was considered in the process (since it forms a matching ), the vertex cover produced, therefore, is at most twice as large as the optimal one. In other words, this is a constant-factor approximation algorithm with an approximation factor of 2. Under the recent unique games conjecture , this factor is even the best possible one. NP-hard problems vary greatly in their approximability; some, such as

255-579: A feasible solution s ∈ S ( i ) {\displaystyle s\in S(i)} , with s ≠ s ∗ {\displaystyle s\neq s^{*}} , we would want a guarantee of the quality of the solution, which is a performance to be guaranteed (approximation factor). Specifically, having A Π ( i ) ∈ S i {\displaystyle A_{\Pi }(i)\in S_{i}} ,

340-681: A field widely used in industries ranging from petrochemicals to airlines, finance, logistics, and government, moving to a focus on the development of mathematical models that can be used to analyse and optimize sometimes complex systems, and has become an area of active academic and industrial research. In the 17th century, mathematicians Blaise Pascal and Christiaan Huygens solved problems involving sometimes complex decisions ( problem of points ) by using game-theoretic ideas and expected values ; others, such as Pierre de Fermat and Jacob Bernoulli , solved these types of problems using combinatorial reasoning instead. Charles Babbage 's research into

425-468: A long way from the target it had time to alter course under water so the chances of it being within the 20-foot kill zone of the charges was small. It was more efficient to attack those submarines close to the surface when the targets' locations were better known than to attempt their destruction at greater depths when their positions could only be guessed. Before the change of settings from 100 to 25 feet, 1% of submerged U-boats were sunk and 14% damaged. After

510-413: A maximization (minimization) problem of c - ϵ (min: c + ϵ) means that the algorithm has an approximation ratio of c ∓ ϵ for arbitrary ϵ > 0 but that the ratio has not (or cannot) be shown for ϵ = 0. An example of this is the optimal inapproximability — inexistence of approximation — ratio of 7 / 8 + ϵ for satisfiable MAX-3SAT instances due to Johan Håstad . As mentioned previously, when c = 1,

595-562: A new technique specific to the problem at hand (and, afterwards, to that type of problem). The major sub-disciplines (but not limited to) in modern operational research, as identified by the journal Operations Research and The Journal of the Operational Research Society are: In the decades after the two world wars, the tools of operations research were more widely applied to problems in business, industry, and society. Since that time, operational research has expanded into

680-404: A path from u {\displaystyle u} to v {\displaystyle v} that uses the fewest edges". This problem might have an answer of, say, 4. A corresponding decision problem would be "is there a path from u {\displaystyle u} to v {\displaystyle v} that uses 10 or fewer edges?" This problem can be answered with

765-461: A performance guarantee of r = ρ − 1 {\displaystyle r=\rho ^{-1}} . In the literature, both definitions are common but it is clear which definition is used since, for maximization problems, as ρ ≤ 1 while r ≥ 1. The absolute performance guarantee P A {\displaystyle \mathrm {P} _{A}} of some approximation algorithm A , where x refers to an instance of

850-404: A problem, and where R A ( x ) {\displaystyle R_{A}(x)} is the performance guarantee of A on x (i.e. ρ for problem instance x ) is: That is to say that P A {\displaystyle \mathrm {P} _{A}} is the largest bound on the approximation ratio, r , that one sees over all possible instances of the problem. Likewise,

935-430: A simple 'yes' or 'no'. The field of approximation algorithms deals with algorithms to find near-optimal solutions to hard problems. The usual decision version is then an inadequate definition of the problem since it only specifies acceptable solutions. Even though we could introduce suitable decision problems, the problem is then more naturally characterized as an optimization problem. An NP-optimization problem (NPO)

SECTION 10

#1733115472649

1020-588: A smooth paint finish increased airspeed by reducing skin friction. On land, the operational research sections of the Army Operational Research Group (AORG) of the Ministry of Supply (MoS) were landed in Normandy in 1944 , and they followed British forces in the advance across Europe. They analyzed, among other topics, the effectiveness of artillery, aerial bombing and anti-tank shooting. In 1947, under

1105-439: A survey carried out by RAF Bomber Command . For the survey, Bomber Command inspected all bombers returning from bombing raids over Germany over a particular period. All damage inflicted by German air defenses was noted and the recommendation was given that armor be added in the most heavily damaged areas. This recommendation was not adopted because the fact that the aircraft were able to return with these areas damaged indicated

1190-451: A year these ideas were incorporated into a near-linear time O ( n log ⁡ n ) {\displaystyle O(n\log n)} algorithm for any constant ϵ > 0 {\displaystyle \epsilon >0} . Given an optimization problem: Π : I × S {\displaystyle \Pi :I\times S} where Π {\displaystyle \Pi }

1275-483: Is a combinatorial optimization problem with the following additional conditions. Note that the below referred polynomials are functions of the size of the respective functions' inputs, not the size of some implicit set of input instances. This implies that the corresponding decision problem is in NP . In computer science, interesting optimization problems usually have the above properties and are therefore NPO problems. A problem

1360-500: Is a large amount of literature on polynomial-time algorithms for certain special classes of discrete optimization. A considerable amount of it is unified by the theory of linear programming . Some examples of combinatorial optimization problems that are covered by this framework are shortest paths and shortest-path trees , flows and circulations , spanning trees , matching , and matroid problems. For NP-complete discrete optimization problems, current research literature includes

1445-526: Is additionally called a P-optimization (PO) problem, if there exists an algorithm which finds optimal solutions in polynomial time. Often, when dealing with the class NPO, one is interested in optimization problems for which the decision versions are NP-complete . Note that hardness relations are always with respect to some reduction. Due to the connection between approximation algorithms and computational optimization problems, reductions which preserve approximation in some respect are for this subject preferred than

1530-444: Is an umbrella organization for operational research societies worldwide, representing approximately 50 national societies including those in the US, UK , France, Germany, Italy , Canada, Australia, New Zealand, Philippines, India, Japan and South Africa. For the institutionalization of Operations Research, the foundation of IFORS in 1960 was of decisive importance, which stimulated

1615-625: Is an approximation problem, I {\displaystyle I} the set of inputs and S {\displaystyle S} the set of solutions, we can define the cost function: c : S → R + {\displaystyle c:S\rightarrow \mathbb {R} ^{+}} and the set of feasible solutions: ∀ i ∈ I , S ( i ) = s ∈ S : i Π s {\displaystyle \forall i\in I,S(i)={s\in S:i\Pi _{s}}} finding

1700-578: Is concerned with developing and applying models and concepts that may prove useful in helping to illuminate management issues and solve managerial problems, as well as designing and developing new and better models of organizational excellence. Some of the fields that have considerable overlap with Operations Research and Management Science include: Applications are abundant such as in airlines, manufacturing companies, service organizations , military branches, and government. The range of problems and issues to which it has contributed insights and solutions

1785-438: Is often concerned with determining the extreme values of some real-world objective: the maximum (of profit, performance, or yield) or minimum (of loss, risk, or cost). Originating in military efforts before World War II , its techniques have grown to concern problems in a variety of industries. Operations research (OR) encompasses the development and the use of a wide range of problem-solving techniques and methods applied in

SECTION 20

#1733115472649

1870-408: Is often much better. This is often the case for algorithms that work by solving a convex relaxation of the optimization problem on the given input. For example, there is a different approximation algorithm for minimum vertex cover that solves a linear programming relaxation to find a vertex cover that is at most twice the value of the relaxation. Since the value of the relaxation is never larger than

1955-419: Is one for the minimum vertex cover problem, where the goal is to choose the smallest set of vertices such that every edge in the input graph contains at least one chosen vertex. One way to find a vertex cover is to repeat the following process: find an uncovered edge, add both its endpoints to the cover, and remove all edges incident to either vertex from the graph. As any vertex cover of the input graph must use

2040-459: Is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on

2125-413: Is said to be an r ( n )-approximation algorithm and has an approximation ratio of r ( n ). Likewise, a problem with an r ( n )-approximation algorithm is said to be r ( n ) - approximable or have an approximation ratio of r ( n ). For minimization problems, the two different guarantees provide the same result and that for maximization problems, a relative performance guarantee of ρ is equivalent to

2210-528: Is vast. It includes: Management is also concerned with so-called soft-operational analysis which concerns methods for strategic planning , strategic decision support , problem structuring methods . In dealing with these sorts of challenges, mathematical modeling and simulation may not be appropriate or may not suffice. Therefore, during the past 30 years , a number of non-quantified modeling methods have been developed. These include: The International Federation of Operational Research Societies (IFORS)

2295-617: The British Army . Patrick Blackett worked for several different organizations during the war. Early in the war while working for the Royal Aircraft Establishment (RAE) he set up a team known as the "Circus" which helped to reduce the number of anti-aircraft artillery rounds needed to shoot down an enemy aircraft from an average of over 20,000 at the start of the Battle of Britain to 4,000 in 1941. In 1941, Blackett moved from

2380-619: The Kammhuber Line , it was realized by the British that if the RAF bombers were to fly in a bomber stream they could overwhelm the night fighters who flew in individual cells directed to their targets by ground controllers. It was then a matter of calculating the statistical loss from collisions against the statistical loss from night fighters to calculate how close the bombers should fly to minimize RAF losses. The "exchange rate" ratio of output to input

2465-428: The asymptotic performance ratio R A ∞ {\displaystyle R_{A}^{\infty }} is: That is to say that it is the same as the absolute performance ratio , with a lower bound n on the size of problem instances. These two types of ratios are used because there exist algorithms where the difference between these two is significant. In the literature, an approximation ratio for

2550-454: The ellipsoid algorithm ), complex data structures, or sophisticated algorithmic techniques, leading to difficult implementation issues or improved running time performance (over exact algorithms) only on impractically large inputs. Implementation and running time issues aside, the guarantees provided by approximation algorithms may themselves not be strong enough to justify their consideration in practice. Despite their inability to be used "out of

2635-579: The initialism OR , is a discipline that deals with the development and application of analytical methods to improve decision-making. The term management science is occasionally used as a synonym. Employing techniques from other mathematical sciences, such as modeling , statistics , and optimization , operations research arrives at optimal or near-optimal solutions to decision-making problems. Because of its emphasis on practical applications, operations research has overlapped with many other disciplines, notably industrial engineering . Operations research

Combinatorial optimization - Misplaced Pages Continue

2720-521: The knapsack problem , can be approximated within a multiplicative factor 1 + ϵ {\displaystyle 1+\epsilon } , for any fixed ϵ > 0 {\displaystyle \epsilon >0} , and therefore produce solutions arbitrarily close to the optimum (such a family of approximation algorithms is called a polynomial-time approximation scheme or PTAS). Others are impossible to approximate within any constant, or even polynomial, factor unless P = NP , as in

2805-400: The performance guarantee , R ( x,y ), of a solution y to an instance x is defined as where f ( y ) is the value/cost of the solution y for the instance x . Clearly, the performance guarantee is greater than or equal to 1 and equal to 1 if and only if y is an optimal solution. If an algorithm A guarantees to return solutions with a performance guarantee of at most r ( n ), then A

2890-613: The 1960s, ORSA reached 8000 members. Consulting companies also founded OR groups. In 1953, Abraham Charnes and William Cooper published the first textbook on Linear Programming. In the 1950s and 1960s, chairs of operations research were established in the U.S. and United Kingdom (from 1964 in Lancaster) in the management faculties of universities. Further influences from the U.S. on the development of operations research in Western Europe can be traced here. The authoritative OR textbooks from

2975-499: The CC-ORS indicated that on average if the trigger depth of aerial-delivered depth charges were changed from 100 to 25 feet, the kill ratios would go up. The reason was that if a U-boat saw an aircraft only shortly before it arrived over the target then at 100 feet the charges would do no damage (because the U-boat wouldn't have had time to descend as far as 100 feet), and if it saw the aircraft

3060-595: The Management Sciences (INFORMS) publishes thirteen scholarly journals about operations research, including the top two journals in their class, according to 2005 Journal Citation Reports . They are: These are listed in alphabetical order of their titles. Approximation algorithm In computer science and operations research , approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on

3145-661: The NATO military command structure , the transfer of NATO headquarters from France to Belgium led to the institutionalization of OR in Belgium, where Jacques Drèze founded CORE, the Center for Operations Research and Econometrics at the Catholic University of Leuven in 1966. With the development of computers over the next three decades, Operations Research can now solve problems with hundreds of thousands of variables and constraints. Moreover,

3230-599: The RAE to the Navy, after first working with RAF Coastal Command , in 1941 and then early in 1942 to the Admiralty . Blackett's team at Coastal Command's Operational Research Section (CC-ORS) included two future Nobel prize winners and many other people who went on to be pre-eminent in their fields. They undertook a number of crucial analyses that aided the war effort. Britain introduced the convoy system to reduce shipping losses, but while

3315-755: The U.S. were published in Germany in German language and in France in French (but not in Italian ), such as the book by George Dantzig "Linear Programming"(1963) and the book by C. West Churchman et al. "Introduction to Operations Research"(1957). The latter was also published in Spanish in 1973, opening at the same time Latin American readers to Operations Research. NATO gave important impulses for

3400-636: The US-based organization INFORMS began an initiative to market the OR profession better, including a website entitled The Science of Better which provides an introduction to OR and examples of successful applications of OR to industrial problems. This initiative has been adopted by the Operational Research Society in the UK, including a website entitled Learn About OR . The Institute for Operations Research and

3485-576: The United Kingdom (including Patrick Blackett (later Lord Blackett OM PRS), Cecil Gordon , Solly Zuckerman , (later Baron Zuckerman OM, KCB, FRS), C. H. Waddington , Owen Wansbrough-Jones , Frank Yates , Jacob Bronowski and Freeman Dyson ), and in the United States ( George Dantzig ) looked for ways to make better decisions in such areas as logistics and training schedules. The modern field of operational research arose during World War II. In

Combinatorial optimization - Misplaced Pages Continue

3570-642: The World War II era, operational research was defined as "a scientific method of providing executive departments with a quantitative basis for decisions regarding the operations under their control". Other names for it included operational analysis (UK Ministry of Defence from 1962) and quantitative management. During the Second World War close to 1,000 men and women in Britain were engaged in operational research. About 200 operational research scientists worked for

3655-486: The algorithm has an approximation factor (or approximation ratio ) of ρ ( n ) {\displaystyle \rho (n)} if ∀ i ∈ I   s . t . | i | = n {\displaystyle \forall i\in I\ s.t.|i|=n} , we have: The approximation can be proven tight ( tight approximation ) by demonstrating that there exist instances where

3740-446: The algorithm performs at the approximation limit, indicating the tightness of the bound. In this case, it's enough to construct an input instance designed to force the algorithm into a worst-case scenario. For some approximation algorithms it is possible to prove certain properties about the approximation of th.e optimum result. For example, a ρ -approximation algorithm A is defined to be an algorithm for which it has been proven that

3825-433: The algorithms may be refined to become more practical. One such example is the initial PTAS for Euclidean TSP by Sanjeev Arora (and independently by Joseph Mitchell ) which had a prohibitive running time of n O ( 1 / ϵ ) {\displaystyle n^{O(1/\epsilon )}} for a 1 + ϵ {\displaystyle 1+\epsilon } approximation. Yet, within

3910-437: The areas were not vital, and adding armor to non-vital areas where damage is acceptable reduces aircraft performance. Their suggestion to remove some of the crew so that an aircraft loss would result in fewer personnel losses, was also rejected by RAF command. Blackett's team made the logical recommendation that the armor be placed in the areas which were completely untouched by damage in the bombers who returned. They reasoned that

3995-567: The auspices of the British Association , a symposium was organized in Dundee . In his opening address, Watson-Watt offered a definition of the aims of OR: With expanded techniques and growing awareness of the field at the close of the war, operational research was no longer limited to only operational, but was extended to encompass equipment procurement, training, logistics and infrastructure. Operations research also grew in many areas other than

4080-452: The best solution s ∗ {\displaystyle s^{*}} for a maximization or a minimization problem: s ∗ ∈ S ( i ) {\displaystyle s^{*}\in S(i)} , c ( s ∗ ) = m i n / m a x   c ( S ( i ) ) {\displaystyle c(s^{*})=min/max\ c(S(i))} Given

4165-419: The box" in practical applications, the ideas and insights behind the design of such algorithms can often be incorporated in other ways in practical algorithms. In this way, the study of even very expensive algorithms is not a completely theoretical pursuit as they can yield valuable insights. In other cases, even if the initial results are of purely theoretical interest, over time, with an improved understanding,

4250-403: The case of the maximum clique problem . Therefore, an important benefit of studying approximation algorithms is a fine-grained classification of the difficulty of various NP-hard problems beyond the one afforded by the theory of NP-completeness . In other words, although NP-complete problems may be equivalent (under polynomial-time reductions) to each other from the perspective of exact solutions,

4335-405: The change, 7% were sunk and 11% damaged; if submarines were caught on the surface but had time to submerge just before being attacked, the numbers rose to 11% sunk and 15% damaged. Blackett observed "there can be few cases where such a great operational gain had been obtained by such a small and simple change of tactics". Bomber Command's Operational Research Section (BC-ORS), analyzed a report of

SECTION 50

#1733115472649

4420-442: The construction of mathematical models that attempt to describe the system. Because of the computational and statistical nature of most of these fields, OR also has strong ties to computer science and analytics . Operational researchers faced with a new problem must determine which of these techniques are most appropriate given the nature of the system, the goals for improvement, and constraints on time and computing power, or develop

4505-410: The corresponding optimization problems behave very differently from the perspective of approximate solutions. By now there are several established techniques to design approximation algorithms. These include the following ones. While approximation algorithms always provide an a priori worst case guarantee (be it additive or multiplicative), in some cases they also provide an a posteriori guarantee that

4590-484: The cost of transportation and sorting of mail led to England's universal "Penny Post" in 1840, and to studies into the dynamical behaviour of railway vehicles in defence of the GWR 's broad gauge. Beginning in the 20th century, study of inventory management could be considered the origin of modern operations research with economic order quantity developed by Ford W. Harris in 1913. Operational research may have originated in

4675-400: The distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time . The field of approximation algorithms, therefore, tries to understand how closely it

4760-527: The efforts of military planners during World War I (convoy theory and Lanchester's laws ). Percy Bridgman brought operational research to bear on problems in physics in the 1920s and would later attempt to extend these to the social sciences. Modern operational research originated at the Bawdsey Research Station in the UK in 1937 as the result of an initiative of the station's superintendent, A. P. Rowe and Robert Watson-Watt . Rowe conceived

4845-804: The following topics: Combinatorial optimization problems can be viewed as searching for the best element of some set of discrete items; therefore, in principle, any sort of search algorithm or metaheuristic can be used to solve them. Widely applicable approaches include branch-and-bound (an exact algorithm which can be stopped at any point in time to serve as heuristic), branch-and-cut (uses linear optimisation to generate bounds), dynamic programming (a recursive solution construction with limited search window) and tabu search (a greedy-type swapping algorithm). However, generic search algorithms are not guaranteed to find an optimal solution first, nor are they guaranteed to run quickly (in polynomial time). Since some discrete optimization problems are NP-complete , such as

4930-667: The foundation of national OR societies in Austria, Switzerland and Germany. IFORS held important international conferences every three years since 1957. The constituent members of IFORS form regional groups, such as that in Europe, the Association of European Operational Research Societies (EURO). Other important operational research organizations are Simulation Interoperability Standards Organization (SISO) and Interservice/Industry Training, Simulation and Education Conference (I/ITSEC) In 2004,

5015-494: The idea as a means to analyse and improve the working of the UK's early-warning radar system, code-named " Chain Home " (CH). Initially, Rowe analysed the operating of the radar equipment and its communication networks, expanding later to include the operating personnel's behaviour. This revealed unappreciated limitations of the CH network and allowed remedial action to be taken. Scientists in

5100-546: The inapproximability of Independent Set and the famous PCP theorem , that modern tools for proving inapproximability results were uncovered. The PCP theorem, for example, shows that Johnson's 1974 approximation algorithms for Max SAT , set cover , independent set and coloring all achieve the optimal approximation ratio, assuming P ≠ NP. Not all approximation algorithms are suitable for direct practical applications. Some involve solving non-trivial linear programming / semidefinite relaxations (which may themselves invoke

5185-465: The knowledge of the existence of Christofides' 1.5 approximation algorithm, this tells us that the threshold of approximability for metric traveling salesman (if it exists) is somewhere between 123/122 and 1.5. While inapproximability results have been proved since the 1970s, such results were obtained by ad hoc means and no systematic understanding was available at the time. It is only since the 1990 result of Feige, Goldwasser, Lovász, Safra and Szegedy on

SECTION 60

#1733115472649

5270-961: The lack of data, there are also no computer applications in the textbooks. Operational research is also used extensively in government where evidence-based policy is used. The field of management science (MS) is known as using operations research models in business. Stafford Beer characterized this in 1967. Like operational research itself, management science is an interdisciplinary branch of applied mathematics devoted to optimal decision planning, with strong links with economics, business, engineering, and other sciences . It uses various scientific research -based principles, strategies , and analytical methods including mathematical modeling , statistics and numerical algorithms to improve an organization's ability to enact rational and meaningful management decisions by arriving at optimal or near-optimal solutions to sometimes complex decision problems. Management scientists help businesses to achieve their goals using

5355-599: The large volumes of data required for such problems can be stored and manipulated very efficiently." Much of operations research (modernly known as 'analytics') relies upon stochastic variables and a therefore access to truly random numbers. Fortunately, the cybernetics field also required the same level of randomness. The development of increasingly better random number generators has been a boon to both disciplines. Modern applications of operations research includes city planning, football strategies, emergency planning, optimizing all facets of industry and economy, and undoubtedly with

5440-400: The likelihood of the inclusion of terrorist attack planning and definitely counterterrorist attack planning. More recently, the research approach of operations research, which dates back to the 1950s, has been criticized for being collections of mathematical models but lacking an empirical basis of data collection for applications. How to collect data is not presented in the textbooks. Because of

5525-474: The losses suffered by convoys depended largely on the number of escort vessels present, rather than the size of the convoy. Their conclusion was that a few large convoys are more defensible than many small ones. While performing an analysis of the methods used by RAF Coastal Command to hunt and destroy submarines, one of the analysts asked what colour the aircraft were. As most of them were from Bomber Command they were painted black for night-time operations. At

5610-437: The measure m ( x , y ) {\displaystyle m(x,y)} is bounded by a polynomial function of the size of x {\displaystyle x} . The class NPOPB is the class of NPO problems that are polynomially-bounded. Operations research Operations research ( British English : operational research ) (U.S. Air Force Specialty Code : Operations Analysis), often shortened to

5695-502: The military once scientists learned to apply its principles to the civilian sector. The development of the simplex algorithm for linear programming was in 1947. In the 1950s, the term Operations Research was used to describe heterogeneous mathematical methods such as game theory , dynamic programming, linear programming, warehousing, spare parts theory , queue theory , simulation and production control, which were used primarily in civilian industry. Scientific societies and journals on

5780-414: The non-existence of efficient algorithms with certain approximation ratios is proved (conditioned on widely believed hypotheses such as the P ≠ NP conjecture) by means of reductions . In the case of the metric traveling salesman problem, the best known inapproximability result rules out algorithms with an approximation ratio less than 123/122 ≈ 1.008196 unless P = NP, Karpinski, Lampis, Schmied. Coupled with

5865-530: The on-target bomb rate of B-29s bombing Japan from the Marianas Islands by increasing the training ratio from 4 to 10 percent of flying hours; revealed that wolf-packs of three United States submarines were the most effective number to enable all members of the pack to engage targets discovered on their individual patrol stations; revealed that glossy enamel paint was more effective camouflage for night fighters than conventional dull camouflage paint finish, and

5950-527: The outset on when they may succeed or fail. There is widespread interest in theoretical computer science to better understand the limits to which we can approximate certain famous optimization problems. For example, one of the long-standing open questions in computer science is to determine whether there is an algorithm that outperforms the 2-approximation for the Steiner Forest problem by Agrawal et al. The desire to understand hard optimization problems from

6035-466: The perspective of approximability is motivated by the discovery of surprising mathematical connections and broadly applicable techniques to design algorithms for hard optimization problems. One well-known example of the former is the Goemans–Williamson algorithm for maximum cut , which solves a graph theoretic problem using high dimensional geometry. A simple example of an approximation algorithm

6120-437: The principle of using warships to accompany merchant ships was generally accepted, it was unclear whether it was better for convoys to be small or large. Convoys travel at the speed of the slowest member, so small convoys can travel faster. It was also argued that small convoys would be harder for German U-boats to detect. On the other hand, large convoys could deploy more warships against an attacker. Blackett's staff showed that

6205-403: The problem is said to have a polynomial-time approximation scheme . An ϵ-term may appear when an approximation algorithm introduces a multiplicative error and a constant error while the minimum optimum of instances of size n goes to infinity as n does. In this case, the approximation ratio is c ∓ k / OPT = c ∓ o(1) for some constants c and k . Given arbitrary ϵ > 0, one can choose

6290-409: The pursuit of improved decision-making and efficiency, such as simulation , mathematical optimization , queueing theory and other stochastic-process models, Markov decision processes , econometric methods , data envelopment analysis , ordinal priority approach , neural networks , expert systems , decision analysis , and the analytic hierarchy process . Nearly all of these techniques involve

6375-573: The quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra , Shmoys and Tardos for scheduling on unrelated parallel machines. The design and analysis of approximation algorithms crucially involves a mathematical proof certifying the quality of the returned solutions in the worst case. This distinguishes them from heuristics such as annealing or genetic algorithms , which find reasonably good solutions on some inputs, but provide no clear indication at

6460-421: The scientific methods of operational research. The management scientist's mandate is to use rational, systematic, science-based techniques to inform and improve decisions of all kinds. Of course, the techniques of management science are not restricted to business applications but may be applied to military, medical, public administration, charitable groups, political groups or community groups. Management science

6545-477: The size of the optimal vertex cover, this yields another 2-approximation algorithm. While this is similar to the a priori guarantee of the previous approximation algorithm, the guarantee of the latter can be much better (indeed when the value of the LP relaxation is far from the size of the optimal vertex cover). Approximation algorithms as a research area is closely related to and informed by inapproximability theory where

6630-603: The spread of Operations Research in Western Europe; NATO headquarters (SHAPE) organised four conferences on OR in the 1950s – the one in 1956 with 120 participants – bringing OR to mainland Europe. Within NATO, OR was also known as "Scientific Advisory" (SA) and was grouped together in the Advisory Group of Aeronautical Research and Development (AGARD). SHAPE and AGARD organized an OR conference in April 1957 in Paris. When France withdrew from

6715-662: The subject of operations research were founded in the 1950s, such as the Operation Research Society of America (ORSA) in 1952 and the Institute for Management Science (TIMS) in 1953. Philip Morse, the head of the Weapons Systems Evaluation Group of the Pentagon, became the first president of ORSA and attracted the companies of the military-industrial complex to ORSA, which soon had more than 500 members. In

6800-504: The suggestion of CC-ORS a test was run to see if that was the best colour to camouflage the aircraft for daytime operations in the grey North Atlantic skies. Tests showed that aircraft painted white were on average not spotted until they were 20% closer than those painted black. This change indicated that 30% more submarines would be attacked and sunk for the same number of sightings. As a result of these findings Coastal Command changed their aircraft to using white undersurfaces. Other work by

6885-519: The survey was biased, since it only included aircraft that returned to Britain. The areas untouched in returning aircraft were probably vital areas, which, if hit, would result in the loss of the aircraft. This story has been disputed, with a similar damage assessment study completed in the US by the Statistical Research Group at Columbia University , the result of work done by Abraham Wald . When Germany organized its air defences into

6970-545: The traveling salesman (decision) problem, this is expected unless P=NP . For each combinatorial optimization problem, there is a corresponding decision problem that asks whether there is a feasible solution for some particular measure m 0 {\displaystyle m_{0}} . For example, if there is a graph G {\displaystyle G} which contains vertices u {\displaystyle u} and v {\displaystyle v} , an optimization problem might be "find

7055-529: The usual Turing and Karp reductions . An example of such a reduction would be L-reduction . For this reason, optimization problems with NP-complete decision versions are not necessarily called NPO-complete. NPO is divided into the following subclasses according to their approximability: An NPO problem is called polynomially bounded (PB) if, for every instance x {\displaystyle x} and for every solution y ∈ f ( x ) {\displaystyle y\in f(x)} ,

7140-419: The value/cost, f ( x ), of the approximate solution A ( x ) to an instance x will not be more (or less, depending on the situation) than a factor ρ times the value, OPT, of an optimum solution. The factor ρ is called the relative performance guarantee . An approximation algorithm has an absolute performance guarantee or bounded error c , if it has been proven for every instance x that Similarly,

7225-594: Was a characteristic feature of operational research. By comparing the number of flying hours put in by Allied aircraft to the number of U-boat sightings in a given area, it was possible to redistribute aircraft to more productive patrol areas. Comparison of exchange rates established "effectiveness ratios" useful in planning. The ratio of 60 mines laid per ship sunk was common to several campaigns: German mines in British ports, British mines on German routes, and United States mines in Japanese routes. Operational research doubled

#648351