Coping with NP-hard problems

Coping with an NP-hard problem means giving up one of three things, because no known algorithm is exact, fast on every input and general at the same time. Keep the exact answer and accept exponential time on small inputs: meet in the middle and branch and bound push that limit far past plain brute force. Keep the exact answer and the speed for the inputs you really have, when they have structure such as a tree, a DAG or small numbers. Or keep the speed and give up the optimum: an approximation algorithm proves that its answer is within a stated factor of the best, such as twice the smallest vertex cover, while a heuristic such as local search usually finds good answers and proves nothing. The worked example takes the first route, subset sum over 36 numbers, with 524,288 half-sums instead of 68,719,476,736 subsets. Whichever route you take, state the guarantee you have.

Three routes, and what each one guarantees

The first question is always whether n is small enough for exponential work: 2²⁰ is about a million, 2⁴⁰ about a trillion. The next is whether your inputs are a special case with a polynomial algorithm. Only then do you trade the optimum for speed, with or without a proof:

The tools of this lesson, one sentence each:

• Meet in the middle lists the subset sums of each half of the input and pairs them, so 2ⁿ work becomes about 2ⁿᐟ² for each half.
• Branch and bound backtracks like a plain search but drops any branch whose optimistic bound cannot beat the best answer found so far.
• Dynamic programming over subsets, such as the Held–Karp algorithm, solves the travelling salesperson problem exactly in O(2ⁿ n²) time.
• The matching algorithm for vertex cover takes both ends of every edge still uncovered, and its cover is never more than twice the smallest.
• Greedy set cover keeps taking the set that covers the most uncovered elements, and stays within about ln n + 1 times the optimum.
• 2-opt removes two edges of a tour and reconnects the two pieces the shorter way, again and again, until no such move helps.
• Integer programming states a problem as linear constraints on whole-number variables and leaves the search to a general solver.

Exact search on 36 numbers: meet in the middle

Subset sum asks for the subset of n numbers whose total comes closest to a target. Deciding whether some subset hits the target exactly is NP-complete, and the O(nW) table of dynamic programming helps only when the numbers are small: with 36 numbers near a billion, W, the target, is close to eight billion. Trying every subset costs 2ⁿ sums. Meet in the middle, from Ellis Horowitz and Sartaj Sahni, splits the numbers into two halves of n/2, lists the 2ⁿᐟ² subset sums of each half, and sorts one list. For every sum s of the other half, the best partner is the sorted sum closest to target − s, which a binary search finds. The program runs both methods at n = 20, where they must agree, and meet in the middle alone at n = 36:

# Subset sum over 36 numbers near a billion: which subset sum comes closest to a target? Trying every subset means
# 2^36 sums. Meet in the middle lists the 2^18 sums of each half, sorts one list, and for every sum of the other
# half looks up the best partner with a binary search. At n = 20 both methods run, and they must agree.
import random
from bisect import bisect_left


def all_sums(items):
    """The sums of all 2^len(items) subsets; bit j of an index says whether item j is in that subset."""
    sums = [0]
    for x in items:
        sums += [s + x for s in sums]
    return sums


def better(s, best, target):
    """Closer to the target wins; on a tie, the smaller sum."""
    return best is None or (abs(s - target), s) < (abs(best - target), best)


def every_subset(nums, target):
    best = None
    for s in all_sums(nums):
        if better(s, best, target):
            best = s
    return best, 2 ** len(nums)


def meet_in_the_middle(nums, target):
    half = len(nums) // 2
    left, right = all_sums(nums[:half]), sorted(all_sums(nums[half:]))
    best = None
    for s in left:
        i = bisect_left(right, target - s)  # the first right sum that reaches the target with s
        for j in (i - 1, i):  # the best partner is just below or at that point
            if 0 <= j < len(right) and better(s + right[j], best, target):
                best = s + right[j]
    return best, len(left) + len(right)


