Advanced Algorithms

Unit:- 4
Module:- 5

Linear Programming:-
Introduction
Linear Programming (LP) is a mathematical optimization technique
used to achieve the best possible outcome under given constraints.
It helps in:
 Maximizing profit

 Minimizing cost

 Efficient resource utilization

LP is widely used in operations research, computer science,

industries, transportation, and scheduling problems.

Definition
Linear Programming:
A mathematical method used to optimize a linear objective function
subject to linear constraints and non-negative conditions.

Components of Linear Programming

1. Decision Variables
These are unknown quantities whose values must be determined.
Example:
 𝑥= number of products A

 𝑦= number of products B

2. Objective Function
The function that needs to be maximized or minimized.
Example:
 𝑍 = 5𝑥 + 3𝑦
Where:
 5and 3are profits/cost coefficients.

3. Constraints
Restrictions or limitations on resources.
Example:
2𝑥 + 𝑦 ≤ 100

4. Non-Negativity Constraints
Variables cannot be negative.
𝑥 ≥ 0, 𝑦 ≥ 0

Standard Form of LP Problem

Maximization Form
Maximize 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
Subject to:
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1
𝑥1 , 𝑥2 , … , 𝑥𝑛 ≥ 0

Characteristics of Linear Programming

1. Linearity
Both objective function and constraints must be linear.

2. Optimization
Aims to maximize or minimize a quantity.

3. Constraints
Solutions must satisfy given restrictions.
4. Deterministic Nature
All coefficients are known and fixed.

5. Non-Negativity
Variables cannot take negative values.

Assumptions of Linear Programming

1. Proportionality
Contribution of variables is proportional.

2. Additivity
Total effect equals sum of individual effects.

3. Divisibility
Variables may take fractional values.

4. Certainty
All parameters remain constant.

Methods to Solve LP Problems

1. Graphical Method
Used When:
 Problem contains only two variables.

Steps:
1. Plot constraints on graph
2. Determine feasible region
3. Identify corner points
4. Evaluate objective function
5. Select optimal solution
2. Simplex Method
Used When:
 Problem contains more than two variables.

Concept:
An iterative algorithm that moves from one feasible solution to
another until the optimal solution is reached.

Important Terms in Linear Programming

1. Feasible Solution
A solution satisfying all constraints.

2. Feasible Region
The set of all feasible solutions.

3. Optimal Solution
Best feasible solution.

4. Infeasible Solution
Does not satisfy constraints.

5. Unbounded Solution
Objective value can increase/decrease indefinitely.

6. Degeneracy
Multiple solutions occur at the same point.

Example of LP Problem
A company produces two products A and B.
 Profit on A = ₹50
  Profit on B = ₹40
Let:
 𝑥= units of A
 𝑦= units of B

Objective Function:
𝑍 = 50𝑥 + 40𝑦
Subject to:
2𝑥 + 𝑦 ≤ 100
𝑥 + 𝑦 ≤ 80
𝑥, 𝑦 ≥ 0

Goal: Find values of 𝑥and 𝑦that maximize profit.

Applications of Linear Programming

1. Production Planning
Optimizing manufacturing processes.

2. Transportation Problems
Minimizing transportation cost.

3. Assignment Problems
Assigning tasks efficiently.

4. Scheduling
Optimal time allocation.

5. Diet Problems
Minimum-cost balanced diet planning.

6. Network Optimization
Routing and shortest path problems.
Advantages of Linear Programming
1. Efficient Resource Utilization
Resources are used optimally.

2. Better Decision Making

Provides scientific decision support.

3. Cost Reduction
Helps minimize expenses.

4. Increased Profit
Improves profitability.

5. Time Saving
Enables systematic planning.

Limitations of Linear Programming

1. Only Linear Relationships
Cannot solve nonlinear problems.

2. Assumes Certainty
Real-world uncertainty is ignored.

3. Complexity
Large problems become computationally difficult.

4. Fractional Results
Integer solutions are not always guaranteed.
Difference Between Graphical and Simplex Method
Graphical Method Simplex Method
Used for 2 variables Used for multiple variables
Easy visualization More computational
Manual approach Iterative algorithm
Suitable for small problems Suitable for large problems

