08 Subset Sum, Knapsack, Longest Increasing Subsequence

Lecture from: 31.10.2024 | Video: Videos ETHZ | Rui Zhangs Notes | Official Script

Subset Sum Problem

The Subset Sum problem presents a classic combinatorial challenge: given a set of non-negative integers and a target sum, determine if a subset of the given numbers adds up precisely to the target.

Formal Definition:

• Input: A set (represented as an array) $A=\{a_1,a_2,\dots ,a_n\}$ of non-negative integers and a target sum $b$, where $a_i,b\in \mathbb{N}$ for all $1\le i\le n$.
• Output: A subset of indices $I\subseteq \{1,2,\dots ,n\}$ such that ${\sum }_{i\in I}{a}_i=b$. If no such subset exists, return an indication that no solution exists.

The Subset Sum problem finds applications in various real-world scenarios. Imagine an operating system needing to distribute tasks (each with a specific CPU time requirement) among multiple processors. The Subset Sum problem can help determine if a balanced workload distribution is possible, aiming to maximize processor utilization while minimizing idle time. For instance, if two processors are available, and the sum of all task CPU times is 22 units, we could check if a subset sums to 11 units to assign to each processor.

Naive Approach: Exhaustive Search

A straightforward, albeit computationally expensive, approach to solving the Subset Sum problem involves examining all possible subsets of the input set $A$. This effectively means traversing the power set of $A$ (the set of all subsets, including the empty set and $A$ itself).

For each subset, we calculate the sum of its elements and compare it to the target sum $b$. If a match is found, we return the corresponding subset as a solution. If no subset sums to $b$ after checking all possibilities, we conclude that no solution exists.

Runtime Analysis:

The power set of a set with $n$ elements contains $2^n$ subsets. Therefore, in the worst case, our naive algorithm would need to examine all $2^n$ subsets. This leads to an exponential runtime complexity of $O(2^n)$. The naive approach suffers from redundant computations. Many subsets share common sub-sums, which are repeatedly recalculated.

Dynamic Programming Approach

Note for readers: I suggest watching this…

Dynamic programming offers a significantly more efficient solution to the Subset Sum problem by avoiding redundant calculations inherent in the naive approach. This is achieved by breaking down the problem into smaller, overlapping subproblems and storing their solutions to reuse later.

Subproblem Definition

Instead of directly determining whether a subset sum exists for the entire array $A[1\dots n]$, we consider the possible subset sums achievable using only the first $i$ elements, $A[1\dots i]$.

Formally, we define our subproblem as follows:

In essence, $T(i,s)$ is a boolean function indicating whether a subset sum of $s$ can be formed using elements from the subarray $A[1\dots i]$.

Recursive Relation

Now, let’s establish the recursive relationship that allows us to compute $T(i,s)$ based on the solutions to smaller subproblems. Given the values of $T(i-1,s^{\prime })$ for all $s^{\prime }$, how can we determine $T(i,s)$?

We have two options to consider:

1. Exclude $a_i$: If $s$ is already a subset sum using elements from $A[1\dots i-1]$, then $T(i,s)=1$. This is captured by $T(i-1,s)$.

2. Include $a_i$: If $s$ is not a subset sum using only $A[1\dots i-1]$, but $s-a_i$ is, then we can include $a_i$ to achieve the target sum $s$. This means $T(i,s)=1$ if $T(i-1,s-a_i)=1$.

Combining these two cases, we get the following recurrence relation: $T(i,s)=T(i-1,s)\vee T(i-1,s-a_i)$ Note that if $s-a_i<0$, we simply consider the term $T(i-1,s-a_i)$ to be 0, effectively excluding this impossible case.

The base cases for our dynamic programming table $T(i,s)$ are used for initializing the recursion correctly:

• $T(i,0)=1$ for all $0\le i\le n$: This signifies that a subset sum of $0$ is always achievable, regardless of how many elements of $A$ we consider. We can simply take the empty subset (containing no elements), and its sum will be $0$.
• $T(0,s)=0$ for all $s\ge 1$: This states that if we are not allowed to use any elements from the array $A$ (i.e., $i=0$), then it’s impossible to achieve any positive subset sum $s$. Since we’re dealing with non-negative integers, no combination of no elements can sum to a positive value.

Bottom Up Approach: With these base cases defined, we can now proceed to fill the entire dynamic programming table using the recursive relation, ultimately determining whether the target sum $b$ is achievable using elements from $A$.

