CompSci 260P: Week 6

Algorithmic Pizza

• A new pizza chain wants to open parlors along a long road
• There are houses located at various points along the road
• Goal: Ensure each house is within 5 miles of a parlor with minimum parlors

Algorithmic Pizza

• We may choose various points along the road to place a parlor
• What is the dumbest algorithm which would satisfy the first condition?
  • At every house, just add a pizza parlor
  • Why is this bad?

Algorithmic Pizza

• So how do we do better?
  • Hint: Is there a difference between being 5 miles away or 1 mile away?
• To any single house, they don't care if it's 5 miles or 1 mile away
• Who should be the furthest away from a parlor?
  • One of the end points!

Algorithmic Pizza: Algorithm

• Identify the westernmost house
• Place a parlor 5 miles east of that house
• Remove all houses covered by the parlor
• Repeat steps until all houses are covered

Algorithmic Pizza: Algorithm

# Each house is a number on the number line
def AlgPizza(houses):
    houses.sort()
    parlor = []
    while houses:
        parlor.append(houses[0] + 5)
        while houses and abs(parlor[-1] - houses[0]) <= 5:
            houses.pop(0)
    return parlor

Algorithmic Pizza: Proof

• We must now prove this algorithm is optimal
  • We first consider some general optimal solution
  • The properties of what that solution may look like
  • Pick a piece of that solution
  • Swap it with a piece of our solution
  • Show that the solution is still optimal

Algorithmic Pizza: Proof

• Consider some optimal solution, which will be a set of parlors
  • Our algorithm looks at the westmost house, so let us do the same
  • Optimal solution must cover the westmost house!
• Can the optimal solution ever be to the right of the parlor we chose?
  • No! Otherwise, the westernmost house would not be covered

Algorithmic Pizza: Proof

• If we swap the optimal solution's westmost house with our westmost house, does the solution stay the same?
  • It must! Our solution only ever covers more houses, not less
• Note: We should prove the inductive step of this following for all houses
  • We will not here as this is not required on the exam

Interval Scheduling Approximation

• Given a set of intervals, find the largest subset of non-overlapping intervals
• Algorithm:
  • Pick the shortest interval
  • Discard any overlapping intervals
  • Repeat until we have no more intervals
• Prove this algorithm is a 2-approximation

Interval Scheduling Approximation

• Consider the optimal solution and compare it to our own
  • What properties does the optimal solution have compared to our own?
  • The magic number to look for is 2
• What happens when the optimal solution has more intervals than the greedy
  • Consider an interval that invalidates more than 1 interval
  • Can it invalidate more than 2?
  • No, because of the middle interval!

Interval Scheduling Approximation

• For each interval, it can overlap at most 2 optimal intervals
• Therefore, our solution is at most half of the optimal solution
• Thus making it a 2 approximation