One-Line Revision
“Linear Programming is an optimization technique used to maximize
or minimize a linear objective function under linear constraints.”

Conclusion
Linear Programming is one of the most important optimization
techniques in advanced algorithms and operations research. It helps
organizations achieve the best possible outcomes while efficiently
managing limited resources.

Linear Programming: Geometry of the Feasibility Region and

Simplex Algorithm
Introduction
Linear Programming (LP) is an optimization technique used to
maximize or minimize a linear objective function under a set of linear
constraints.
Two major concepts in LP are:
1. Geometry of the Feasibility Region
2. Simplex Algorithm
These concepts are very important in Advanced Algorithms and
Operations Research.
1. Geometry of the Feasibility Region
Definition
The feasibility region (or feasible region) is the set of all possible
solutions that satisfy all constraints of a Linear Programming
problem.
It is represented graphically as an area formed by constraint lines.
Basic LP Structure
Objective Function
Maximize 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2
Subject to:
𝑎1 𝑥 + 𝑏1 𝑦 ≤ 𝑐1
𝑎2 𝑥 + 𝑏2 𝑦 ≤ 𝑐2
𝑥 ≥ 0, 𝑦 ≥ 0
Geometry of Feasible Region
Important Concepts
1. Constraint Lines
Each inequality forms a straight line on the graph.
Example:
𝑥 + 𝑦 ≤ 10

represents a line and a region below it.

2. Feasible Region
The common area satisfying all constraints.
 Can be bounded or unbounded.

 Contains all feasible solutions.

3. Corner Points (Vertices)

The intersection points of constraint lines.
According to LP theory:
Optimal solution always occurs at a corner point of feasible region.

4. Convex Region
The feasible region is always convex.

Convex Set Property

If two points lie inside the feasible region, then the line joining them
also lies inside the region.
Types of Feasible Regions
1. Bounded Feasible Region
Closed region with finite optimal solution.
2. Unbounded Feasible Region
Region extends infinitely.
Possible infinite solutions.
3. Empty Feasible Region
No common area exists.
Problem becomes infeasible.

Important Geometric Terms

Term Meaning
Feasible Solution Satisfies all constraints
Feasible Region Set of all feasible solutions
Optimal Solution Best feasible solution
Corner Point Intersection of constraints
Convex Set Region containing line segment between points

Example of Feasible Region

Objective Function:
𝑍 = 3𝑥 + 2𝑦
Subject to:
𝑥+𝑦 ≤4
𝑥≤2
𝑦≤3
 𝑥, 𝑦 ≥ 0

Steps
1. Draw all constraint lines.
2. Shade feasible area.
3. Find corner points.
4. Evaluate 𝑍at vertices.
5. Maximum value gives optimal solution.
2. Simplex Algorithm
Definition
The Simplex Algorithm is an iterative method used to solve Linear
Programming problems with multiple variables.
Developed by George Dantzig.

Why Simplex Method is Needed

Graphical method works only for:
 Two variables

Simplex method works for:

 Large-scale LP problems

 Multiple variables and constraints

Basic Idea of Simplex Algorithm

The algorithm:
1. Starts from one corner point
2. Moves to adjacent corner points
3. Improves objective value step by step
4. Stops at optimal solution

Standard Form for Simplex

Maximization Problem
Maximize 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
Subject to:
𝐴𝑥 ≤ 𝑏
𝑥≥0

Steps of Simplex Algorithm

Step 1: Convert into Standard Form
 Convert inequalities into equations.

 Add slack variables.

Example:
𝑥 + 𝑦 ≤ 10

becomes
𝑥 + 𝑦 + 𝑠 = 10

where 𝑠is slack variable.

Step 2: Construct Initial Simplex Table

Prepare tableau containing:
 Variables

 Constraints

 Objective coefficients

Step 3: Select Entering Variable

Choose variable with highest negative coefficient in objective row.

Step 4: Select Leaving Variable

Use minimum ratio test.

Step 5: Pivot Operation

Perform row operations to update table.
Step 6: Repeat Iterations
Continue until no negative coefficient remains.