While the bottom-up approach systematically fills the entire dynamic programming table $T(i,s)$, it can lead to redundant computations, especially if the target sum $b$ is relatively small compared to the potential range of subset sums. A top-down (memoized) recursive approach can be more efficient in such cases by computing only the necessary table entries.

Top-Down (Memoized) Approach:

The top-down approach starts with the original problem ($T(n,b)$) and recursively breaks it down into smaller subproblems. Crucially, it uses memoization to store the results of these subproblems. Before computing any $T(i,s)$, we check if its value has already been stored in the memoization table (often implemented as a dictionary or a 2D array). If it has, we simply retrieve the stored value, avoiding recomputation. Otherwise, we compute the value using the recursive relation and store it before returning.

Pseudocode (Python):

def subset_sum(A, b):
	n = len(A)
	memo = {} # Initialize memoization table (dictionary)
	
	def T(i, s):
		if (i, s) in memo:
			return memo[(i, s)]
		
		if s == 0:
			return 1
		if i == 0 and s > 0:
			return 0
		
		res = T(i - 1, s)
		if s - A[i-1] >= 0:
			res = res or T(i - 1, s - A[i-1])
		
		memo[(i, s)] = res
		return res
 
	return T(n, b)

Advantages of Top-Down:

Avoids calculating entries in $T$ that are never needed to determine $T(n,b)$. If you suspect a large portion of the DP table will not be needed, top-down can be more efficient.

Advantages of Bottom-Up:

Can be slightly faster for problems where most subproblems need to be computed anyway. Bottom-up might be a simpler and slightly faster choice for large problems.

Runtime Analysis

The dynamic programming approach we’ve outlined has a time complexity of $\Theta (n\cdot b)$, where $n$ is the number of elements in the input array $A$, and $b$ is the target sum. This comes from filling a dynamic programming table $T$ of size $(n+1)\times (b+1)$.

Pseudo-Polynomial Runtime:

It’s crucial to understand that this runtime is pseudo-polynomial. While expressed as a product of $n$ and $b$, the parameter $b$ represents a number in the input, not the input size itself. The actual input size is determined by the number of bits required to represent all the input numbers.

Here’s why this distinction matters:

• Representing the $n$ elements of array $A$ requires at least $n$ units of space. We cannot represent $n$ distinct elements in less than $n$ units of space.
• The target sum $b$ requires roughly $\log b$ bits to represent its value.

Therefore, the total input size can be approximated as $\Theta (n+\log b)$. If $b$ is relatively small compared to $n$ (e.g., $b\le n^c$ for some constant $c$), the $\log b$ term is dominated by the $n$ term, and the dynamic programming algorithm effectively behaves like a polynomial-time algorithm.

However, if $b$ is exponentially large compared to $n$ (e.g., $b=2^n$), the runtime becomes $\Theta (n\cdot 2^n)$. The input size is $\Theta (n+\log b)=\Theta (n+n)=\Theta (n)$. This runtime is now exponential in $n$, the length of the input. This is the characteristic of a pseudo-polynomial runtime: it’s polynomial in the magnitude of the input numbers but exponential in the length of their representation (number of bits).

Lower Bound:

A trivial lower bound for this problem is the time required to read the input, which is $\Theta (n+\log b)$. In the case where $b=2^n$, this input reading runtime becomes $\Theta (n)$.

Our dynamic programming algorithm’s $\Theta (n{2}^n)$ runtime significantly exceeds this lower bound. It’s not simply processing each input bit a fixed number of times ; instead, the number of operations grows exponentially with the input size. This contrasts true polynomial-time algorithms where the number of operations is bounded by a polynomial function of the number of input bits.

Knapsack Problem

The Knapsack Problem is a classic optimization problem in which we aim to maximize profit while adhering to a weight constraint. Imagine you have a knapsack with a limited weight capacity, and you’re presented with various items, each having a specific weight and profit. The goal is to select a subset of items that maximizes the total profit within the knapsack’s weight restriction.

Input:

• A set of $n$ items, each with a weight $w_i$ and a profit $p_i$, where $w_i,p_i\in \mathbb{N}$ for $1\le i\le n$.
• A knapsack with a maximum weight capacity $W\in \mathbb{N}$.

Output:

• A subset of items $S\subseteq \{1,2,\dots ,n\}$ such that:
• The total weight of the selected items does not exceed the knapsack capacity: ${\sum }_{i\in S}{w}_i\le W$
• The total profit of the selected items is maximized: ${\sum }_{i\in S}{p}_i$ is maximal among all valid subsets.

