CSE 347 Analysis of Algorithms
Homework 8: Approximation Algorithms
Approximation Algorithms代写
Approximation Algorithms代写 This homework must be completed and submitted electronically. Formatting standards, submission procedures…
This homework must be completed and submitted electronically. Formatting standards, submission procedures, and (optional) document templates for homeworks may be found at
https://classes.engineering.wustl.edu/cse347/ehomework/ehomework-guide.html
Advice on how to compose homeworks electronically, with links to relevant documentation for several dif- ferent composition tools, may be found at
https://classes.engineering.wustl.edu/cse347/ehomework/composing-tips.html
Please remember to Approximation Algorithms代写
- typesetyour homework;
- includea header with your name, 6-digit student ID, and the homework number at the top of each page;
- includeany figures (typeset or hand-drawn) inline or as floats;
- uploadand submit your PDF to Gradescope before class time on the due date;
- selectthe pages corresponding to each problem after uploading the PDF.
Always show your work.
- Solve Kleinberg Tardos Problem 11.3. (Part (a): 10%, Part (b): 40%)
- Solve Kleinberg and Tardos Problem 11.10.
.
Note: max independent set on an arbitrary graph is known not to be approximable to within better than a factor that grows polynomially in the graph size unless P=NP. This problem illustrates that some hard optimization problems can often be better approximated on a restricted subset of inputs.
