Algorithmic Design Paradigms and Strengths in Solving Problems

Lower Bounds in Greedy Model Sashka Davis Advised by Russell Impagliazzo (Slides modified by Jeff) UC San Diego October 6, 2006

Suppose you have to solve a problem No Greedy alg. exists? Or I didn t think of one? Is there a Greedy algorithm that solves ? algorithm that solves ? Algorithm! Is there a Backtracking Eureka! I have a DP No Backtracking agl. exists? Or I didn t think of one? Is my DP algorithm optimal or a better one exists?

Suppose we a have formal model of each algorithmic paradigm No Greedy algorithm can solve exactly. Is there a Dynamic Programming alg. that optimal, or a better DP Is my algorithm Is there a Backtracking algorithm that solves solves ? algorithm exists? Is there a Greedy algorithm that solves ? ? No Backtracking algorithm can solve exactly. DP helps! Yes, it is! Because NO DP alg. can solve more efficiently.

The goal To build a formal model of each of the basic algorithmic design paradigms which should capture the strengths of the paradigm. To develop lower bound technique, for each formal model, that can prove negative results for all algorithms in the class.

Using the framework we can answer the following questions 1. When solving problems exactly: What algorithmic design paradigm can help? No algorithm within a given formal model can solve the problem exactly. Wefind an algorithm that fits a given formal model. 2. Is a given algorithm optimal? Prove a lower bound matching the upper bound for all algorithms in the class. 3. Solving the problems approximately: What algorithmic paradigm can help? Is a given approximation scheme optimal within the formal model?

Some of our results Dynamic Programming Backtracking & Simple DP (tree) Greedy pBP pBT ADAPTIVE PRIORITY FIXED Online

On-line algorithms is a set of data items; is a set of options Input: instance I={ 1 , 2, , n }, I Output: solution S={( i , i) | i= 1,2, ,d}; i 1. Order: Objects arrive in worst case order chosen by adversary. 2. Loop considering i in order. Make a irrevocable decision i

Fixed priority algorithms is a set of data items; is a set of options Input: instance I={ 1 , 2, , n }, I Output: solution S={( i , i) | i= 1,2, ,d}; i 1. Order: Algorithm chooses fixed : R+ without looking at I. 2. Loop considering i in order. Make a irrevocable decision i

Adaptive priority algorithms is a set of data items; is a set of options Input: instance I={ 1 , 2, , n }, I Output: solution S={( i , i) | i= 1,2, ,d}; i 2. Loop - Order: Algorithm reorders : R+ without looking at rest of I. - Considering next i in current order. Make a irrevocable decision i

Fixed priority Back Tracking is a set of data items; is a set of options Input: instance I={ 1 , 2, , n }, I Output: solution S={( i , i) | i= 1,2, ,d}; i 1. Order: Algorithm chooses : R+ without looking at I. 2. Loop considering i in order. Make a set of decisions i (one of which will be the final decision.)

Some of our results Maximum Matching in Bipartite graphs in Bipartite graphs Maximum Matching Shortest Path in negative graphs no cycles Shortest Path in no-negative graphs Flow Algorithms Bellman-Ford pBP pBT ADAPTIVE PRIORITY Dijkstra s PRIORITY FIXED Kruskal s Kruskal s Prim s Online Minimum Spanning Tree

Some of our results Shortest Path in no-negative graphs pBP pBT ADAPTIVE PRIORITY Dijkstra s PRIORITY FIXED Kruskal s Kruskal s Prim s Online Minimum Spanning Tree

Kruskal algorithm for MST is a Fixed priority algorithm Input (G=(V,E), : E R) 1. Initialize empty solution T 2. L = Sorted list of edges in non-decreasing order according to their weight 3. while (L is not empty) e = next edge in L Add the edge to T, as long as T remains a forest and remove e from L 4. Output T

Prims algorithm for MST is an adaptive priority algorithm Prim s algorithm Input G=(V,E), w: E R 1. Initialize an empty tree T ; S 2. Pick a vertex u; S={u}; 3. for (i=1 to |V|-1) (u,v) = min(u,v) cut(S, V-S)w(u,v) S S {v}; T T {(u,v)} 4. Output T