Example:

Consider a knapsack with a capacity of $W=10$ and the following items:

A possible solution is selecting items 1 and 4 (total weight = 8, total profit = 8). A better solution, however, is selecting items 1 and 2 (total weight = 9, total profit = 9). The challenge lies in finding the optimal combination.

Failing Approaches

Several seemingly intuitive approaches fall short of optimally solving the Knapsack Problem:

• Greedy Approach (Maximum Profit First): Selecting items with the highest profit first might seem reasonable, but it can lead to suboptimal solutions. High-profit items could quickly fill the knapsack, leaving space for potentially more profitable combinations of smaller items.

• Greedy Approach (Minimum Weight First): Prioritizing lightweight items allows fitting more items, but these might not necessarily yield the highest overall profit.

• Greedy Approach (Maximum Profit/Weight Ratio): Choosing items with the highest profit-to-weight ratio can be better than the previous two greedy strategies but still doesn’t guarantee optimality. The discrete nature of the Knapsack problem means that fractional values of items cannot be taken. This fractional amount could correspond to a more profitable option.

These greedy approaches are efficient but often fail to find the absolute best solution because they don’t consider all possible combinations of items. Dynamic programming, however, provides a structured way to explore these combinations systematically.

Dynamic Programming Approach

Dynamic programming provides an optimal solution to the Knapsack Problem by breaking it down into smaller, overlapping subproblems and storing their solutions to avoid redundant computations. This will be a 2D DP approach.

Subproblem Definition

The core of our dynamic programming approach lies in defining the right subproblem. We aim to capture the essence of the Knapsack Problem but for a smaller subset of items and a potentially reduced weight capacity. This allows us to build up the solution incrementally.

Formally, we define our subproblem as:

$P(i,w):=$ the maximum profit achievable using a subset of items from the set $\{1,2,\dots ,i\}$ with a total weight not exceeding $w$.

In simpler terms, $P(i,w)$ represents the best profit we can get if we only consider the first $i$ items and have a knapsack with a capacity of $w$.

Recursive Relation

Note for readers: Check this video for a great explanation…

This subproblem allows us to create a recursive relationship. Consider the $i$-th item: we either include it in the knapsack or not.

• If we include item $i$: We gain a profit of $p_i$ but reduce our available weight capacity to $w-w_i$. The remaining profit comes from optimally selecting items from the set $\{1,2,\dots ,i-1\}$ with the reduced weight capacity. This is represented by $P(i-1,w-w_i)$. The total profit in this case becomes $p_i+P(i-1,w-w_i)$.

• If we don’t include item $i$: Our available weight capacity remains $w$, and the maximum profit we can obtain is the same as the maximum profit achievable using only the first $i-1$ items, which is $P(i-1,w)$.

We choose the better of these two options, leading to the recursive relationship:

$P(i,w)=\max \{P(i-1,w),p_i+P(i-1,w-w_i)\}$

It’s important to handle the case where $w-w_i<0$ (we can’t include item $i$ if its weight exceeds the current capacity). In such a case, the second term of the $\max$ function is considered to be $-\infty$, effectively making $P(i-1,w)$ the chosen value.

Runtime Analysis

The dynamic programming approach to the Knapsack Problem involves filling a table $P$ of size $(n+1)\times (W+1)$, where $n$ is the number of items and $W$ is the knapsack’s weight capacity. This leads to a time complexity of $\Theta (nW)$.

Pseudo-Polynomial Time:

Similar to the Subset Sum problem, the Knapsack Problem’s dynamic programming solution has a pseudo-polynomial runtime. The runtime is polynomial in the numerical value of $W$, but not necessarily in the size of the input (number of bits needed to represent the input).

• Representing the $n$ items requires $\Theta (n)$ space (for their weights and profits).
• Representing the capacity $W$ takes $\Theta (\log W)$ bits.

The total input size is therefore $\Theta (n+\log W)$. If $W$ is relatively small compared to $n$ (e.g., $W\le n^c$ for some constant $c$), the dynamic programming algorithm behaves effectively like a polynomial-time algorithm.

However, if $W$ is exponentially large compared to $n$ (e.g., $W=2^n$), the runtime becomes $\Theta (n\cdot 2^n)$, while the input size is $\Theta (n+n)=\Theta (n)$. This runtime is exponential in the input size. This is the characteristic of a pseudo-polynomial runtime: polynomial in the magnitude of the input numbers ($W$), but potentially exponential in the length of their representation ($\log W$).