rng = random.Random(36)
nums = [rng.randrange(100_000_000, 1_000_000_000) for _ in range(36)]
for n in (20, 36):
    part = nums[:n]
    target = sum(part) * 2 // 5
    print(f"n = {n}, target {target:,}")
    best, listed = meet_in_the_middle(part, target)
    print(f"  meet in the middle: {listed:,} half-sums listed, closest sum {best:,}, off by {abs(best - target):,}")
    if n <= 20:
        best, tried = every_subset(part, target)
        print(f"  every subset:       {tried:,} sums tried, closest sum {best:,}, off by {abs(best - target):,}")
    else:
        print(f"  every subset would need {2 ** n:,} sums")

n = 20, target 4,122,734,372
  meet in the middle: 2,048 half-sums listed, closest sum 4,122,734,277, off by 95
  every subset:       1,048,576 sums tried, closest sum 4,122,734,277, off by 95
n = 36, target 7,773,804,694
  meet in the middle: 524,288 half-sums listed, closest sum 7,773,804,694, off by 0
  every subset would need 68,719,476,736 sums

At n = 20, every subset meant 1,048,576 sums, and meet in the middle listed 2,048 half-sums; both found the same closest sum, 95 below the target. At n = 36, meet in the middle listed 524,288 half-sums and hit the target exactly, where trying every subset would need 68,719,476,736 sums. The cost is O(2ⁿᐟ² n) time for the listing and the sort, and memory for 2ⁿᐟ² sums, which is what limits the method: about 40 to 50 numbers, against about 25 for every subset.

Practise: the closest subset sum

Write meet in the middle for the closest subset sum. The sample tests include 34 numbers near a trillion, too many for a search of every subset, and compare your answers with a slow search on 300 small lists.

from bisect import bisect_left


def closest_subset_sum(nums, target):
    """The sum of some subset of nums (the empty subset counts) closest to target; on a tie, the smaller sum."""
    # Write meet in the middle here.
    return 0

import random
from itertools import combinations

from closest import closest_subset_sum

BIG = [
    493113784116, 132580534659, 352730161662, 133924420423, 528990724597, 172794715421, 474977204024, 740356142812,
    203744176332, 479134929061, 102622444117, 270838240370, 678758273429, 980839394515, 503989920585, 912844967050,
    875464764886, 168027315632, 528639733939, 284399052225, 442036977465, 517865774538, 333276218569, 594806016691,
    295572531361, 244342064118, 888440858074, 698684003136, 359518668886, 852686342057, 223760290864, 836934969835,
    184820004716, 588817237807,
]


def slow(nums, target):
    best = None
    for size in range(len(nums) + 1):
        for subset in combinations(nums, size):
            s = sum(subset)
            if best is None or (abs(s - target), s) < (abs(best - target), best):
                best = s
    return best


def test_small_cases():
    """small lists: exact hits, everything, nothing, and the empty list"""
    assert closest_subset_sum([3, 34, 4, 12, 5, 2], 9) == 9
    assert closest_subset_sum([3, 34, 4, 12, 5, 2], 100) == 60
    assert closest_subset_sum([1, 2, 4, 8, 16, 32, 64], 77) == 77
    assert closest_subset_sum([], 7) == 0
    assert closest_subset_sum([10], 6) == 10


def test_ties_go_to_the_smaller_sum():
    """when two sums are equally close, the smaller one wins"""
    assert closest_subset_sum([3, 34, 4, 12, 5, 2], 1) == 0
    assert closest_subset_sum([7, 9], 8) == 7
    assert closest_subset_sum([10], 5) == 0


def test_against_a_slow_search():
    """300 random lists of up to 12 numbers give the same answer as trying every subset"""
    rng = random.Random(5)
    for _ in range(300):
        nums = [rng.randint(1, 60) for _ in range(rng.randint(0, 12))]
        target = rng.randint(0, 400)
        assert closest_subset_sum(nums, target) == slow(nums, target), (nums, target)