Important Terms in Simplex Method

1. Slack Variable
Added to convert ≤ inequalities into equations.

2. Basic Variables
Variables currently in solution.

3. Non-Basic Variables
Variables set to zero.

4. Pivot Element
Element used for row transformation.

5. Tableau
Tabular representation of calculations.

Properties of Simplex Algorithm

1. Iterative Nature
Improves solution step by step.

2. Finite Termination
Stops after finite iterations.

3. Efficient for Large Problems

Handles many constraints and variables.
Advantages of Simplex Method
1. Solves Large LP Problems
Efficient for industrial applications.

2. Gives Optimal Solution

Guaranteed optimum if feasible.

3. Systematic Procedure
Easy computational implementation.

Limitations of Simplex Method

1. Computational Complexity
Very large problems may take time.

2. Degeneracy
May repeat same solution.

3. Cycling
Rarely loops indefinitely without special rules.

Applications of LP and Simplex Algorithm

1. Production Planning
Resource allocation.

2. Transportation
Minimum transportation cost.

3. Scheduling
Time optimization.
4. Network Flow Problems
Communication and routing.

5. Finance
Investment optimization.

NP-Completeness
Introduction
NP-Completeness is one of the most important topics in Advanced
Algorithms and Computational Complexity Theory.
It helps classify computational problems based on:
 Difficulty level

 Time complexity

 Solvability

The theory mainly deals with:

1. P Problems
2. NP Problems
3. NP-Hard Problems
4. NP-Complete Problems

1. Complexity Classes
Class P
Definition
Class P contains problems that can be solved in polynomial time
using deterministic algorithms.
Examples
 Binary Search

 Merge Sort

 Dijkstra’s Algorithm

 Minimum Spanning Tree

Time Complexity
𝑂(𝑛), 𝑂(𝑛2 ), 𝑂(𝑛3 )

etc.

Class NP
Definition
Class NP (Non-deterministic Polynomial time) contains problems
whose solutions can be verified in polynomial time.
Important Point
 Solution may be difficult to find.

 But easy to verify.

Example
Sudoku Verification
Checking a completed Sudoku solution is easy.

Relation Between P and NP

𝑃 ⊆ 𝑁𝑃

Meaning:
Every problem solvable in polynomial time can also be verified in
polynomial time.

2. NP-Hard Problems
Definition
A problem is NP-Hard if:
 Every NP problem can be reduced to it in polynomial time.

 It may or may not belong to NP.

Important Properties
1. At least as hard as NP problems
2. Solution verification may not be polynomial
3. Can be optimization problems

Examples of NP-Hard Problems

 Traveling Salesman Problem (Optimization Version)

 Halting Problem

 Job Scheduling

 Knapsack Optimization

3. NP-Complete Problems
Definition
A problem is NP-Complete if:
1. It belongs to NP.
2. It is NP-Hard.

Formula for NP-Completeness

NP-Complete = 𝑁𝑃 ∩ 𝑁𝑃-Hard

Important Characteristics
1. Hardest problems in NP
2. No known polynomial-time algorithm
3. If one NP-Complete problem is solved in polynomial time:
Then all NP problems can also be solved in polynomial time.

Famous NP-Complete Problems

Problem Description
SAT Boolean satisfiability
3-SAT Special SAT problem
Clique Problem Fully connected subgraph
Problem Description
Vertex Cover Minimum covering vertices
Hamiltonian Cycle Visit each vertex exactly once
Traveling Salesman (Decision Version) Tour within given cost
Subset Sum Subset with given sum

4. Polynomial-Time Reduction
Definition
Reduction means transforming one problem into another in
polynomial time.
If problem A reduces to problem B:
𝐴 ≤𝑝 𝐵

Then:
 B is at least as hard as A.

Importance of Reduction
Used to:
 Prove NP-Hardness

 Prove NP-Completeness

5. Proof of NP-Hardness
Steps to Prove NP-Hardness
Step 1
Choose a known NP-Complete problem.

Step 2
Reduce it to the target problem in polynomial time.

Step 3
Show transformation is correct.

Step 4
Conclude target problem is NP-Hard.

