 | This article may be too technical for most readers to understand.(December 2016) |
In operations research, the glove problem [1] (also known as the condom problem [2] ) is an optimization problem used as an example that the cheapest capital cost often leads to dramatic increase in operational time, but that the shortest operational time need not be given by the most expensive capital cost. [3]
M doctors are each to examine each of N patients, wearing gloves to avoid contamination. Each glove can be used any number of times, but the same side of one glove cannot be exposed to more than one person. Gloves can be re-used any number of times, and more than one can be used simultaneously.
Given M doctors and N patients, the minimum number of gloves G(M, N) required for all the doctors to examine all the patients is given by:
A naive approach would be to estimate the number of gloves as simply G(M, N) = MN. But this number can be significantly reduced by exploiting the fact that each glove has two sides, and it is not necessary to use both sides simultaneously.
A better solution can be found by assigning each person his or her own glove, which is to be used for the entire operation. Every pairwise encounter is then protected by a double layer. Note that the outer surface of the doctor's gloves meets only the inner surface of the patient's gloves. This gives an answer of M + N gloves, which is significantly lower than MN.
The makespan with this scheme is K · max(M, N), where K is the duration of one pairwise encounter. Note that this is exactly the same makespan if MN gloves were used. Clearly in this case, increasing capital cost has not produced a shorter operation time.
The number G(M, N) may be refined further by allowing asymmetry in the initial distribution of gloves. The best scheme is given by:
This scheme uses (1 · N) + ((M − 1 − 1) · 1) + (1 · 0) = M + N − 2 gloves. This number cannot be reduced further.
The makespan is then given by:
Makespan: K · (2N + max(M − 2, N)).
Clearly, the minimum G(M, N) increases the makespan significantly, sometimes by a factor of 3. Note that the benefit in the number of gloves is only 2 units.
One or the other solution may be preferred depending on the relative cost of a glove judged against the longer operation time. In theory, the intermediate solution with (M + N − 1) should also occur as a candidate solution, but this requires such narrow windows on M, N and the cost parameters to be optimal that it is often ignored.
The statement of the problem does not make it clear that the principle of contagion applies, i.e. if the inside of one glove has been touched by the outside of another that previously touched some person, then that inside also counts as touched by that person.
Also, medical gloves are reversible; therefore a better solution exists, which uses
gloves where the less numerous group are equipped with a glove each, the more numerous in pairs. The first of each pair use a clean interface, the second reverse the glove.[ original research? ]
In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, if one has three gloves, then there must be at least two right-handed gloves, or at least two left-handed gloves, because there are three objects, but only two categories of handedness to put them into. This seemingly obvious statement, a type of counting argument, can be used to demonstrate possibly unexpected results. For example, given that the population of London is greater than the maximum number of hairs that can be present on a human's head, then the pigeonhole principle requires that there must be at least two people in London who have the same number of hairs on their heads.
In mathematics and computer science, the floor function is the function that takes as input a real number x, and gives as output the greatest integer less than or equal to x, denoted floor(x) or ⌊x⌋. Similarly, the ceiling function maps x to the least integer greater than or equal to x, denoted ceil(x) or ⌈x⌉.
Rounding means replacing a number with an approximate value that has a shorter, simpler, or more explicit representation. For example, replacing $23.4476 with $23.45, the fraction 312/937 with 1/3, or the expression √2 with 1.414.
In geometry, the Wallace–Bolyai–Gerwien theorem, named after William Wallace, Farkas Bolyai and Paul Gerwien, is a theorem related to dissections of polygons. It answers the question when one polygon can be formed from another by cutting it into a finite number of pieces and recomposing these by translations and rotations. The Wallace–Bolyai–Gerwien theorem states that this can be done if and only if two polygons have the same area.
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data, with:
In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares.
In computer science and graph theory, Karger's algorithm is a randomized algorithm to compute a minimum cut of a connected graph. It was invented by David Karger and first published in 1993.
Job-shop scheduling or the job-shop problem (JSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan – the total length of the schedule. In the specific variant known as job-shop scheduling, each job consists of a set of operationsO1, O2, ..., On which need to be processed in a specific order. Each operation has a specific machine that it needs to be processed on and only one operation in a job can be processed at a given time. A common relaxation is the flexible job shop, where each operation can be processed on any machine of a given set.
The jeep problem, desert crossing problem or exploration problem is a mathematics problem in which a jeep must maximize the distance it can travel into a desert with a given quantity of fuel. The jeep can only carry a fixed and limited amount of fuel, but it can leave fuel and collect fuel at fuel dumps anywhere in the desert.
Flow-shop scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan – the total length of the schedule. In the specific variant known as flow-shop scheduling, each job contains exactly m operations. The i-th operation of the job must be executed on the i-th machine. No machine can perform more than one operation simultaneously. For each operation of each job, execution time is specified.
Collective operations are building blocks for interaction patterns, that are often used in SPMD algorithms in the parallel programming context. Hence, there is an interest in efficient realizations of these operations.
David Bernard Shmoys is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984. His major focus has been in the design and analysis of algorithms for discrete optimization problems.
In operations research, the makespan of a project is the length of time that elapses from the start of work to the end. This type of multi-mode resource constrained project scheduling problem (MRCPSP) seeks to create the shortest logical project schedule, by efficiently using project resources, adding the lowest number of additional resources as possible to achieve the minimum makespan. The term commonly appears in the context of scheduling.
In graph theory, a branch of mathematics, the linear arboricity of an undirected graph is the smallest number of linear forests its edges can be partitioned into. Here, a linear forest is an acyclic graph with maximum degree two; that is, it is a disjoint union of path graphs. Linear arboricity is a variant of arboricity, the minimum number of forests into which the edges can be partitioned.
Matroid partitioning is a problem arising in the mathematical study of matroids and in the design and analysis of algorithms. Its goal is to partition the elements of a matroid into as few independent sets as possible. An example is the problem of computing the arboricity of an undirected graph, the minimum number of forests needed to cover all of its edges. Matroid partitioning may be solved in polynomial time, given an independence oracle for the matroid. It may be generalized to show that a matroid sum is itself a matroid, to provide an algorithm for computing ranks and independent sets in matroid sums, and to compute the largest common independent set in the intersection of two given matroids.
A partition of a polygon is a set of primitive units, which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length.
Truthful job scheduling is a mechanism design variant of the job shop scheduling problem from operations research.
The Queuing Rule of Thumb (QROT) is a mathematical formula, known as the queuing constraint equation when it is used to find an approximation of servers required to service a queue. The formula is written as an inequality relating the number of servers (s), total number of service requestors (N), service time (r), and the maximum time to empty the queue (T):
In parallel computing, all-to-all is a collective operation, where each processor sends an individual message to every other processor.
Blichfeldt's theorem is a mathematical theorem in the geometry of numbers, stating that whenever a bounded set in the Euclidean plane has area , it can be translated so that it includes at least points of the integer lattice. Equivalently, any set with this area, in its original position, must contain some subset of points whose coordinates all differ by integers.
