
Search It!

Recent Entries
 CPSC 4110/5110/7110 – Introduction to Algorithms in Facility Location
 CPSC 4210/5210: Wireless Networks
 Optimization Seminar Series – Fri Dec 16, 2016, noon, in B543
 Optimization Seminar Series – Wed. Oct 19, 2016, noon, in C620
 CPSC 3780 for Dr. Gaur (Sept 2022, 2016)
 CPSC 2620 for Dr. Hossain (Sept 1315, 2016)
 Optimization Seminar Series – Wed. Jul 13, 2016, noon, in B543
 Optimization Seminar Series – Wed Mar 23, 1Pm in D633
 Optimization Seminar Series – Mon Mar 7 at 1 pm – B756
 Optimization Seminar Series – Fri Feb 12 at 9 am

Links
CPSC 4110/5110: Archive of assignments
Assignment 2
Due: TBD, in class
Undergraduate students can work in teams of two students and can submit a single paper per team. Problems marked (grad) are optional for undergraduate students.
Any notation that is not explained is standard notation. Search google for the definition.
Problem 1: Consider the ksuppliers problem defined in Exercise 2.1 in the textbook. In class, we argued that choosing an arbitrary vertex as center for the 1center problem is a 2approximation algorithm. Show that the same strategy has an unbounded approximation factor for the 1supplier problem (show that $\forall \alpha > 0$, there exists an instance with $Z_{arb} > \alpha Z_{OPT}$, where $Z_{arb}$ is the cost of an arbitrary center in the 1supplier problem).
Problem 2 (grad): Consider the following strategy for the 1supplier problem:
 Choose an arbitrary customer $i \in D$.
 Let $j \in F$ be the closest facility from $i$.
 Place the facility at $j$.
Show that this strategy is a 3approximation for the 1supplier problem (ignore the fact that the 1supplier problem can be solved optimally in polynomial time by a brute force algorithm). Give a 3approximation greedy algorithm for the $k$suppliers problem. Prove its approximation factor.
Problem 3: Consider the following greedy algorithm for the knapsack problem, where $i \in I$ represents an object with value $v_i$ and size $s_i$, and $B$ is the knapsack capacity. Let $v(S)$ and $s(S)$ be the total value and size respectively of items in $S$, $v(S) = \sum_{i \in S} v_i$, $s(S) = \sum_{i \in S} s_i$.
 Initialize the solution set $S \leftarrow \emptyset$.
 while the total size of the solution $S$ does not exceed the knapsack capacity, $s(S) \le B$ do:
 Let $j$ be the object with largest value per unit size, $j = \mathop{\rm argmax}_{i \in IS} \frac{v_i}{s_i}$.
 Add $j$ to the solution, $S \leftarrow S \cup \{j\}$
 Return $v(S)$
Give a simple example to show that this greedy algorithm has an arbitrarily small approximation factor.
Problem 4 (grad): Show that replacing the last step of the greedy algorithm from Problem 3 with
\[
\text{Return } \max\{v(S), \max_{i \in I} v_i\},
\]
gives a $\frac{1}{2}$approximation for the knapsack problem. Provide an example where the greedy algorithm returns a solution with cost equal to half of the optimal solution. Justify your answer even if you cite published work.
Assignment 1
Due: Thursday Oct 3, 2013, in class
Undergraduate students can work in teams of two students and can submit a single paper per team. Problems marked (grad) are optional for undergraduate students.
Any notation that is not explained is standard notation. Search google for the definition.
Problem 1: Consider the vertex cover problem discussed in class for Graph $K_3$. Write the linear programming (LP) relaxation for the problem and give the optimal fractional solution. Write the dual LP and prove that your answer is indeed optimal (find a feasible dual solution whose cost equals that of the primal).
Problem 2: (grad) Relax the LP from Problem 1 by removing the condition that variables $x_v$ associated with the vertices of $K_3$ must be nonnegative. Explain how you obtain the dual of the LP in this case. Write this dual LP.
Problem 3: Solve Problem 1.4 b from the textbook. Briefly argue that your algorithm runs in time polynomial with the problem size.
Problem 4: (grad) Solve Problem 1.4 a in the textbook. Hint: read the textbook.
Problem 5: Describe the local search approximation algorithm for scheduling jobs on identical parallel machines completely, including any data structures that you are using. Try to describe an algorithm that is as fast as you can. Analyse the running time of your algorithm.