Unit 12: Approximation - Subjective Questions

Definition: An approximation algorithm is a polynomial-time algorithm that produces a feasible solution whose value is provably close to the optimal value.

Need for approximation algorithms:

• Many optimization problems are NP-hard, so no polynomial-time exact algorithm is known.
• Exact algorithms may require exponential time on large inputs.
• Approximation algorithms trade a limited amount of solution quality for computational efficiency.
• They provide a mathematical guarantee on how far the returned solution can be from the optimum.

For example, if a minimization algorithm has approximation ratio , its solution cost satisfies

where is the optimal cost for instance .

Let be the value produced by an approximation algorithm and be the optimal value for instance .

For a minimization problem, a solution cannot be smaller than the optimum. An algorithm is a -approximation if

where .

For a maximization problem, a feasible solution cannot exceed the optimum. An algorithm is a -approximation under the reciprocal convention if

A unified performance ratio is

A ratio closer to indicates a better approximation.

Exact algorithm:

• Always returns an optimal solution.
• May require exponential time for NP-hard problems.
• Its correctness guarantee concerns optimality.

Heuristic:

• Attempts to find a good solution quickly.
• Usually has no proven worst-case quality guarantee.
• Often performs well on typical or practical inputs.

Approximation algorithm:

• Runs in polynomial time.
• Returns a feasible but not necessarily optimal solution.
• Has a formally proved approximation bound.

Thus, approximation algorithms combine the efficiency associated with heuristics and a rigorous solution-quality guarantee, while exact algorithms prioritize optimality regardless of potentially high running time.

Absolute approximation guarantee: A minimization algorithm has absolute ratio if, for every instance ,

The guarantee applies even when the optimal value is small.

Asymptotic approximation guarantee: An algorithm has asymptotic ratio if there is a constant such that

The additive constant becomes relatively insignificant for large values of .

Difference:

• An absolute guarantee provides a direct multiplicative bound on every instance.
• An asymptotic guarantee permits an additive error.
• An algorithm may therefore have a strong asymptotic ratio but a weaker absolute ratio on small instances.

Bin-packing algorithms are commonly analyzed using asymptotic guarantees.

Approximation analysis compares the algorithmic solution with a bound on the unknown optimum.

For minimization problems:

• The feasible solution produced by an algorithm gives an upper bound on .
• A relaxation or structural argument gives a lower bound such that .
• If one proves , then
  

For maximization problems:

• The algorithmic solution is a lower bound on .
• An upper bound on is used to prove solution quality.

Useful lower bounds may come from total workload, the largest item or task, linear programming relaxations, or counting arguments. The tighter the bound, the more informative the performance proof.

A constant-factor approximation algorithm has a fixed performance ratio such as or , independent of a requested accuracy.

A polynomial-time approximation scheme (PTAS) accepts an accuracy parameter and returns a solution within a factor of for minimization, or for maximization. For each fixed , its running time is polynomial in input size , but it may be exponential in .

A fully polynomial-time approximation scheme (FPTAS) is polynomial in both and .

For minimization, a PTAS or FPTAS guarantees

Therefore, schemes permit adjustable accuracy, while a constant-factor algorithm provides one fixed guarantee.

Suppose there are independent tasks with processing times and identical machines. Each task must be assigned to exactly one machine and cannot be split.

The load of machine is

The objective is to minimize the makespan

Two fundamental lower bounds are:

• Average-load bound:
  
• Largest-task bound:
  

Hence,

These bounds are central to analyzing scheduling approximations.

List scheduling algorithm: Process tasks in the given order and assign each task to a currently least-loaded machine.

For two machines and the order :

• Assign to : loads are .
• Assign to : loads are .
• Assign to : loads are .
• Assign to : loads are .
• Assign to either machine: loads become .

Therefore, the produced makespan is

The total processing time is , so the average-load lower bound is . In fact, a schedule with loads exists, such as and . Thus, the approximation ratio on this instance is .