Implications:

The pseudo-polynomial nature of the runtime means that the dynamic programming approach is efficient for instances where $W$ is not excessively large. However, for very large values of $W$, the runtime can become prohibitive. This is a crucial consideration when applying dynamic programming to the Knapsack Problem. Alternative algorithms might be necessary for instances with exponentially large $W$.

Alternative Subproblem Definition

While the previous dynamic programming approach focused on maximizing profit for a given weight limit, we can formulate an alternative subproblem that focuses on minimizing weight for a given profit target. This can be particularly useful when we are primarily concerned with achieving a certain profit level and want to minimize the resources (weight) used.

Formally, let’s define the alternative subproblem as:

$G(i,p):=$ the minimum weight required to achieve a profit of at least $p$ using a subset of items from the set $\{1,2,\dots ,i\}$.

In other words, $G(i,p)$ represents the smallest knapsack capacity needed to achieve a profit of $p$ or more, considering only the first $i$ items. If it’s impossible to reach a profit of $p$ using any combination of the first $i$ items, we set $G(i,p)=\infty$.

Recursive Relation

Similar to our previous approach, we can derive a recursive relationship for this subproblem:

$G(i,p)=\min \{G(i-1,p),G(i-1,p-p_i)+w_i\}$

Here’s the breakdown:

• If we don’t include item $i$: The minimum weight required to achieve a profit of $p$ remains the same as using only the first $i-1$ items, which is $G(i-1,p)$.

• If we include item $i$: We gain a profit of $p_i$. Therefore, we need to achieve a profit of at least $p-p_i$ using the remaining $i-1$ items. The weight required for this is $G(i-1,p-p_i)$. Adding the weight of item $i$ ($w_i$) gives us the total weight in this case: $G(i-1,p-p_i)+w_i$.

As before, we select the minimum of these two options. We must handle the case where $p-p_i<0$. In this situation, $G(i-1,p-p_i)$ is considered to be 0 if $p-p_i=0$ and $\infty$ if $p-p_i<0$.

Base Cases:

• $G(0,0)=0$: If we have no items and want zero profit, zero weight is sufficient.
• $G(0,p)=\infty$ for $p>0$: We cannot achieve any positive profit with no items.
• $G(i,0)=0$ for all $i$: We can achieve zero profit using zero weight, simply by not taking any items, regardless of the number of available items.

Using this approach:

After filling the $G$ table using the recursive relation and base cases, we find the optimal solution by determining the maximum $p$ such that $G(n,p)\le W$. This represents the maximum profit we can achieve within the knapsack’s weight capacity.

Runtime Analysis

This alternative dynamic programming approach involves filling a table $G$ of size $(n+1)\times (P+1)$, where $n$ is the number of items and $P$ is the maximum possible total profit achievable, summing over all the items profits. In other words: $P={\sum }_{i=1}^n{p}_i$This assumes that all items could potentially be included. This leads to a time complexity of $\Theta (nP)$.

Pseudo-Polynomial Time:

Similar to the first dynamic programming approach, this alternative approach also has a pseudo-polynomial runtime. The runtime is polynomial in the numerical value of $P$, but not necessarily in the input size (number of bits to represent the input).

• Representing the $n$ items takes $\Theta (n)$ space (for weights and profits).
• Representing the total profit $P$ requires $\Theta (\log P)$ bits. However, because $P$ is derived from the sum of profits of the $n$ items, each represented by $\log (p_i)$ bits, it could be as large as $n\times \max (\log p_i)$, it will usually be smaller since individual profit values are smaller than their sum. Nevertheless, $P$ can potentially be exponential in the input size.

The total input size is $\Theta (n+{\sum }_{i=1}^n\log p_i+\log W)$. If the individual profits and $W$ are bounded in relation to $n$, the runtime can be considered polynomial in practice.

However, if $P$ grows exponentially with $n$, or if the individual profit values are significantly larger than $W$ and $n$, then the runtime could become $\Theta (n\cdot P)$, which would then be dominated by the profit values. Then the algorithm behaves exponentially with the input size, similar to the previous dynamic programming approach.

Comparison

The choice between the two dynamic programming approaches depends on the specific problem instance:

