Reduction. Algorithm Series

Reduction is a basic technique in algorithm design.

A problem A reduces to problem B if we can use an algorithm that solves B to develop an algorithm that solves A.

This concept should be pretty familiar in software development. For example, when you use method evaluate() of Apache Commons library to solve a problem, your problem is reduced to the one solved by library method.

Simple example of reduction would be finding a median in a collection. This operation is a common computation in statistics and in various other data-processing applications.

Finding a median can be reduced to Sorting.

Let’s start with Unit tests that will check two main cases:

• if sorted collection has an odd number of values, the median is the middle value
• if sorted collection has an even number of values, the median is the average of the two middle values.

    @Test
    void valueInTheMiddleWhenNumOfObservationsIsOdd() {
        List<Double> dataset = Arrays.asList(12.5, 18.3, 11.2, 19.0, 22.1, 14.3, 16.2, 12.5, 17.8, 16.5, 12.5);

        Double median = Median.getMedian(dataset);

        assertEquals(16.2, median);
    }

    @Test
    void averageOfMiddleWhenNumOfObservationsIsEven() {
        List<Double> dataset = Arrays.asList(12.5, 18.3, 11.2, 19.0, 14.3, 16.2, 12.5, 17.8, 16.5, 12.5);

        Double median = Median.getMedian(dataset);

        assertEquals(15.25, median);

    }

After test cases are defined, writing implementation (can be found on GitHub) is pretty easy.

    public static Double getMedian(List<Double> input) {
        Collections.sort(input);
        int size = input.size();
        
        if (size % 2 == 0) {
            return (input.get(size / 2) + input.get(size / 2 - 1)) / 2;
        } else {
            return input.get(size / 2);
        }
    }

To solve “Finding the median” we used Sorting reduction. Efficient sorting algorithm is useful for efficiently solving many problems. Among them:

• Distinct values - determine the number of distinct values in a set of numbers.
• Scheduling to minimize average completion time - how to schedule set of jobs on a single processor so as to minimize their average completion time?

A large number of important problems can be solved applying Shortest-paths and Maxflow reductions. Let’s mention them here.

Shortest-paths reductions

• Single-source shortest paths in undirected graphs - is there a path from source to a given target vertex?
• Arbitrage - find an arbitrage opportunity in a given table of currency-conversion rates.

Maxflow reductions

• Job placement. A college’s job-placement office arranges interviews for a set of students with a set of companies. What is the maximum number of jobs that can be filled?
• Product distribution. A company that manufactures a single product has factories, where the product is produced; distribution centers, where the product is stored temporarily; and retail outlets, where the product is sold. Is it possible to get the product from the warehouses to the retail outlets such that supply meets demand everywhere?

Reduction plays important role in studying relationships between diverse problems. Many of the problems seem to be unrelated directly, but at the same time can be reduced to sorting, shortest-paths, maxflow, etc.

Sources:

1. Algorithms by Robert Sedgewick.
2. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.