1. Assume you have the following set of preferences of people over seats at a ta

Question

1. Assume you have the following set of preferences of people over seats at a table:
{"John", {Seat1, Seat2, Seat 3},
"Mary",{Seat2, Seat4},
"Bob", {Seat1, Seat3, Seat4},
"Alice", {Seat3, Seat5},
"Cindy", {Seat1, Seat2, Seat3}}

What is the competitive ratio of the greedy algorithm vs. the optimal seating arrangement? Show your work?

What I have; But i'm not understanding the formulas to actuall solve the problem. This was more a process of elmiantion

Competitive ratio = minall possible inputs I (|Mgreedy|/|Mopt|)

1

2

3

4

5

John

1

1

1

Mary

1

1

Bob

1

1

1

Alice

1

1

Cindy

1

1

1

3

3

4

2

1

60%

60%

80%

40%

20%

Greedy

Optimal

John

Seat1

Alice

Seat 5

Mary

Seat4

Mary

Seat2

Bob

Seat3

Bob

Seat 4

Alice

Seat5

John

Seat 1

Cindy

Seat 2

Cindy

Seat 3

1

2

3

4

5

John

1

1

1

Mary

1

1

Bob

1

1

1

Alice

1

1

Cindy

1

1

1

3

3

4

2

1

60%

60%

80%

40%

20%

Greedy

Optimal

John

Seat1

Alice

Seat 5

Mary

Seat4

Mary

Seat2

Bob

Seat3

Bob

Seat 4

Alice

Seat5

John

Seat 1

Cindy

Seat 2

Cindy

Seat 3

Explanation / Answer

Your answer for optimal solution is correct.

For greedy solution, just assign the first empty seat in the preference set of that person.

For eg. For John Seat1 is initially empty so assign seat1 to John

Now for Mary assign Seat2

For Bob first seat in preference set is seat1 which is already filled, so moving on to next seat which is seat3 and is empty, therefore assign seat3 is assigned to Bob.

competitive ratio =4/5

Greedy Optimal John Seat1 Seat1 Mary Seat2 Seat2 Bob Seat3 Seat4 Alice Seat5 Seat5 Cindy Seat3

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.