Let task be the task that finishes last in the list schedule, let its processing time be , and let its start time be . Immediately before assigning task , every machine has load at least $s_k`; otherwise the algorithm would have assigned it to a less-loaded machine.

The work scheduled before task is therefore at least . Since the total work excluding task is at most ,

The makespan satisfies

Using

we obtain

Thus, list scheduling is a -approximation algorithm. Its implementation takes time when machine loads are maintained in a min-priority queue.

Longest Processing Time first (LPT) sorts all tasks in non-increasing order of processing time and then repeatedly assigns the next task to a least-loaded machine.

Comparison with ordinary list scheduling:

• Ordinary list scheduling accepts tasks in any given order.
• LPT deliberately places large tasks first, reducing the chance that a large task will be assigned near the end to an already heavily loaded machine.
• List scheduling has approximation ratio
  
• LPT has the stronger bound
  
• LPT requires sorting and therefore typically runs in time.

Both methods use the same least-loaded-machine assignment rule, but LPT obtains a better worst-case guarantee through preprocessing.

The tasks are already arranged in non-increasing order. LPT assigns them as follows:

• Assign to : .
• Assign to : .
• Assign to : .
• Assign to : .
• Assign to : .
• Assign to : .
• Assign to any machine: .

Thus, the LPT makespan is

The total processing time is , giving the lower bound

The schedule is feasible and has instance-specific ratio at most

This comparison uses a lower bound; it does not by itself prove that the optimum equals .

Large tasks have fewer opportunities for correction after they are assigned. If a large task is postponed, all machines may already have substantial loads, forcing the task onto a machine that then determines a high makespan.

Scheduling large tasks first helps because:

• Large tasks are distributed while many machines are still lightly loaded.
• Small tasks can later fill gaps between machine loads.
• The final load imbalance is more likely to be caused by a small task rather than a large one.
• This reasoning leads to the LPT rule.

In the formal analysis of LPT, if the last-finishing critical task is relatively large, the structure of the instance severely limits how many tasks can appear on each machine. Otherwise, the critical task is small relative to , which limits its effect on the makespan. This produces the improved bound .

Maintain the machines in a min-priority queue keyed by current load.

For each task:

1. Extract a machine having minimum current load.
2. Assign the task to that machine.
3. Increase the machine's load by the task's processing time.
4. Insert or update the machine in the priority queue.

Each extraction and insertion takes time. For tasks, ordinary list scheduling therefore takes

time and uses auxiliary space, excluding the stored schedule.

For LPT, sorting tasks first takes time. Its total time is

If assignments must be reported, an additional space is used to store the machine selected for every task.

In one-dimensional bin packing, each item has size with

and every bin has capacity . Each item must be placed wholly in one bin, and the objective is to minimize the number of bins used.

Useful lower bounds include:

• Total-size bound:
  
• Large-item bound: If items have size greater than , then
  
  because no two such items fit together.
• More generally, counting items above capacity fractions can produce additional bounds.

The total-size bound alone may not be tight because unused space can be distributed across different bins in a way that prevents consolidation.

Next Fit (NF):

• Keeps only the current bin open.
• Places the next item there if it fits; otherwise closes that bin and opens a new one.
• It is fast but may waste space in previously closed bins.

First Fit (FF):

• Scans bins in creation order.
• Places an item in the first bin with enough remaining capacity.
• Opens a new bin only when no existing bin can hold the item.

Best Fit (BF):

• Places an item in a feasible bin that leaves the smallest remaining capacity.
• Attempts to fill bins as tightly as possible.

All three are online algorithms when they process items in arrival order. NF makes the fewest placement searches, while FF and BF usually produce better packings by reconsidering all open bins. However, locally filling a bin most tightly does not always guarantee a globally optimal packing.

Suppose Next Fit uses bins with loads . A new bin is opened only because its first item does not fit in bin . Therefore, for every adjacent pair,

Pair bins as . If is even, summing the inequalities gives

If is odd, pairing the first bins gives

Let be the total item size. Since every optimal bin has capacity ,

The adjacent-pair property implies that Next Fit cannot use or more bins; with integral bin counts, this yields

Hence Next Fit is an absolute -approximation, with the sharper integer bound shown above.

Next Fit:

• Put in .
• does not fit, so put it in .
• Put in , whose load becomes .
• does not fit, so put it in .
• Put in .

The bins are , , and , so NF uses bins.

First Fit:

• Put in .
• Put in .
• Put in , filling it.
• Put in .
• Put in , filling it.

FF uses bins: and .

The total size is , so at least bins are necessary. Therefore, First Fit is optimal on this instance, whereas Next Fit is not.

First Fit Decreasing (FFD): Sort items in non-increasing order of size and then apply First Fit.

Best Fit Decreasing (BFD): Sort items in non-increasing order and then apply Best Fit.

Sorting improves packing because:

• Large items, which are difficult to place, are handled before bins become fragmented.
• Small items are flexible and can fill gaps left by large items.
• A late-arriving large item is less likely to force the opening of an avoidable new bin.

FFD has the well-known asymptotic bound

Both methods are offline because all item sizes must be known before sorting. A straightforward implementation is polynomial, with sorting taking time; the placement phase depends on the data structure used to locate a feasible bin.

Online bin packing:

• Items arrive one at a time.
• Each item must be placed without knowledge of future items.
• Existing decisions normally cannot be changed.
• Next Fit, First Fit, and Best Fit are online when used in arrival order.
• These methods suit streaming, storage allocation, and real-time settings.

Offline bin packing:

• All items are known before packing begins.
• Items may be sorted or otherwise preprocessed.
• First Fit Decreasing and Best Fit Decreasing are offline algorithms.
• Offline knowledge generally enables better packing guarantees.

The limitation of online algorithms is uncertainty: an apparently good current placement may be poor after future items arrive. Offline algorithms avoid this issue but require complete input availability and additional preprocessing time and memory.

Similarities:

• Both assign indivisible objects to capacity-like containers.
• Task sizes correspond to processing times, while machines or bins receive collections of objects.
• Both are NP-hard optimization settings and motivate approximation algorithms.
• Total size or workload provides a natural lower bound.
• Greedy placement and decreasing-order strategies are useful in both problems.

Differences:

• In makespan scheduling, the number of machines is fixed and the objective is to minimize the maximum machine load.
• In bin packing, bin capacity is fixed and the objective is to minimize the number of bins.
• Scheduling permits any machine load but penalizes the largest one; bin packing prohibits a load above capacity.

The problems are related through decision versions: asking whether tasks can be scheduled on machines with makespan at most resembles asking whether items can be packed into bins of capacity . Their approximation analyses nevertheless use different objective-specific bounds.