• If the knapsack capacity $W$ is relatively small compared to the potential total profit $P$, the first approach ($P(i,w)$) is generally more efficient.
• If the maximum possible profit $P$ is relatively small compared to the capacity $W$, this alternative approach ($G(i,p)$) can be more advantageous.

In situations where both $W$ and $P$ are large, other algorithms, or approximations, might be needed to tackle the problem effectively.

Can We Do Better? P vs. NP and the Knapsack Problem

We’ve seen two dynamic programming approaches to the Knapsack Problem, both with pseudo-polynomial runtimes. This means their efficiency depends on the magnitude of the input numbers (capacity $W$ or maximum profit $P$), not just the number of items $n$. A natural question arises: can we find an algorithm with a runtime truly polynomial in the input size, meaning polynomial in $n$ and $\log W$ (or $\log P$)?

The prevailing conjecture is no. This relates to the famous P vs. NP problem, one of the most fundamental unsolved questions in computer science and mathematics.

P (Polynomial Time): The class of decision problems solvable by a deterministic algorithm in polynomial time. This means the runtime is polynomial in the size of the input (number of bits).

NP (Nondeterministic Polynomial Time): The class of decision problems where a proposed solution can be verified in polynomial time. The Knapsack Problem, framed as a decision problem (“Is there a subset of items with total weight ≤ W and profit ≥ p?”), is in NP. Given a subset of items, we can quickly check if its weight is within the limit and calculate its profit.

NP-hard: A problem is NP-hard if every problem in NP can be reduced to it in polynomial time. If we could solve an NP-hard problem in polynomial time, we could solve every problem in NP in polynomial time.

NP-complete: A problem is NP-complete if it is both NP-hard and in NP. These problems are, in a sense, the “hardest” problems in NP.

The Knapsack Problem and NP-Completeness:

The Knapsack Problem is NP-complete. This means:

1. It’s in NP (we can verify solutions efficiently).
2. It’s NP-hard (if we could solve it in polynomial time, P would equal NP).

If either the Subset Sum or Knapsack problems could be solved in polynomial time, then $P=NP$. This is a profound statement because it implies that a fast algorithm for Knapsack would revolutionize computer science. We could solve thousands of other NP-complete problems efficiently, problems currently believed to require exponential time in the worst case.

Current State:

The P vs. NP question remains open. While most computer scientists believe $P\ne NP$, no proof exists. If it turns out that $P=NP$, then a truly polynomial-time algorithm for Knapsack (and all other NP-complete problems) would be possible. However, until then, the pseudo-polynomial dynamic programming approaches and approximation algorithms remain the most practical options for the Knapsack Problem.

Approximation Algorithms for the Knapsack Problem

Because finding an exact solution to the Knapsack Problem in polynomial time is highly unlikely (unless $P=NP$), we often use approximation algorithms. These algorithms aim for near-optimal solutions with guaranteed polynomial runtimes.

Note for readers: I’d suggest watching this video to get a idea of what’s happening…

Key Idea: Scaling and Rounding:

One common technique involves scaling and rounding profit values to simplify the problem and speed up dynamic programming.

1. Scale and Round Profits: Choose a scaling factor $K$ (a positive integer). Calculate scaled, rounded profits: $\widehat{p_i}=K\cdot \lfloor \frac{p_i}{K}\rfloor$.

2. Solve Rounded Instance: Apply dynamic programming with the $P(i,w)$ formulation using the rounded profits ${\hat{p}}_i$. Recall that $P(i,w)$ represents the maximum profit achievable using items from the subset $\{1,2,\dots ,i\}$ with a weight limit of $w$. The recursive relation with the rounded profits becomes: $\hat{P}(i,w)=\max \{\hat{P}(i-1,w),\widehat{p_i}+\hat{P}(i-1,w-w_i)\}$.

3. Return Solution: The solution obtained for this rounded instance serves as our approximation.

Also let us assume that all $w_i\le W$. This will become important later on.

Illustrative Example ($K=10$):

Suppose $K=10$, and an item has profit $p_i=42$. Scaling gives $420$. Rounding down results in $\widehat{p_i}=10\cdot \lfloor \frac{42}{10}\rfloor =40$.

How does this affect the $P(i,w)$ dynamic programming table? We’re reducing the granularity of profit values. With rounded profits in multiples of 10, we only compute table entries for profit values that are also multiples of 10. We’re using a coarser grid, focusing on every tenth “column” (representing profit values) in the DP table. The rows (representing items) remain the same. $K=1$ gives us the standard DP algorithm, while larger $K$ increases speed but reduces accuracy.

