## Solutions to midterm and assignments

Midterm questions:
http://www.cs.uleth.ca/~benkoczi/files/approx/midterm.pdf

Midterm solutions:
http://www.cs.uleth.ca/~benkoczi/files/approx/midterm-sol.pdf

Assignment 2 questions:
http://www.cs.uleth.ca/~benkoczi/wordpress/?page_id=317

Assignment 2 solutions:
http://www.cs.uleth.ca/~benkoczi/files/approx/a2-sol.pdf

Assignment 3 questions:
http://www.cs.uleth.ca/~benkoczi/wordpress/?p=370

Assignment 3 solutions:
http://www.cs.uleth.ca/~benkoczi/files/approx/a3-sol.pdf

## Midterm exam – Thr. October 31, 2013

Happy Haloween!
Exam duration: 75 minutes, in class, on Thr. Oct 31, 2013.

Exam preparation guidelines:

• Chapters covered: 1, 2 (excluding section 2.6); 3.1
• Review linear programming
• Attempt the following exercises from the text: 1.1 (use the greedy algorithm), 1.2 (use the unweighted set cover problem); 1.6a; 2.1 – 2.4a; 2.5 (first convince yourselves that the MST on $G[R]$ is not optimal for the Steiner tree problem; then consider an optimal Steiner tree solution, make the tree Eulerian, and shortcut all the non-terminal vertices. What do you get?); 2.6; 2.11a; 2.16; 3.1, 3.2

## Term project and presentation

Due date for projects: Friday Dec 6, midnight
Submission instructions: Please send the following by e-mail to the address: roben777+files@gmail.com:

1. the source code, preferably as a link to some code repository or inside a compressed archive (zip, tar.bz2, or tar.gz)
2. some of the problem data, either hosted in the repository or inside the file archive
3. your report in PDF format

Graduate students must write their report in latex.

Guidelines for projects:

• choose the topic by Friday, Nov 1, 23:59. Please e-mail me your choice.
• you may work in teams of two. Both graduate and undergraduate students will be evaluated in the same way, and so an undergraduate student may pair up with a graduate student.
• Topic: choose a particular problem for which approximation algorithms are known or can be devised from other problems. If you are unsure, please see me. The project must implement at least two different approximation algorithms for the problem if you are part of a team; if you are alone, then you must implement at least one algorithm.
• tentative date for the project: end of November.
• submit:
1. a project report as a PDF file please. Grad students must use latex for document preparation.
2. your source code with data, ideally as a link to bitbucket or github or some other public code repository. Alternatively, you can send me a bz2, zip, or tar.gz archive.

Project evaluation criteria:

1. compilation: I should be able to compile and execute your code on the provided data, without problems. Target the architecure for a linux machine.
2. description of the problem and the algorithm(s): describe the problem, the algorithms implemented and a proof of the approximation factor if the algorithm was not already discussed in class.
3. data: describe in the report how you obtained the data. Be concise but rigorous. Include both randomly generated data and real data if you can obtain it. The data size should be as large as possible. Talk to me for ideas and advice.
4. correctness: describe how you assessed the correctness of your code. Ideas: small separate code to verify the constraints, code that generates specific instances on which you know the results expected from the algorithms, etc. Provide appropriate details in the report.
5. quality of the solutions: provide graphs in the report that show the quality of the solutions obtained. Give an a posteriori guarantee: either use the optimal solution which is published for some real problem instances that you download, or calculate the bound for the optimal solution. For plots, I recommend gnuplot. Provide details as appropriate.
6. efficiency of the algorithm(s): explain your data structures and provide both a running time analysis like for Problem 5 in Assignment 1 and a plot with measurements from your experiments. Try to get an implementation that is as efficient as you can. Use library data structures as much as you can in your implementation.

Notes on code & data:

• do not submit executables, just the source code.
• submit just enough data so that the total size of your submission does not exceed 2Mb.
• briefly explain any specific steps required to get your code to compile and run.

Guidelines for presentations:

