Assignment 3

Due: Thr, Dec 5, in class

Undergraduate students can work in teams of two students and can submit a single paper per team.
Any notation that is not explained is standard notation. Search google for the definition. 10 pts are assigned for each problem. Answers from undergraduate students are marked out of 30 points. Answers from graduate students are marked out of 50 points.

Problem 1: (Based on Problem 3.3 in the textbook) There are $n$ jobs to be scheduled on a single machine, where each job $j$ has a processing time $p_j$, a weight $w_j$, and a due date $d_j$, $j = 1, \ldots, n$. The objective is to schedule the jobs so as to maximize the total weight of the jobs that complete by their due date.

  1. First prove that there always exists an optimal schedule in which all on-time jobs complete before all late jobs, and the on-time jobs complete in an earliest due date order.
  2. Next, give a polynomial time algorithm that finds the optimal solution to the scheduling problem for the case when all weights are one, $w_j = 1$ for all $j = 1, \ldots, n$. Justify the time complexity of your algorithm.

Problem 2: Consider the scheduling problem with arbitrary weights from Problem 1. Show how to solve this problem using dynamic programming in $O(nW )$ time, where $W = \sum_{j=1}^n w_j$. Use this result to derive a fully polynomial-time approximation scheme for the problem.

Problem 3: (Problem 4.2 in the textbook) Consider the scheduling problem from Section 4.2 in the textbook but without release times. We must schedule jobs non-preemptively on a single machine to minimize the weighted sum of completion times $\sum_{j=1}^n w_j C_j$. Suppose that the jobs are indexed such that $\frac{w_1}{p_1} \ge \frac{w_2}{p_2}
\ge \ldots \ge \frac{w_n}{p_n}$. Then show it is optimal to schedule job 1 first, job 2 second, and so on. This scheduling rule is called Smith’s rule.

Problem 4: Consider the Integer Programming formulation for the minimum cost complete matching problem in a bipartite graph from Exercise 4.6 in the text.

  1. Give an example of a bipartite graph for which there is no feasible solution to the integer programming formulation.
  2. Answer Question 4.6 a.

Problem 5: Answer Question 4.6 b.

Schedule for presentations

Farshad Barahimi: Tue Nov 19, 1:40 PM: Shortest superstring problem.
A. Golovnev, A.S. Kulikov, and I. Mihajlin, Approximating Shortest Superstring Problem Using de Bruijn Graphs. In CPM 2013, Lect. Notes Comput. Sci. 7922:120–129, 2013.

Regular lecture: Tue Nov 19, 2:20 PM.

Mark Thom: Thr Nov 21, 1:40 PM : Canadian traveller problem.
Liao, Chung-Shou, and Yamming Huang. “Generalized Canadian traveller problems.” Journal of Combinatorial Optimization (2013): 1-12.

Jayati Law: Thr Nov 21, 2:20 PM : A PTAS for the max-colouring problem in trees.
Pemmaraju, Sriram V., and Rajiv Raman. “Approximation algorithms for the max-coloring problem.” Automata, languages and programming. Springer Berlin Heidelberg, 2005. 1064-1075.

Farnoush Davoodi: Tue Nov 26, 1:40 PM : Greedy algorithms for the minimum knapsack problem.
J. Csirik, J. B. G. Frenk, M. Labbe, and S. Zhang. Heuristics for the 0-1 min-knapsack ´ problem. Acta Cybernetica, 10(1-2):15-20, 1991.

Jahan Kawsar: Tue Nov 26, 2:20 PM : Primal-dual algorithm for the minimum knapsack problem.
Section 7.5 in the text.

Mohammad Akbari: Thr Nov 28, 1:40 PM : Asymmetric TSP.
“Frieze, A.M., Galbiati, G., and Maffioli, F. [1982]: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12 (1982), 23–39″.

Sina Golestanirad: Tue Nov 28, 2:20 PM: Partial set cover.
Covering Analysis of the Greedy Algorithm for Partial Cover, Tapio Elomaa and Jussi Kujala, LNCS 6060, pp. 102-113, 2010.

Solutions to midterm and assignments

Midterm questions:

Midterm solutions:

Assignment 2 questions:

Assignment 2 solutions:

Assignment 3 questions:

Assignment 3 solutions:

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:

  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.

[course wbpage]