Let’s clarify the observation regarding profit values and their relationship to the optimal solution in the Knapsack Problem’s approximation algorithm.

Observation:

The key insight for analyzing the approximation guarantee is the following inequality, which holds for each item $i$:

$p_i-K\le \widehat{p_i}\le p_i\le p_{max}\le P_{Optimal}$

Here’s a reminder of what each term represents:

• $p_i$: Original profit of item $i$.
• $\widehat{p_i}$: Scaled and rounded profit of item $i$.
• $K$: Scaling factor.
• $p_{max}$: Maximum profit among all items.
• $P_{Optimal}$: The optimal achievable profit.

Runtime:

The dynamic programming algorithm runs in $O(n\cdot \frac{\hat{P}}{K})$ time, where $\hat{P}$ is the sum of rounded profits which is upper-bounded by $n\cdot p_{max}$. This gives us a runtime of $O(n\cdot \frac{n\cdot p_{max}}{K})=O(n^2\cdot \frac{p_{max}}{K})$.

Accuracy:

How good is this approximated solution? Let $\widehat{OPT}$ be the set of indices returned by our approximation algorithm. The user would calculate the profit using the original profit values: ${\sum }_{i\in \widehat{OPT}}{p}_i$. Let’s analyze this.

Since $\widehat{OPT}$ is optimal for the rounded profits ($\widehat{p_i}$), we know that for any subset of indices $I$ whose total weight fits in the knapsack, the following holds:

${\sum }_{i\in \widehat{OPT}}\widehat{p_i}\ge {\sum }_{i\in I}\widehat{p_i}$

Consider the case where $I=OPT$, representing the true optimal subset (which we don’t know explicitly). The above inequality still holds:

${\sum }_{i\in \widehat{OPT}}\widehat{p_i}\ge {\sum }_{i\in OPT}\widehat{p_i}$

Using our initial observation, we can derive:

${\sum }_{i\in \widehat{OPT}}{p}_i\ge {\sum }_{i\in \widehat{OPT}}\widehat{p_i}\ge {\sum }_{i\in OPT}\widehat{p_i}\ge {\sum }_{i\in OPT}(p_i-K)={\sum }_{i\in OPT}{p}_i-nK$

Since ${\sum }_{i\in OPT}{p}_i=P_{Optimal}$, we have:

${\sum }_{i\in \widehat{OPT}}{p}_i\ge P_{Optimal}-nK=P_{Optimal}(1-\frac{nK}{P_{Optimal}})\ge P_{Optimal}(1-\frac{nk}{p_{max}})$

To control the accuracy, we introduce $ϵ>0$ and set $K=\frac{ϵp_{max}}{n}$. This gives us:

${\sum }_{i\in \widehat{OPT}}{p}_i\ge P_{Optimal}(1-ϵ)$

This shows that our algorithm achieves a $(1-ϵ)$ approximation.

Now, substituting $K$ back into our runtime expression:

$O(\frac{n^2{p}_{max}}{K})=O(\frac{n^2{p}_{max}}{\frac{ϵp_{max}}{n}})=O(\frac{n^3}{ϵ})$

$K$ (and inversely $ϵ$) controls the trade-off between solution quality and runtime. Smaller $ϵ$ (larger K) improves accuracy but increases runtime.

This runtime demonstrates the trade-off between accuracy ($ϵ$) and efficiency. A smaller $ϵ$ (higher accuracy) leads to a longer runtime.

Fully Polynomial Time Approximation Scheme (FPTAS):

As discussed, setting $K=\frac{ϵ\cdot P_{max}}{n}$ yields a $(1-ϵ)$-approximation in $O(\frac{n^3}{ϵ})$ time. This is a Fully Polynomial Time Approximation Scheme (FPTAS), providing arbitrarily good approximations with a runtime polynomial in both $n$ and $\frac{1}{ϵ}$.

Can We Do Better? Geht es besser?

While the FPTAS we’ve described is powerful, its $O(\frac{n^3}{ϵ})$ runtime can still be quite large for practical applications, especially as $n$ grows or a high accuracy (small $ϵ$) is required.

The natural question then arises: can we improve upon this? Yes, indeed, there are more sophisticated algorithms that achieve better time complexities.