• choose a topic by Friday, Oct 25, 23:59. Please send an e-mail with your choice and provide references to where the result is described.
• Topic: choose a particular approximation algorithm for a particular problem. If you are unsure, please see me. The algorithm for the problem you chose must not have been already discussed in class. The topic can be from the text or from another paper, for example, consult part II of the text. Make sure you provide the reference to where the result is described.
• tentative date for presentations: mid november
• target your presentation for 35 minutes; we will have two presentations per class.
• organize your presentation as if you are teaching that topic in the class. You are encouraged to propose homework.
• try to present the algorithm gradually, starting with simple ideas and slowly building more complex ideas incrementally.
• you are free to choose the presentation style, slides, blackboard, or a mixture.

Presentation evaluation criteria:

1. clarity: is the algorithm and the analysis clear to the audience?
2. correctness: does the presentations seem free of errors?

The students attending the class will be asked to write comments, anonymously.

## 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 k-suppliers problem defined in Exercise 2.1 in the textbook. In class, we argued that choosing an arbitrary vertex as center for the 1-center problem is a 2-approximation algorithm. Show that the same strategy has an unbounded approximation factor for the 1-supplier 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 1-supplier problem).

Problem 2 (grad): Consider the following strategy for the 1-supplier 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 3-approximation for the 1-supplier problem (ignore the fact that the 1-supplier problem can be solved optimally in polynomial time by a brute force algorithm). Give a 3-approximation 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 I-S} \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.

## Optimization Seminar: The weighted colouring problem on path graphs

18 Sept 2013 @ 1:00 – 1:50 pm
Room: E575
Presenter: Ram Dahal

Abstract: We present a generalization of the classical vertex colouring problem, weighted colouring, that has applications in the management of wireless networks. We focus on the simplest network topology, the path graph. Time permitting, we conclude with several open problems.

Bio: Ram Dahal is a PhD candidate in Computer Science at The University of Lethbridge. He is a member of the Optimization Research Group since September 2012.

## 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 non-negative. 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.

## Approximation algorithms – Lectures

Sep 5 – 19
Read Chapter 1 – Introduction and Appendix A – Linear programing.
Sep 19 – 26
Read Chapter 2 (greedy and local search): The k-center + scheduling with deadlines on a single machine + scheduling on parallel identical machines.
Oct 1-3
Chapter 2: TSP + Max float
Oct 8-10
Chapter 2: edge colouring, Chapter 3 (rounding data and PTAS): a PTAS for the knapsack problem
Oct 15-17
Chapter 3: PTAS for scheduling on identical parallel machines
Oct 22-24
Chapter 3: scheduling on identical parallel machines, bin packing
Oct 29-Nov 14
Chapter 4 (deterministic rounding): sections 4.1 – 4.5 (job scheduling to minimize weighted sum of completion times, the ellipsoid algorithm, prize collecting Steiner tree and UFL)
Nov 19-28
Student presentations (shortest super-string, Canadian traveller in double valued graphs, PTAS for max-colouring in trees, minimum knapsack greedy and primal-dual (Section 7.5), asymmetric TSP, and partial set cover).

Dec 3-5
Chapter 7 (primal-dual): 7.2, 7.6 (feedback vertex set, UFL)

## CPSC 4110/5110 – Advanced Algorithms (Approximations)

This course is about designing approximation algorithms for difficult
optimization problems for which no optimal algorithms with running
time polynomial in the problem size are known. Approximation
algorithms find feasible solutions that may not be optimal but are not
too far from the optimal one.

We overview various interesting
algorithm design techniques that may prove extremely useful to
graduate students tackling research questions in various fields and to
undergraduates who may encounter interesting problems in their future
projects in the industry.

## Optimization Seminar – Thr. Apr. 11, 2013

Thursday April 11, from 12:15-13:05
Room E-575
Speaker: Daya Gaur.
Abstract:
Given a fleet of vehicles and a set of customers, the objective in capaciated vehicle routing problems is to minimize the total distance traveled and serve the customers subject to vehicle capacity constraints. We will examine existing approximation algorithms for deterministic and stochastic versions of capaciated vehicle routing problems.
This talk is open to everyone. Graduate students are encouraged to attend. Light refreshments will be served.

## Optimization Seminar – Thr. Mar 21, 2013

Thursday Mar 21 from 12:15-13:05
Room E-575

Speaker: Ram Dahal
Ram will talk about the weighted colouring problem in a graph and its connection to routing and scheduling in wireless networks.
Everyone is welcome. All graduate students are encouraged to attend. Light refreshments will be served.