https://dm865.github.io/exercises/sheet1/2019/01/10/exercises.html

1<!DOCTYPE html>
2<html lang="en-US">
3
4    <head>
5	<meta charset='utf-8'>
6	<meta http-equiv="X-UA-Compatible" content="chrome=1">
7	<meta name="viewport" content="width=device-width,maximum-scale=2">
8	<meta name="description" content="DM865 @ SDU - Heuristics and Approximation Algorithms : Course on Heuristics and Approximation Algorithms">
9	<title>DM865 @ SDU - Heuristics and Approximation Algorithms</title>
10	<link rel="icon" href="https://imada.sdu.dk/favicon.ico"> 
11	<link rel="stylesheet" href="https://www.w3schools.com/w3css/4/w3.css">
12	<link rel="stylesheet" href="https://www.w3schools.com/lib/w3-theme-dark-grey.css">
13	

13<script src="https://www.w3schools.com/lib/w3.js"></script>

13
14	<link rel="stylesheet" type="text/css" media="screen" href="https://dm865.github.io/assets/css/style.css?v=ca262b1104a0c8a305c1a417ef94828a1d20bfae">
15
16
17

18<script type="text/x-mathjax-config">
19  MathJax.Hub.Config({
20    tex2jax: {
21      inlineMath: [ ['$','$'], ["\\(","\\)"] ],
22	displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
23      processEscapes: true
24    }
25  });
26</script>

26

27<script
28  type="text/javascript"
29  charset="utf-8"
30  src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"
31>
32</script>

32

33<script
34  type="text/javascript"
35  charset="utf-8"
36  src="https://vincenttam.github.io/javascripts/MathJaxLocal.js"
37>
38</script>

38
39
40
41
42<!-- Begin Jekyll SEO tag v2.8.0 -->
43<title>Sheet 1 | DM865 @ SDU - Heuristics and Approximation Algorithms</title>
44<meta name="generator" content="Jekyll v3.10.0" />
45<meta property="og:title" content="Sheet 1" />
46<meta property="og:locale" content="en_US" />
47<meta name="description" content="Sheet 1:" />
48<meta property="og:description" content="Sheet 1:" />
49<link rel="canonical" href="https://dm865.github.io/exercises/sheet1/2019/01/10/exercises.html" />
50<meta property="og:url" content="https://dm865.github.io/exercises/sheet1/2019/01/10/exercises.html" />
51<meta property="og:site_name" content="DM865 @ SDU - Heuristics and Approximation Algorithms" />
52<meta property="og:type" content="article" />
53<meta property="article:published_time" content="2019-01-10T08:33:19+00:00" />
54<meta name="twitter:card" content="summary" />
55<meta property="twitter:title" content="Sheet 1" />

56<script type="application/ld+json">
57{"@context":"https://schema.org","@type":"BlogPosting","dateModified":"2019-01-10T08:33:19+00:00","datePublished":"2019-01-10T08:33:19+00:00","description":"Sheet 1:","headline":"Sheet 1","mainEntityOfPage":{"@type":"WebPage","@id":"https://dm865.github.io/exercises/sheet1/2019/01/10/exercises.html"},"url":"https://dm865.github.io/exercises/sheet1/2019/01/10/exercises.html"}</script>