A much more complex algorithm exists that runs in $O(n+\frac{1}{{ϵ}^2})$ time, ignoring logarithmic factors. This represents a significant improvement, particularly for large $n$. What’s even more remarkable is that this algorithm is essentially optimal ; we can prove that significant further improvements are unlikely. This algorithm was developed as recently as April 2024, highlighting ongoing research in this area.

Longest Increasing Subsequence (LIS)

Leetcode: Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem involves finding the length of the longest subsequence within a given sequence such that all elements of the subsequence are in strictly increasing order. Note that the elements of the subsequence do not need to be contiguous within the original sequence.

Formal Definition:

• Input: A sequence (often represented as an array) $A=[a_1,a_2,\dots ,a_n]$ of numbers. For simplicity, let’s assume all numbers in $A$ are unique.
• Output: The length of the longest strictly increasing subsequence in $A$. A subsequence is a sequence that can be derived from $A$ by deleting some or no elements without changing the order of the remaining elements.

A first idea

Let’s explore a first attempt at defining a subproblem for the LIS problem and see why it falls short.

We might initially define the subproblem as follows:

$LIS(i):=$ the length of the longest increasing subsequence ending at index $i$. We would then return the maximum value of $LIS(i)$.

Let’s consider the example $A=[1,8,9,5,6,7]$ and see how this subproblem definition works:

• $LIS(1)=1$ (the LIS ending at index 1 is just $[1]$)
• $LIS(2)=2$ (the LIS ending at index 2 is $[1,8]$)
• $LIS(3)=3$ (the LIS ending at index 3 is $[1,8,9]$)
• $LIS(4)=3$ (the LIS ending at index 4 is $[1,8,9]$)
• $LIS(5)=3$ (the LIS ending at index 5 is $[1,8,9]$)
• $LIS(6)=4$ (the LIS ending at index 6 is $[1,5,6,7]$)

If you observe this, it’s trivial to see that the $LIS(i-1)$ doesn’t hint us what $LIS(i)$ might be. For example, $LIS(4)$ and $LIS(5)$ both have the same value, despite their indexes being adjacent in the sequence.

This subproblem definition, while seemingly intuitive, is not sufficient for efficiently finding the overall LIS. We need a more robust subproblem definition that captures the global nature of the LIS.

Brute Force

Let’s refine our subproblem definition further. This approach won’t be the most efficient, but it brings us closer to the optimal solution and helps illustrate the thought process.

Define the subproblem as follows:

$E(i,l):=$ Does there exist an increasing subsequence of length $l$ that ends at index $i$? (This will be a boolean value, 1 if true and 0 if false)

Recursive Relation:

1. Base Case: $l=1$: $E(i,1)=1$ for all $1\le i\le n$. Any single element constitutes an increasing subsequence of length 1.

2. Recursive Step: $l>1$: An increasing subsequence of length $l$ ending at index $i$ can be formed if there exists an increasing subsequence of length $l-1$ ending at some index $j<i$ such that $A[j]<A[i]$. We can express this recursively as:

Runtime Analysis:

The size of the $E$ table is $n\times n$. For each entry $E(i,l)$, we might need to check up to $i-1$ previous entries in the $E$ table. This leads to a time complexity of $O(n^3)$. This is because the exists step can be quite costly).

Dynamic Programming: $O(n^2)$

This approach focuses on efficiently determining the smallest possible ending value for an increasing subsequence of a given length.

Subproblem Definition

Define the subproblem as follows:

$M(i,l):=$ The smallest ending value of an increasing subsequence of length $l$ considering only the elements $A[1\dots i]$. If no increasing subsequence of length $l$ exists using these elements, set $M(i,l)=\infty$.

Recursive Relation

The value of $M(i,l)$ can be determined by considering whether or not the element $A[i]$ can extend an existing increasing subsequence.

Let’s break this down:

• Case 1: $M(i-1,l-1)<A[i]<M(i-1,l)$: If $A[i]$ is greater than the smallest ending value of a subsequence of length $l-1$ (meaning we can potentially extend a subsequence) and is smaller than the current smallest ending value for subsequences of length $l$, then including $A[i]$ creates a new LIS of length $l$ with a smaller ending value. We update $M(i,l)$ to $A[i]$.
• Case 2 (Otherwise): If the condition in Case 1 is not met, either we can’t extend any subsequence of length $l-1$ with $A[i]$, or including $A[i]$ doesn’t create a smaller ending value for a subsequence of length $l$. In this case, the smallest ending value remains the same as $M(i-1,l)$.

Base Cases:

