Category Archives: approx-course

Duration: 24 hours.
Dates:

• Pickup the questions on Wed. Dec 11, 9am – 10am, in my office at C556.
• Drop off the answers on Thr. Dec 12, 9am – 10am, in my office at C556.

I recommend you stay at school for the first hour or so to read and to think about all questions. In case you need clarifications, you can see me in my office until noon on Dec 11. I do not guarantee that I will answer promptly any questions that you might send me by e-mail after Dec 11 at noon.
Attempt all questions.

Topics: everything covered in the course, including the topics from the student presentations. To prepare, attempt the relevant exercises from the textbook.

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.

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.
[paper]
[presentation]

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.
[paper]

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.
[paper]
[presentation]

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.
[paper]
[presentation]

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″.
[paper]

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.
[paper]

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

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

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.

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)