def test_thirty_four_big_numbers():
    """34 numbers near a trillion: 2^34 subsets are too many, so this needs meet in the middle"""
    assert closest_subset_sum(BIG, 5360110952657) == 5360110952810
    assert closest_subset_sum(BIG, sum(BIG) + 5) == sum(BIG)
    assert closest_subset_sum(BIG, 0) == 0

/** The sum of some subset of nums (the empty subset counts) closest to target; on a tie, the smaller sum. */
export function closestSubsetSum(nums, target) {
  // Write meet in the middle here.
  return 0;
}

import { test, assert } from 'mysmartcopilot:test';
import { closestSubsetSum } from './closest.mjs';

const BIG = [
  493113784116, 132580534659, 352730161662, 133924420423, 528990724597, 172794715421, 474977204024, 740356142812,
  203744176332, 479134929061, 102622444117, 270838240370, 678758273429, 980839394515, 503989920585, 912844967050,
  875464764886, 168027315632, 528639733939, 284399052225, 442036977465, 517865774538, 333276218569, 594806016691,
  295572531361, 244342064118, 888440858074, 698684003136, 359518668886, 852686342057, 223760290864, 836934969835,
  184820004716, 588817237807,
];

function slow(nums, target) {
  let best = null;
  for (let mask = 0; mask < 1 << nums.length; mask++) {
    let s = 0;
    for (let i = 0; i < nums.length; i++) if (mask & (1 << i)) s += nums[i];
    if (best === null || Math.abs(s - target) < Math.abs(best - target) || (Math.abs(s - target) === Math.abs(best - target) && s < best)) best = s;
  }
  return best;
}

test('small lists: exact hits, everything, nothing, and the empty list', () => {
  assert.equal(closestSubsetSum([3, 34, 4, 12, 5, 2], 9), 9);
  assert.equal(closestSubsetSum([3, 34, 4, 12, 5, 2], 100), 60);
  assert.equal(closestSubsetSum([1, 2, 4, 8, 16, 32, 64], 77), 77);
  assert.equal(closestSubsetSum([], 7), 0);
  assert.equal(closestSubsetSum([10], 6), 10);
});

test('when two sums are equally close, the smaller one wins', () => {
  assert.equal(closestSubsetSum([3, 34, 4, 12, 5, 2], 1), 0);
  assert.equal(closestSubsetSum([7, 9], 8), 7);
  assert.equal(closestSubsetSum([10], 5), 0);
});

test('300 random lists of up to 12 numbers give the same answer as trying every subset', () => {
  let seed = 5;
  const next = (n) => {
    seed = (seed * 48271) % 2147483647;
    return seed % n;
  };
  for (let k = 0; k < 300; k++) {
    const nums = Array.from({ length: next(13) }, () => 1 + next(60));
    const target = next(401);
    assert.equal(closestSubsetSum(nums, target), slow(nums, target), JSON.stringify([nums, target]));
  }
});

test('34 numbers near a trillion: 2^34 subsets are too many, so this needs meet in the middle', () => {
  const total = BIG.reduce((a, b) => a + b, 0);
  assert.equal(closestSubsetSum(BIG, 5360110952657), 5360110952810);
  assert.equal(closestSubsetSum(BIG, total + 5), total);
  assert.equal(closestSubsetSum(BIG, 0), 0);
});

Branch and bound measured, and the inputs where its bound fails Pro: opens with a Pro, Premium or Ultimate pass

Approximation with proofs: vertex cover and set cover, measured Pro: opens with a Pro, Premium or Ultimate pass

Local search with honest expectations: 2-opt on 200 points Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• An NP-hard problem forces a choice: exact but exponential, fast for a special structure, or fast with only an approximate or heuristic answer.
• Meet in the middle turns 2ⁿ subsets into two lists of 2ⁿᐟ² sums: 524,288 half-sums instead of 68,719,476,736 subsets for 36 numbers.
• Branch and bound, approximation algorithms and local search each come with a different kind of promise: the optimum, a factor, or nothing in advance.
• State the guarantee with every answer: exact, within a proven factor, or measured against a lower bound.