General Structure
If:
𝐴 ≤𝑝 𝐵

and A is NP-Complete,
then B is NP-Hard.

Example of NP-Hardness Proof

Traveling Salesman Optimization Problem
Reason
 Decision version is NP-Complete.

 Optimization version is harder.

Thus:
Traveling Salesman Optimization is NP-Hard.

6. Proof of NP-Completeness
Two Conditions Required
Condition 1
Problem must belong to NP.
Means:
Solution can be verified in polynomial time.

Condition 2
Problem must be NP-Hard.
Means:
Known NP-Complete problem reduces to it.

Example: SAT Problem

SAT (Boolean Satisfiability)
Given a Boolean formula:
Determine whether variables can satisfy the formula.
Example:
(𝐴 ∨ 𝐵) ∧ (¬𝐴 ∨ 𝐶 )

Importance
SAT was the first NP-Complete problem proved by the Cook-Levin
Theorem.

Cook-Levin Theorem
Statement
Boolean Satisfiability Problem (SAT) is NP-Complete.
This theorem forms the foundation of NP-Completeness theory.

7. Examples of NP-Complete Problems

1. Vertex Cover
Goal
Find minimum vertices covering all edges.

2. Clique Problem
Goal
Find complete subgraph of size k.

3. Hamiltonian Cycle
Goal
Visit every vertex exactly once and return.
4. Subset Sum
Goal
Find subset with target sum.

5. 3-SAT
Each clause contains exactly 3 literals.

8. P vs NP Problem
Biggest Open Problem in Computer Science
Question:
𝑃 = 𝑁𝑃 ?

Meaning
If P = NP
All NP problems become efficiently solvable.

If P ≠ NP
NP-Complete problems remain computationally hard.

Applications of NP-Completeness
1. Cryptography
Security systems depend on hard problems.

2. Scheduling
Airline and job scheduling.

3. Artificial Intelligence
Search and optimization.
4. Network Design
Routing and communication.

5. Compiler Optimization
Efficient code generation.

Difference Between NP-Hard and NP-Complete

NP-Hard NP-Complete
May not belong to NP Must belong to NP
Verification may be difficult Verification is polynomial
Can be undecidable Always decidable
Harder category Subset of NP-Hard

Important Exam Points

Must Remember
 𝑃 ⊆ 𝑁𝑃

 NP-Complete = NP + NP-Hard

 Reduction is used for proofs

 SAT was first NP-Complete problem

 Cook-Levin theorem is important

 NP-Hard problems may not be in NP

Approximation Algorithms in Advanced Algorithms

Introduction
Approximation Algorithms are used to solve optimization problems
that are:
 NP-Hard

 NP-Complete

 Difficult to solve exactly in polynomial time

Instead of finding the exact optimal solution, these algorithms find a

solution that is:
  Close to optimal
 Computed efficiently

They are widely used in:

 Network design

 Scheduling

 Routing

 Resource allocation

 Traveling Salesman Problem

Definition
Approximation Algorithm
An approximation algorithm is a polynomial-time algorithm that
produces a near-optimal solution for an optimization problem.

Main Goal
 Reduce computation time

 Obtain acceptable solution quality

 Handle large-scale NP-Hard problems

Basic Idea
Instead of:
 Searching all possible solutions

Approximation algorithms:
 Use heuristics and strategies

 Produce good enough solutions quickly

Optimization Problems
Approximation algorithms mainly solve:
1. Minimization Problems
Goal:
Minimize cost, distance, time, etc.
Example:
 Vertex Cover

 Traveling Salesman Problem

2. Maximization Problems
Goal:
Maximize profit, coverage, efficiency, etc.
Example:
 Knapsack Problem

Approximation Ratio
Definition
Approximation ratio measures how close the algorithm’s solution is
to the optimal solution.

Formula
For minimization problems:
Approximate Solution
𝜌=
Optimal Solution
For maximization problems:
Optimal Solution
𝜌=
Approximate Solution

Interpretation
 𝜌 = 1→ Exact optimal solution

 𝜌 = 2→ At most twice the optimal value

Characteristics of Approximation Algorithms

1. Polynomial-Time Execution
Runs efficiently.