This establishes the foundation for calculating $M(i,l)$ for larger $i$ and $l$.

Runtime Analysis

The $M$ table has dimensions $(n+1)\times (n+1)$, and filling each entry takes constant time ($O(1)$). The runtime of this dynamic programming approach is therefore $O(n^2)$.

Example:

Observations:

• All the rows are sorted
• We are only changing one value per row
  • We can find that entry in $O(\log n)$
  • This means we’ll not write a 2D DP Table but instead us the same array n times
  • This will mean we’ll get a runtime of $O(n\log n)$

Dynamic Programming: $O(n\log n)$

This approach optimizes the previous DP approach by utilizing binary search, leading to a significant improvement in runtime.

Subproblem Definition

This is the same as in DP Approach 3:

• $M(i,l):=$ The smallest ending value of an increasing subsequence of length $l$ considering only the elements $A[1\dots i]$. If no increasing subsequence of length $l$ exists using these elements, set $M(i,l)=\infty$.

Key Insight: Instead of storing the entire $M$ table, we can maintain a single array, tails, of size $n+1$. This array tails[l] stores the smallest ending value of all increasing subsequences of length l.

Note for readers: Good video explaining this specific ($O(n\log n)$ algorithm)

Recursive Relation

We iterate through the input array A, processing each element A[i]. For each A[i], we perform a binary search in the tails array to find the largest index j where tails[j] < A[i]. This implies that we can extend an increasing subsequence of length j by adding A[i].

Algorithm

1. Initialization: Initialize tails[1] = A[1] and set all other tails[i] to infinity.
2. Iteration: For each element A[i] in the input array:
   • Perform binary search in tails array to find the largest index j where tails[j] < A[i].
   • Update: Set tails[j+1] = A[i]. This means we have found a shorter increasing subsequence ending with A[i].
3. Result: The length of the longest increasing subsequence is the largest index l in tails where tails[l] is not infinity.

Runtime Analysis

• Binary Search: Each binary search operation takes $O(\log n)$ time.
• Iteration: We perform $n$ binary search operations for each element in the input array.

Therefore, the total runtime of this approach is $O(n\log n)$.

Example

Consider the same example as before, A = [1, 8, 9, 5, 6, 7].

1. Initialize tails = [inf, 1, inf, inf, inf, inf, inf].
2. A[1] = 1:
   • Binary search finds j = 1 (since tails[1] < A[1] is false, we need to go one index down)
   • Update tails = [inf, 1, inf, inf, inf, inf, inf]
3. A[2] = 8:
   • Binary search finds j = 1 (since tails[1] < A[2] is true)
   • Update tails = [inf, 1, 8, inf, inf, inf, inf]
4. A[3] = 9:
   • Binary search finds j = 2 (since tails[2] < A[3] is true)
   • Update tails = [inf, 1, 8, 9, inf, inf, inf]
5. A[4] = 5:
   • Binary search finds j = 1 (since tails[1] < A[4] is true)
   • Update tails = [inf, 1, 5, 9, inf, inf, inf]
6. A[5] = 6:
   • Binary search finds j = 2 (since tails[2] < A[5] is true)
   • Update tails = [inf, 1, 5, 6, 9, inf, inf]
7. A[6] = 7:
   • Binary search finds j = 3 (since tails[3] < A[6] is true)
   • Update tails = [inf, 1, 5, 6, 7, 9, inf]

The final tails array contains [inf, 1, 5, 6, 7, 9, inf]. The length of the longest increasing subsequence is the largest index where tails is not infinity, which is 6.

Pseudocode

def longest_increasing_subsequence(arr):
  n = len(arr)
  tails = [float('inf')] * (n + 1)
  tails[1] = arr[0]
  
  for i in range(1, n):
    # Binary search to find the largest index j where tails[j] < arr[i]
    left, right = 1, n
    while left <= right:
      mid = (left + right) // 2
      if tails[mid] < arr[i]:
        left = mid + 1
      else:
        right = mid - 1
    
    # Update tails[j+1] = arr[i]
    tails[left] = arr[i]
 
  # The length of the longest increasing subsequence is the largest index j where tails[j] is not infinity
  for j in range(n, 0, -1):
    if tails[j] != float('inf'):
      return j
 
arr = [1, 8, 9, 5, 6, 7]
result = longest_increasing_subsequence(arr)
print(f"The length of the longest increasing subsequence is: {result}") 

Continue here: 09 Graph Theory, Eulerian Cycle Algorithm