Dijkstras Shortest Paths Alg is an adaptive priority algorithm Dijkstra algorithm (G=(V,E), s V) T ; S {s}; Until (S V) Find e=(u,x) | e = mine Cut(S, V-S){path(s, u)+ (e)} T T {e}; S S {x}

Some of our results Shortest Path in no-negative graphs pBP pBT ADAPTIVE PRIORITY Dijkstra s PRIORITY FIXED Kruskal s Kruskal s Prim s Online Minimum Spanning Tree

Some of our results ShortPath Problem: Given a graph G=(V,E), : E R+; s, t V. Find a directed tree of edges, rooted at s, such that the combined weight of the path from s to t is minimal Data items are edges of the graph Decision options = {accept, reject} Theorem: No Fixed priority algorithm can achieve any constant approximation ratio for the ShortPath problem

Fixed priority game 0 Solver Adversary d i 1 2 3 j k = 0 1 i1 i2 i3 i4 i5 i6 i7 i8 2 i4 End Game S_adv = {( i2, *i2), ( i4, *i4)} 3 i9, i2 S_sol = {( i2, i2)} S_sol = {( i2, i2), ( i4, i4)} (S_sol) (S_adv) f = Solver is awarded f

Adversary selects 0 u(k) a s t b w(k) , , , , , u v w x y z = 0

Solver selects an order on 0 If then the Adversary presents: ( ) ( ) y z u(k) a s t b w(k) = , , , u x y z 1

Adversarys strategy Waits until Solver considers edge y(1) Event 1 y=accept Event 2 y=reject Solver will consider y(1) before z(1)

Event 1: Solver accepts y(1) u(k) a t s b The Solver constructs a path {u,y} The Adversary outputs solution {x,z} Alg Adv + 1 k = 2

Event 2: Solver rejects y(1) u(k) a t s b The Solver fails to construct a path. The Adversary outputs a solution {u,y}.

The outcome of the game: The Solver either fails to output a solution or achieves an approximation ratio (k+1)/2 The Adversary can set k arbitrarily large and thus can force the Algorithm to claim arbitrarily large approximation ratio

Some of our results Shortest Path in no-negative graphs pBP pBT ADAPTIVE PRIORITY Dijkstra s PRIORITY FIXED Online

Some of our results Interval Scheduling value is width pBP pBT ADAPTIVE PRIORITY PRIORITY FIXED Factor of 3 Online Factor of 3

Interval scheduling on a single machine Instance: Set of intervals I=(i1, i2, ,in), j ij=[rj, dj] Problem: schedule intervals on a single machine Solution: S I Objective function: maximize i S(dj - rj)

A simple solution (LPT) Longest Processing Time algorithm input I=(i1, i2, ,in) 1. Initialize S 2. Sort the intervals in decreasing order (dj rj) 3. while (I is not empty) Let ik be the next in the sorted order If ikcan be scheduled then S S U {ik}; I I \ {ik} 4. Output S

LPT is a 3-approximation LPT sorts the intervals in decreasing order according to their length LPT OPT OPT OPT ri di 3 LPT OPT

Example lower bound [BNR02] Theorem1: No adaptive priority algorithm can achieve an approximation ratio better than 3 for the interval scheduling problem with proportional profit for a single machine configuration

Proof of Theorem 1 Adversary s move e 2 q 2 1 3 q-1 q-1 3 1 Algorithm s move: Algorithm selects an ordering Let i be the interval with highest priority

Adversarys strategy If Algorithm decides not to schedule i During next round Adversary removes all remaining intervals and schedules interval i 2 i i 2 1 3 k j 3 1 Alg s value = 0 Adv s value = i

Adversarys strategy If i = and Algorithm schedules i During next round the Adversary restricts the sequence: i 2 i i 1 3 i-1 k i+1 j Alg s value = i Adv s value = (i-1)+3(i/3)+(i+1)=3i