57
58<!-- End Jekyll SEO tag -->
59
60  </head>
61
62  <body>
63
64    <!-- HEADER -->
65      <div id="header_wrap" class="outer">
66        <header class="inner">
67           <!-- <a id="forkme_banner" href="https://github.com/DM865/dm865.github.io">View on GitHub</a> -->
68
69           <h1 id="project_title">DM865 @ SDU - Heuristics and Approximation Algorithms</h1>
70	  <!--           <h2 id="project_tagline">Course on Heuristics and Approximation Algorithms</h2>-->
71          
72        </header>
73    </div>
74
75    <!-- MAIN CONTENT -->
76    <div id="main_content_wrap" class="outer">
77      <section id="main_content" class="inner">
78        <h4 id="sheet-1">Sheet 1:</h4>
79<!-- Exercises for Thursday, February 7 -->
80
81<ol>
82  <li>
83    <p>Let $G$ be a complete undirected graph with non-negative edge
84weights.</p>
85
86    <p>a) Let $W$ denote the maximum weight of any edge in $G$.<br />
87   For each edge $e$, add $W$ to the weight of $e$.<br />
88   Let $G’$ denote the resulting weighted graph.</p>
89
90    <p>Prove that the weights of $G’$ are metric, i.e., prove that
91   they satisfy the triangle inequality.</p>
92
93    <p>b) Argue that a TSP tour in $G$ is optimal, if and only if the
94   corresponding tour in $G’$ is optimal.</p>
95
96    <p>c) Why doesn’t this contradict Theorem 2.9?</p>
97  </li>
98  <li>
99    <p>Argue that (the decision version of) metric TSP is NP-hard.</p>
100  </li>
101  <li>
102    <p>Describe an algorithm for finding an Euler tour in a graph where
103all vertices have even degree.</p>
104  </li>
105  <li>
106    <p>a) Give an example where Christofide’s Algorithm produces a better
107   solution than the Double Tree Algorithm.
108   More specifically, give a graph and concrete runs of the two
109   algorithms on the graph such that Christofide’s Algorithm
110   produces a cycle of smaller total weight than the Double Tree
111   Algorithm.</p>
112
113    <p>b) Do a) again, but such that the Double Tree Algorithm gives the
114   better result.</p>
115
116    <p>c) How many nodes do you need to construct the examples in a) and
117   b)?</p>
118  </li>
119</ol>
120
121<h4 id="sheet-2--">Sheet 2: <a name="sheet2"></a> <!-- Exercises for Friday, February 16 --></h4>
122
123<ol>
124  <li>
125    <p>Read the Python tutorial [No]. You find some starting code from that
126page <a href="https://github.com/DM865/TSP">here</a>.</p>
127  </li>
128  <li>
129    <p>Implement the exact methods: plain enumeration and Held Karp dynamic
130programming algorithm.</p>
131  </li>
132  <li>
133    <p>Following the procedure for Benchmarking described in [No] implement
134and compare as many TSP heuristics as you can. You find a list below,
135in bold the heuristics implemented in [No]. For a description of
136these heuristics see [Be].</p>
137
138    <ul>
139      <li>Heuristics that Grow Fragments
140        <ul>
141          <li><strong>Nearest neighborhood heuristic</strong></li>
142          <li>Double-Ended Nearest Neighbor heuristic</li>
143          <li><strong>Multiple Fragment heuristic (aka, greedy heuristic)</strong></li>
144        </ul>
145      </li>
146      <li>Heuristics that Grow Tours
147        <ul>
148          <li>Nearest Addition</li>
149          <li>Farthest Addition</li>
150          <li>Random Addition</li>
151          <li>Clarke-Wright savings heuristic</li>
152          <li>Nearest Insertion</li>
153          <li>Farthest Insertion</li>
154          <li>Random Insertion</li>
155        </ul>
156      </li>
157      <li>Heuristics based on Trees
158        <ul>
159          <li><strong>Minimum spanning tree heuristic</strong></li>
160          <li>Christofides’ heuristics</li>
161          <li>Fast recursive partitioning heuristic</li>
162        </ul>
163      </li>
164    </ul>
165  </li>
166  <li>
167    <p>In Python kd-trees are already implemented in the module
168<a href="https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.KDTree.html">scipy</a>. Try
169to use them and improve some implementations of the construction
170heuristics described above (you will probably need to change the
171representation of points).</p>
172  </li>
173</ol>
174
175<h4 id="sheet-3--">Sheet 3: <a name="sheet3"></a> <!-- Exercises for Thursday, February 21. --></h4>
176
177<!--
1781. In a 3-opt local search algorithm for the TSP how many possible ways
179   are there to add three new edges once three edges have been removed
180   in order to re-obtain an Hamiltonian tour? Justify your answer.
181-->
182
183<ol>
184  <li>
185    <p>

