6.5 Reductions

This chapter under construction.

Reduction.

Reduction or simulation is a powerful idea in computer science.... Problem-solving framework that transforms a problem X into a simpler problem Y such that it is easy to deduce a solution to the original problem X based on the solution for Y.

Eric Alander - "Reduction provides an abstraction. If A efficiently reduces to B and B efficiently reduces to A, then A and B are equivalent in a meaningful sense: they are two different ways to look at the same problem. Instead of infinitely many computational problems, we are left with a smaller number of classes of equivalent problems. Nothing had prepared the computing community for the shocking insight that there are really just a handful of fundamentally different computational problems that people want to solve." Partitions natural computational problems into meaningful groups based on resource bounds.

Reductions.

Upper bounds.

3-COLLINEAR to sorting.
Convex hull to sorting (Graham scan).
MEDIAN to SORTING.
Bipartite matching to maxflow.
BipartiteMatching.java computes a maximum cardinality matching in a bipartite graph by reducing the problem to max flow. The order of growth of the running time is E V in the worst case since each augmentation increases the cardinality of the matching by one.
The Hopcroft-Karp algorithm improves the running time to E V^.5. LP standard form: a standard form linear program is { max cx : Ax <= b, x ≥ 0 }. Show how to reduce a general linear program (with ≤, ≥, and = constraints) to standard form.
Maximum flow to linear programming.
Assignment problem to linear programming.
PERT to topological sort in a DAG.
USTCONN (s-t connectivity in undirected graphs) to STCONN (undirected s-t connectivity in directed graphs).
Shortest paths on undirected graphs to shortest paths on directed graphs.
Euclidean MST to Delauney triangulation.
LP feasibility reduces to LP. (Use binary search. Need to bound value of a bounded LP.)
Two-person zero-sum games to LP.
LP reduces to two-person zero-sum games. (Exercise 26 in Bradley, Hax, and Magnanti)

Lower bounds.

Element distinctness to sorting.
Closest pair 2D to Euclidean MST 2D.
Convex hull to Voronoi / Delauney triangulation.
3-SUM to 3-COLLINEAR.
Exercise: 3-SUM to 4-SUM.
Exercise: 3-SUM to 3-SUMplus
Exercise: 3-COLLINEAR to 3-CONCURRENT.
3-SAT to INDEPENDENT-SET.
INDEPENDENT-SET to ILP.

Element distinctness. Given N elements x₁, ..., x_n from a totally ordered universe, is there a pair i ≠ j such that x_i = x_j? Theta(N log N) lower bound in algebraic decision tree model. O(N log N) easy by sorting.
Solution 1: Given N distinct values. Let ai be ith smallest element. In any comparison based algorithm for the problem, we must compare a_i against a_i-1; otherwise the algorithm could not distinguish between the case a_i-1 < a_i and a_i-1 = a_i. Consider two different permutations of the N elements. There is an element a_i where a_i-1 precedes a_i in the first permutation but a_i-1 precedes a_i in the second. Since every comparison based algorithm must compare a_i and a_i-1, the algorithm runs differently on the two permutations. Thus, there are at leats N! leaves. reference
Solution 2: suppose the elements are all distinct and a_1 < a_2 < ... < a_N. Any correct algorithm for element distinctness must compare a_i with a_i+1 for each i < N. If not, then the algorithm would produce the same output if we changed a_i+1 to a_i (but this would change the answer from no duplicates to has duplicates). The set of compares the algorithm uses forms a DAG. Find the total order (in linear time) and this gives the sorted order. Thus, the algorithm can be used for sorting distinct elements and the sorting lower bound applies.
3-SUM.
3-SAT.

Assignment problem.

AssignmentProblem.java implements the successive shortest paths algorithm; the order of growth of the running time in the wrost case is N^3 log N. AssignmentProblemDense.java implements the successive shortest paths algorithm; the order of growth of the running time in the wrost case is N^3.

Linear programming.

Linear programming solvers.

Simplex.java is a bare-bones version of the simplex algorithm.
QSopt is a Java linear program solver created by David Applegate, William Cook, Sanjeeb Dash, and Monika Mevenkamp. It can be used at no cost for research or education purposes. QSoptSolver.java solves a linear program in LP format, such as beer.lp.

Matlab contains a linear programming solver in the optimization toolbox.

[wayne:tombstone] ~> matlab
                                      < M A T L A B (R) >
                            Copyright 1984-2009 The MathWorks, Inc.
                          Version 7.9.0.529 (R2009b) 64-bit (glnxa64)
                                        August 12, 2009
>> A = [5 15; 4 4; 35 20];
>> b = [480; 160; 1190];
>> c = [13; 23];

>> lb = [0; 0];
>> ub = [inf; inf];
>> x = linprog(-c, A, b, [], [], lb, ub)
x =
    12.0000
    28.0000

CPLEX is a high-performance mathematical programming solver for linear programming, mixed integer programming, and quadratic programming. It supports interfaces to C, C++, Java, Python, Matlab, and Microsoft Excel. It is also accessible via the modeling systems including AIMMS, AMPL, GAMS, and MPL.

AMPL is a modeling language for mathematical programming. The files beer.mod and beer.dat specify the model and data for the brewery problem.