Adversarys strategy If i = and Algorithm schedules i During next round the Adversary restricts the sequence: 1 2 2 i 2 1 1 3 k j 3 1 Alg s value = 1 Adv s value = 3(1/3)+(2)=3

Adversarys strategy If i = and Algorithm schedules i During next round the Adversary restricts the sequence: q 2 q i 2 1 3 q-1 k q-1 j 3 1 Alg s value = q Adv s value = (q-1)+3(q/3)+(q-1)=3q-1 But q is big

Adversarys strategy If i = and Algorithm schedules i During next round Adversary restricts the sequence: i m 2 m i 2 1 3 k j 3 1 Alg s value = i Adv s value = (3i) =3i

Some of our results Interval Scheduling value is width pBP pBT ? ADAPTIVE PRIORITY PRIORITY FIXED Factor of 3 Online Factor of 3 The algorithm was missed up before it got a chance to reorder things.

Some of our results Weighted Vertex Cover pBP pBT ADAPTIVE PRIORITY PRIORITY FIXED Factor of 2 Online

Weighted Vertex Cover [Joh74] greedy 2-approximation for WVC Input: instance G with weights on nodes. Output: solution S V covers all edges and minimizes weight taken nodes. Repeat until all edges covered. Take v minimizing (v)/(# uncovered adj edges)

Weighted Vertex Cover Theorem: No Adaptive priority algorithm can achieve an approximation ration better than 2 With Shortest Path, a data item is an edge of the graph = (<u,v>, (<u,v>) ) With weighted vertex cover, A data item is a vertex of the graph = (v, (v), adj_list(v)) (Stronger than having the items be edges, because the alg gets more info from nodes.

Adaptive priority game Solver Adversary 3 1 2 0 9 10 12 2 8 3 5 7 6 11 1 4 S_sol = {( 7, 7)} S_sol = {( 7, 7), ( 4, 4)} S_sol = {( 7, 7), ( 4, 4),( 2, 2)} 7 4 2 The Game Ends: 1. S_adv = {( 7, *7), ( 4, *4),( 2, *2)} 2. Solver is awarded payoff f(S_sol)/f(S_adv)

The Adversary chooses instances to be graphs Kn,n n2 n2 1 1 1 n2 n2 1 The weight function :V {1, n2}

The game Data items each node appears in oas two separate data items with weights 1, n2 Solver moves Choses a data item, and commits to a decision Adversary move Removes from the next t the data item, corresponding to the node just committed and..

Adversarys strategy is to wait unitl Event 1: Solver accepts a node of weight n2 Event 2: Solver rejects a node of any weight Event 3: Solver has committed to all but one nodes on either side of the bipartite 1 1 1 1 1

Event 1: Solver accepts a node (v)=n2 n2 1 1 1 1 1 1 A B The Adversary chooses part B of the bipartite as a cover, and incurs cost n The cost of a cover for the Solver is at least n2+n-1 2 lg A n Adv n = 2

Event 2: Solver rejects a node of any weight n2 n2 A B The Adversary chooses part A of the bipartite as a cover. The Solver must choose part B of the bipartite as a cover. lg 2 A Adv n 2 n + 2 2 n

Event 3: Solver commits to n-1 nodes w(v)=1, on either side of Kn,n 1 1 1 1 1 1 n2 1 A B The Adversary chooses part B of the bipartite as a cover, and incurs cost n The cost of a cover for the Solver is 2n-1 lg 2 1 A n Adv n = 2

Some of our results Weighted Vertex Cover pBP pBT ADAPTIVE PRIORITY PRIORITY FIXED Factor of 2 Online

Some of our results Facility Location pBP pBT ADAPTIVE PRIORITY PRIORITY FIXED Factor of logn Online

Facility location problem Instance is a set of cities and set of facilities The set of cities is C={1,2, ,n} Each facility fi has an opening cost cost(fi) and connection costs for each city: {ci1, ci2, , cin} Problem: open a collection of facilities such that each city is connected to at least one facility Objective function: minimize the opening and connection costs min( f Scost(fi) + j Cmin fi Scij )