185In the code available in the
186<a href="https://github.com/DM865/TSP">git repository</a> you find a file
187<code class="language-plaintext highlighter-rouge">local_search.py</code>, which contains an implementation of a 2 opt local
188search. Study the implementation and test the results when the local
189search is executed after different construction heuristics. Is the
190local search implemented in that file a first improvement or a best
191improvement?  Does the 2-opt algorithm improve the results of the
192construction heuristics?  How many steps (changes in the solutions)
193are executed?  Which combination <code class="language-plaintext highlighter-rouge">construction_heuristic</code> + <code class="language-plaintext highlighter-rouge">2_opt</code>
194leads to the best results (including a random initial solution)?</p>
195  </li>
196  <li>
197    <p>Compare the results of a <em>first improvement</em> 2-opt against those of a
198<em>best improvement</em> 2-opt procedure. Is the comparison the same across
199different initial solutions attained by different construction
200heuristics (including a random solution and a canonical sequence)?</p>
201  </li>
202  <li>
203    <p>Try to improve the 2-opt implementation from the previous
204point. Start by adding random choices. Then, improve its execution
205time by adopting some of the techniques explained in class.</p>
206  </li>
207  <li>
208    <p>Consider the traveling salesman problem defined on an incomplete
209graph. How could we encode the problem such that we can approach it
210with the construction heuristics and local search algorithms
211implemented for the complete graph version of the problem?</p>
212  </li>
213  <li>
214    <p>Consider the asymmetric TSP. How can we encode this problem into a
215symmetric TSP, such that we can approach it with the construction
216heuristics and local search algorithms implemented for the symmetric
217version of the problem?</p>
218  </li>
219</ol>
220
221<h4 id="sheet-4--">Sheet 4: <a name="sheet4"></a> <!-- Exercises for Thursday, February 28. --></h4>
222
223<p>Design a 3 exchange iterative improvement procedure for the TSP.  The
224procedure must return a local optimum in the 3 exchange neighborhood.
225Implement the procedure in the framework made
226<a href="https://github.com/DM865/TSP">available in git</a>.
227A template to be completed is available in the file <code class="language-plaintext highlighter-rouge">three_opt.py</code>.</p>
228
229<p>You must only edit this file, you are not allowed to change the other
230files.  When executed, your program will read the instance USA,
231construct a canonical tour and call your iterative improvement
232procedure. The benchmarking called from the main file will take care of
233assessing the quality of your solution.</p>
234
235<p>Describe your algorithm in pseudocode in a one-page document edited with
236Latex. Use the Latex package
237<a href="https://ctan.org/pkg/algorithm2e?lang=en">algorithm2e</a>.</p>
238
239<p>Submit only the file <code class="language-plaintext highlighter-rouge">three_opt.py</code> and the PDF result of your Latex
240pseudocode at this <a href="http://valkyrien.imada.sdu.dk/DOApp/">portal</a>. Keep your
241files anonymous!</p>
242
243<p>You are encouraged to work in pairs at this assignment, in which case it is
244enough that only one submits.</p>
245
246<p>Remember: start out with simple and even inefficient code without
247optimizing for efficiency. Only later, when your initial implementation
248is working and doing what you expect, start looking at efficiency
249improvements of your code (and consider the quality of the solutions as
250well.</p>
251
252<p>Instructions for the submission to http://valkyrien.imada.sdu.dk/DOApp/:</p>
253
254<ul>
255  <li>
256    <p>Submit separately the source code (tgz file) and the description (pdf
257file).</p>
258  </li>
259  <li>
260    <p>Organize the source file like it is organized in the git repository
261from where you got the starting package. Create the archive from the
262root of the repository (that is, the directory that contains <code class="language-plaintext highlighter-rouge">src/</code>)
263using the following command:</p>
264  </li>
265</ul>
266
267<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>tar czvf TSP.tgz * --exclude=.git --exclude=__*
268</code></pre></div></div>
269
270<p>

270Include a Makefile in the src directory. It can be empty.</p>
271
272<h4 id="sheet-5--">Sheet 5: <a name="sheet5"></a> <!-- Exercises for Thursday, March 7. --></h4>
273
274<p>Argue that $\text{Rand}_p$ with $p=\frac{1}{2}(\sqrt{5}-1)$ (the
275algorithm from Section 5.3) can be 
276derandomized to obtain a deterministic $p$-approximation algorithm.</p>
277
278<h4 id="sheet-6--">Sheet 6: <a name="sheet6"></a> <!-- Exercises for Tuesday, March 19. --></h4>
279
280<ol>
281  <li>
282    <p>a) Write down an LP-formulation of the unweighted Vertex Cover problem.</p>
283
284    <p>b) Write down the dual of the LP from a).</p>
285
286    <p>c) Which combinatorial problem does the dual correspond to?</p>
287  </li>
288  <li>
289    <p>Although the unweighted Vertex Cover problem is NP-hard for general
290graphs, there are graph classes that allow for efficient algorithms.
291Design an algorithm that finds a minimum cardinality vertex cover of a
292tree in linear time.</p>
293  </li>
294  <li>
295    <p>a) Assume that you have an algorithm for finding a minimum
296   cardinality vertex cover in a graph.<br />
297   Explain how you can use the algorithm for finding a maximum
298   cardinality independent set.</p>
299
300    <p>b) Does this mean that you can use an approximation algorithm for
301   unweighted Vertex Cover, like the ones in Sections 1.3 and 1.4,
302   for approximating a maximum cardinality independent set?
303   (Hint: What approximation factor could you obtain?)</p>
304  </li>
305</ol>
306
307<h4 id="sheet-7--">Sheet 7: <a name="sheet7"></a> <!-- Exercises for Tuesday, March 26. --></h4>
308
309<ol>
310  <li>
311    <p>Consider the primal-dual algorithm for the unweighted Vertex Cover problem.</p>
312
313    <p>a) What does the algorithm do?</p>
314
315    <p>b) Write down the same algorithm without explicitly using the
316   LP-formulation of the problem.</p>
317
318    <p>c) Give an example showing that the algorithm has an approximation
319   factor of at least 2.</p>
320  </li>
321  <li>
322    <p>Do Exercise 5.7.
323Hint: Using $\lambda = n \cdot \ln n \cdot Z_{\text{LP}}^*$, it is
324possible to obtain a $(3 \ln n)$-approximation algorithm.</p>
325  </li>
326</ol>
327
328<h4 id="sheet-8--">Sheet 8: <a name="sheet8"></a> <!-- Exercise for Thursday, May 2. --></h4>
329
330<ol>
331  <li>
332    <p>Solve Exercise 3.1.</p>
333
334    <p>Hint: For proving the appoximation ratio it may be helpful to first consider the algorithm that chooses between the sets {1,2,…,k} and {k+1}.</p>
335  </li>
336</ol>
337
338<h4 id="sheet-9--">Sheet 9: <a name="sheet9"></a> <!-- Exercise for Tuesday, May 7. --></h4>
339
340<p>Classfy the following scheduling applications:</p>
341
342<ol>
343  <li>
344    <p>Gate Assignment at an Airport</p>
345
346    <ul>
347      <li>
348        <p>Airline terminal at a airport with dozes of gates and hundreds of arrivals each day.</p>
349      </li>
350      <li>
351        <p>Gates and Airplanes have different characteristics</p>
352      </li>
353      <li>
354        <p>Airplanes follow a certain schedule</p>
355      </li>
356      <li>
357        <p>During the time the plane occupies a gate, it must go through a series of operations</p>
358      </li>
359      <li>
360        <p>There is a scheduled departure time (due date)</p>
361      </li>
362      <li>
363        <p>Performance measured in terms of on time departures.</p>
364      </li>
365    </ul>
366  </li>
367  <li>
368    <p>Scheduling Tasks in a Central Processing Unit (CPU)</p>
369
370    <ul>
371      <li>
372        <p>Multitasking operating system</p>
373      </li>
374      <li>
375        <p>Schedule time that the CPU devotes to the different programs</p>
376      </li>
377      <li>
378        <p>Exact processing time unknown but an expected value might be known</p>
379      </li>
380      <li>
381        <p>Each program has a certain priority level</p>
382      </li>
383      <li>
384        <p>Tasks are often sliced into little pieces. They are then rotated
385such that low priority tasks of short duration do not stay for
386ever in the system.</p>
387      </li>
388      <li>
389        <p>Minimize  expected time %, ie, sum of the weighted completion times  for all tasks</p>
390      </li>
391    </ul>
392  </li>
393  <li>
394    <p>Paper bag factory</p>
395
396    <ul>
397      <li>
398        <p>Basic raw material for such an operation are rolls of paper.</p>
399      </li>
400      <li>
401        <p>Production process consists of three stages: printing of the logo, gluing of the side of the bag, sewing of one end or both ends.</p>
402      </li>
403      <li>
404        <p>Each stage consists of a number of machines which are not necessarily identical.</p>
405      </li>
406      <li>
407        <p>Each production order indicates a given quantity of a specific bag
408that has to be produced and shipped by a committed shipping date or due date.</p>
409      </li>
410      <li>
411        <p>Processing times for the different operations are proportional to the number of bags ordered.</p>
412      </li>
413      <li>
414        <p>There are setup times when switching over different types of bags (colors, sizes) that depend on the similarities between the two consecutive orders</p>
415      </li>
416      <li>
417        <p>A late delivery implies a penalty that depends on the importance 
418of the order or the client and the tardiness of the delivery.</p>
419      </li>
420    </ul>
421  </li>
422</ol>
423
424<h4 id="sheet-10--">Sheet 10: <a name="sheet10"></a> <!-- Exercises for Monday, May 13. --></h4>
425
426<ol>
427  <li>
428    <p>Solve Exercise 2.2</p>
429  </li>
430  <li>
431    <p>

431In the lecture on Tuesday, May 21, we proved that the approximation
432ratio of the List Scheduling algorithm is <strong>at most</strong>
433$2−\frac{1}{m}$. Prove that this bound is tight, i.e., prove that the
434ratio is <strong>at least</strong> $2−\frac{1}{m}$.</p>
435  </li>
436</ol>
437
438
439      </section>
440    </div>
441
442    <!-- FOOTER  -->
443    <div id="footer_wrap" class="outer">
444      <footer class="inner">
445          <p>Hosted on <a href="https://pages.github.com">GitHub Pages</a> using <a href="https://github.com/pages-themes/slate">Slate theme</a> for <a href="https://jekyllrb.com">Jekyll</a></p>
446      </footer>
447    </div>
448
449  

449<script>
450         function myFunction(id) {
451             var x = document.getElementById(id);
452             if (x.className.indexOf("w3-show") == -1) {
453                 x.className += " w3-show";
454             } else { 
455                 x.className = x.className.replace(" w3-show", "");
456             }
457         }
458        </script>

458
459
460    
461  </body>
462</html>