# Algorithm: Strategies for Packing

## Basic Principles

• The concept of Packing in algorithms refers to a category of optimisation problems which involve the arranging or allocation of resources in a certain way.

• Packing problems are often defined in the context of trying to minimise waste or maximise usage of available resources.

## Example Problems

• Packing problems include issues like arranging physical objects in containers in the most efficient manner (Bin-Packing), scheduling tasks for a finite number of processors or machines (Job Scheduling), or optimizing network traffic (Network Packing).

## Greedy Algorithm

• A common approach to solving packing problems is to use a Greedy Algorithm, which makes the locally optimal choice at each stage with the hope that this will lead to a global optimum.

• While the Greedy Algorithm can solve some packing problems quite efficiently, it can also result in non-optimal solutions in certain cases.

## Backtracking Algorithm

• Another approach is to use a Backtracking Algorithm, which systematically searches for a solution by exploring all possible cases and retracting steps when it encounters a dead end.

• Backtracking algorithms can generally find an optimal solution, but can be time-consuming when the number of elements involved in the packing problem is large.

## Algorithms for Specific Problems

• Several specific algorithms have been developed for particular packing problems, for example, the First Fit Decreasing (FFD) Algorithm and Best Fit Decreasing (BFD) Algorithm for the Bin-Packing problem.

• These algorithms involve reordering the items to be packed in a certain manner before applying the packing algorithm.

## Theoretical Underpinnings

• Most packing problems are classed as NP-hard in computational complexity theory, implying that they are as hard as the hardest problems in NP (Nondeterministic Polynomial time).

• As such, they cannot be solved in polynomial time, and finding an efficient algorithm that can solve all instances of a packing problem to optimality is an open question in computer science.

## Real-world Applications

• Despite their theoretical complexity, packing algorithms have numerous practical applications, from optimizing storage and shipping in logistics, to task scheduling in computing, to bandwidth allocation in telecommunications.