Fractional Programming: Binary Search on a Ratio

Fractional programming is an extension topic beyond most interviews; it pays off in hard OA problems that ask for the best ratio or average: the maximum average of a subarray of length at least k, the best value-per-weight subset of a fixed size, a spanning tree or cycle with the best cost ratio.

Intuition

We want to choose items (a subarray, a subset, a tree) to maximize R = sum(a) / sum(b), where every b is positive. Ratios are awkward to optimize directly, because adding an item can raise or lower the ratio depending on what else is chosen. The trick is to guess the answer λ and ask a simpler question:

Is there a choice with sum(a) / sum(b) >= λ ?
  <=>  is there a choice with sum(a) - λ * sum(b) >= 0 ?
  <=>  is max over choices of sum(a_i - λ * b_i) >= 0 ?

The last form is a plain sum with per-item weights a_i - λ * b_i, which is usually easy to maximize: take the k largest weights, find the best subarray, run a knapsack or a minimum spanning tree with those weights. The answer to the question is "yes" for every λ up to the optimum and "no" above it, so binary search on λ finds the optimum.

Dinkelbach's method replaces the binary search with a fixed-point iteration: start from any feasible ratio λ, pick the choice that maximizes sum(a - λ b), and set λ to that choice's actual ratio. The ratio strictly increases until the maximum of sum(a - λ b) is exactly 0, which happens at the optimum. It usually needs only a handful of rounds, and with exact fractions it returns the exact answer.

When to use it in interviews / OAs

• "Maximum average subarray with length at least k" (with exactly k it is just a sliding window).
• "Choose k items maximizing total value divided by total weight", or "minimize cost per unit", "best efficiency ratio".
• A ratio objective on top of a classic structure: a ratio spanning tree (MST with weights a - λb), a minimum mean cycle (detect a negative cycle with weights w - λ), a ratio knapsack with a lower bound on total weight (0/1 knapsack in the check).
• The statement asks for a real-valued answer within an absolute or relative error such as 1e-5.

Template

Exactly k items: binary search and Dinkelbach

With exactly k items, the best choice for a fixed λ is simply the k largest values of a_i - λ * b_i:

def max_ratio_k_items_bs(a: list[int], b: list[int], k: int) -> float:
    """Max of sum(a)/sum(b) over exactly k items (all b > 0), by binary search on the answer."""
    def feasible(lam: float) -> bool:
        weights = sorted((x - lam * y for x, y in zip(a, b)), reverse=True)
        return sum(weights[:k]) >= 0

    ratios = [x / y for x, y in zip(a, b)]
    lo, hi = min(ratios) - 1, max(ratios) + 1  # any set's ratio lies between the extreme single ratios
    for _ in range(100):  # fixed iteration count instead of an epsilon loop
        mid = (lo + hi) / 2
        if feasible(mid):
            lo = mid
        else:
            hi = mid
    return lo

from fractions import Fraction


def max_ratio_k_items(a: list[int], b: list[int], k: int) -> Fraction:
    """Same problem, exact answer by Dinkelbach iteration."""
    lam = Fraction(0)
    while True:
        chosen = sorted(range(len(a)), key=lambda i: a[i] - lam * b[i], reverse=True)[:k]
        ratio = Fraction(sum(a[i] for i in chosen), sum(b[i] for i in chosen))
        if ratio == lam:  # max of sum(a - lam * b) is 0: lam is optimal
            return lam
        lam = ratio  # strictly larger than before from the second round on

The first round may move λ down (it starts from an arbitrary 0); from then on every λ is the ratio of a real choice, so it can only increase, and there are finitely many choices.

Maximum average subarray of length at least k

For a guess λ, subtract λ from every element; a subarray with average at least λ is a subarray with non-negative sum. With prefix sums P, we need P[j] - P[i] >= 0 for some j - i >= k, so keep the minimum of P[0..j-k] while scanning:

def max_average_subarray(nums: list[int], k: int) -> float:
    def feasible(lam: float) -> bool:
        prefix = 0.0         # P[j] for the shifted values
        lagged = 0.0         # P[j - k]
        min_lagged = 0.0     # min of P[0..j-k]
        for j, x in enumerate(nums, 1):
            prefix += x - lam
            if j >= k:
                if j > k:
                    lagged += nums[j - k - 1] - lam
                    min_lagged = min(min_lagged, lagged)
                if prefix - min_lagged >= 0:
                    return True
        return False

    lo, hi = float(min(nums)), float(max(nums))
    for _ in range(100):
        mid = (lo + hi) / 2
        if feasible(mid):
            lo = mid
        else:
            hi = mid
    return lo

The answer always lies between the smallest and the largest element, which gives tight starting bounds.

Complexity

• Binary search: O(I * C), where I is the number of iterations (40 to 100 for double precision) and C the cost of one check. The k-items check is O(n log n) (O(n) with selection); the subarray check is O(n).
• Dinkelbach: same check cost per round, usually very few rounds; with Fraction the numbers can grow, so it suits moderate inputs or problems that need the exact value.
• Ratio spanning tree: O(I * MST); minimum mean cycle via negative-cycle checks: O(I * V * E).

Common pitfalls

• Wrong direction of the check. For maximizing, max sum(a - λb) >= 0 means "λ is achievable, move up". For minimizing a ratio, use min sum(a - λb) <= 0 and move down.
• Bounds that exclude the answer. Derive them from the data (the extreme single-item ratios, or min and max elements for averages).
• Epsilon loops. while hi - lo > 1e-9 can fail to terminate with large magnitudes; a fixed number of halvings is safer.
• Zero or negative denominators. The method assumes sum(b) > 0 for every feasible choice.
• Greedy checks that ignore constraints. "Take every positive weight" is only valid when any subset is allowed; with "exactly k" take the top k, with "total b at least W" you need a knapsack.
• Precision of the output. Print or compare with the tolerance the problem specifies, not with == on floats.

Interview variations

• Maximum average subarray I (length exactly k): a sliding window, no fractional programming needed.
• Maximum average subarray II (length at least k): the binary search above.
• K-th smallest prime fraction and minimum cost to hire k workers: ratio problems solved by sorting by ratio plus a heap, or by binary search on the ratio with counting.
• Best ratio subset with a weight floor: binary search plus 0/1 knapsack in the check.
• Minimum ratio spanning tree and minimum mean cycle: binary search plus MST or Bellman-Ford; beyond typical interview scope.