[wayne:tombstone] ~> ampl
ILOG AMPL 9.100
AMPL Version 20021038 (SunOS 5.8)

ampl: model beer.mod;

ampl: data beer.dat;

ampl: solve;
ILOG CPLEX 9.100 
CPLEX 9.1.0: optimal solution; objective 800
2 dual simplex iterations (1 in phase I)

ampl: display x;
x [*] :=  ale 12  beer 28  ;

ampl: display constraints.dual;
x [*] :=  corn 1  hops 2  malt 0  ;

Microsoft Excel has a primitive solver add-in for Windows, but it is no longer available for Mac.

Q + A

Q. Undirected shortest paths with negative weights to directed shortest paths?

A. Need more clever reduction to avoid negative cycles (via nonbipartite matching).

Exercises

gcd and lcm. Reduce lcm to gcd.
Table k-sum. Given a k-by-N table of integers, are there k that sum to 0, one from each of the k rows?
Coin distinctness. Given N coins and a balance scale, determine if the coins all weigh different amounts. Prove that any algorithm that solves the problem has complexity at least N log N. Hint: you may use the fact that given N real numbers, element distinctness requires at least N log N comparisons in the linear decision tree model (where you can make comparisons between arbitrary linear combinations of the N elements, e.g, x1 + 2x2 < x3).
Set equality. Given two sets S and T, does S equal T? Give an O(N log N) algorithm and a matching lower bound.
Set subset. Given two sets S and T, is S a subset of T? Give an O(N log N) algorithm and a matching lower bound.
Set disjointness. Given two sets S and T, does S intersect T equal the empty set? Give an O(N log N) algorithm and a matching lower bound. (Since S and T are sets, there are no duplicated elements in either.)
Solution. To get the O(N log N) upper bound, sort the union of the elements in S and T and check for duplicates.
Set disjointness. Given two sets S and T, each in ascending order, does S intersect T equal the empty set? Prove an Omega(N log N) lower bound or given an O(N) algorithm.
Lower bound for merging two lists. Show any comparison-based algorithm for merging two lists of size N requires at least 2N-1 comparisons in the worst case. Solution: lower bound holds even if all elements are distinct. If the ith and (i+1)st smallest elements are in different lists, then they must be compared.
Lower bound for binary search. log(N+1) comparisons required. Solution: lower bound holds even if all elements are distinct....
Euclidean TSP and MST lower bounds. Given an Omega(N log N) for the Euclidean TSP or Euclidean MST (requires algebraic decision trees to make sense since you want to allow a reasonable algorithm to compute distances). Solution: choose N points on a line. Optimal tour must visit the points in ascending order.
Lower bound for mode. Theta(N log N) bound for mode. Solution: could solve element distinctness problem by finding mode and checking whether it is more than one.
Lower bound for closest pair. Theta(N log N) bound for closest pair. Solution: could solve element distinctness problem in sub-lineararithmic time if had a sub-lineararithmic algorithm by finding closest pair and checking if they are equal.
Smallest and second smallest. Describe how to find both the smallest and second smallest element using at most N + log N comparisons. Solution: divide the elements into pairs and compare two elements in each pair. Recur with the N/2 winners from each pair. After N-1 comparisons, we have the minimum element. Note that each element is compared with at most log N other elements. In particular, the smallest element is compared with at most log N other elements, and one of these must be the second smallest. If you keep track of all the comparisons, you can remember the log N involving the smallest element and compare these.
Counting inversions. Prove a Theta(N log N) lower bound. This is an open research question.
Nuts and bolts. Prove a Theta(N log N) lower bound for the nuts and bolts problem in the quicksort section. [A matching worst case upper bound of O(N log N) is known, but it is remarkably complicated.]
Existence symbol table. Suppose you had a comparison-based algorithm that supports insert and exists in O(1) comparisons per operation. Explain why this is impossible in this model of computation. Solution: to solve element distinctness in O(N) time, for each of the N elments, check whether it's already in the data structure (if so, then this is a duplicate); if not, insert it.
Model a constraint of the form x ≤ y using integer programming (Ax = b, x >= 0, x integral).
Model a constraint of the form x = { 0 or 1 } using integer programming.
Model a constraint of the form x = { 1 or 2 or 4 } using integer programming.
Tait coloring. Model 3-edge coloring cubic graph using IP.
Assign organ donors to patients.
Bipartite vertex cover. Reduce to max flow.
Transitive reduction and transitive closure. Reduce transitive reduction to transitive closure and vice versa (when running time is measured only as a function of the number of vertices V). Also reduces to Boolean matrix multiplication.
3SUM'. Given three sets of integers A, B, and C of total size n, are there a in A, b in B and c in C such that a + b = c? Prove that 3SUM linear-time reduces to 3SUM' and vice versa.
Solution. To show that 3SUM reduces to 3SUM', set A = S, B = S, and C = -S.
To show that 3SUM' reduces to 3SUM, assume that all integers are positive (if not, add k to each element in A and B and 2K to each element in C). Set m = 2 max(A, B, C). For each element a in A, put a + m in S. For each element b in B, put b in S. For each elemenet in C, put -c -m in S.