2. Near-Optimal Solution
Produces approximate answer.

3. Performance Guarantee
Has bounded approximation ratio.

4. Useful for NP-Hard Problems

Practical for difficult problems.

General Structure of Approximation Algorithms

Start
↓
Input Optimization Problem
↓
Check Complexity
↓
Exact Solution Feasible?
↓ Yes ↓ No
Use Exact Algorithm Use Approximation Algorithm
↓
Generate Near-Optimal Solution
↓
Evaluate Approximation Ratio
↓
End

Types of Approximation Algorithms

1. Greedy Approximation Algorithms
Idea
Make locally optimal choice at each step.

Examples
 Vertex Cover

 Set Cover

 Scheduling Problems

2. Local Search Algorithms

Idea
Improve solution iteratively using neighboring solutions.

Example
Traveling Salesman Problem

3. Randomized Approximation Algorithms

Idea
Use random choices during execution.

Advantage
Sometimes gives better average performance.

4. Primal-Dual Approximation Algorithms

Idea
Use Linear Programming duality concepts.

Used In
 Network design

 Set cover
Vertex Cover Approximation Algorithm
Problem
Given a graph:
Find minimum number of vertices covering all edges.

Simple Approximation Algorithm

Steps
1. Select any uncovered edge.
2. Add both endpoints to vertex cover.
3. Remove covered edges.
4. Repeat until all edges covered.

Approximation Guarantee
Produces at most:
2 × 𝑂𝑃𝑇
where:
 𝑂𝑃𝑇= optimal solution size

Thus it is a 2-Approximation Algorithm.

Traveling Salesman Problem (TSP)

Problem
Find shortest possible tour visiting every city exactly once.

Difficulty
TSP is NP-Hard.

Approximation for Metric TSP

Algorithm
1. Compute Minimum Spanning Tree (MST)
2. Perform preorder traversal
3. Construct Hamiltonian cycle
Approximation Ratio
Approximation Ratio = 2

Knapsack Approximation
Problem
Select items maximizing profit under weight limit.

Greedy Approximation
Choose items according to:
 Profit/Weight ratio

Advantage
Fast and practical.

Set Cover Approximation

Problem
Cover all elements using minimum subsets.

Greedy Strategy
Repeatedly choose subset covering maximum uncovered elements.

Approximation Ratio
𝐻(𝑛) ≈ ln⁡𝑛
where:
 𝐻(𝑛)= Harmonic number

Performance Analysis
Why Important?
Measures:
 Solution quality
  Efficiency
 Worst-case behavior

Performance Guarantee
If algorithm always produces solution within factor 𝜌:
Then algorithm is called:
 𝜌-Approximation Algorithm

Approximation Algorithm Design Techniques

Technique Description
Greedy Method Local optimal choices
Dynamic Programming Approximate states
Linear Programming Relaxation Relax integer constraints
Randomization Random choices
Local Search Neighbor improvements

Advantages of Approximation Algorithms

1. Fast Execution
Efficient for large problems.

2. Practical Solutions
Useful in real-world systems.

3. Handles NP-Hard Problems

Provides feasible approach.

4. Guaranteed Quality
Approximation ratio bounds error.

Limitations
1. Not Exact
Solution may differ from optimum.

2. Approximation Bound
Quality depends on ratio.

3. Problem-Specific
No universal approximation method.

Applications
1. Network Routing
Efficient communication paths.

2. Scheduling
Task allocation.

3. Logistics
Transportation optimization.

4. Machine Learning
Optimization tasks.

5. Resource Allocation
Efficient usage of limited resources.

Difference Between Exact and Approximation Algorithms

Exact Algorithms Approximation Algorithms
Give optimal solution Give near-optimal solution
May require exponential time Polynomial-time
Suitable for small problems Suitable for large NP-Hard problems
Exact Algorithms Approximation Algorithms
High computational cost Efficient and practical

Important Exam Points

Must Remember
 Used for NP-Hard optimization problems

 Gives near-optimal solutions

 Runs in polynomial time

 Approximation ratio measures quality

 Vertex Cover has 2-approximation

 Greedy techniques are common