课程大纲

COURSE SYLLABUS

1.

课程代码/名称

Course Code/Title

CSE5003/高级算法 Advanced Algorithms

2.

课程性质

Compulsory/Elective

Elective

3.

课程学分/学时

Course Credit/Hours

3/64

4.

授课语言

Teaching Language

英文 English

5.

授课教师

Instructor(s)

Hisao Ishibuchi

6.

是否面向本科生开放

Open to undergraduates

or not

Yes

7.

先修要求

Pre-requisites

（ 如 面 向 本 科 生 开 放 ， 请 注 明 区 分 内 容 。 If the course is open to

undergraduates, please indicate the difference.）

CS208 算 法 设 计 与 分 析 Algorithm Design and Analysis (for undergraduate

students)

For postgraduate students, no prerequisites.

8.

教学目标

Course Objectives

This course explains various algorithms for a wide variety of combinatorial optimization problems such as load

balancing, center selection, set covering, vertex cover, disjoint path, and knapsack problems. As a related topic to

center selection, some clustering algorithms are also explained. For each problem, a greedy algorithm is firstly

explained. Students will learn the mechanism of the greedy algorithm. Next, a theoretical lower bound of the solution

quality obtained by the greedy algorithm is derived. Students will learn how to evaluate the greedy algorithm

theoretically. Then it is explained that the performance of the greedy algorithm depends on some randomness such

as a random initial choice and a random tiebreak. Appropriate handling of such randomness is discussed. Finally,

the greedy algorithm is further analyzed by applying to various problem instances. Students will deeply understand

the mechanism of the greedy algorithm by creating both easy and difficult problem instances. Students will also

understand how to evaluate the greedy algorithm empirically, especially the importance of appropriate selection of

test problem instances. After explaining the greedy algorithm for each problem, some other approaches are

explained. They are linear programming-based relaxation for load balancing and vertex cover, local search, dynamic

programming, and branch-and-bound for knapsack problems. For the vertex cover problem, three algorithms are

compared: a pricing method, a greedy set cover algorithm, and a linear program-based relaxation method. Students

will learn that the performance of each algorithm depends on the characteristic features of a problem instance: No

algorithm work well on all problem instances.

9.

教学方法

Teaching Methods

Lectures, weekly assignments and presentations.

10.

教学内容

Course Contents

Section 1

Greedy nearest neighbor TSP algorithm

[Lab 1] Creation of test problems to explain the greedy nearest neighbor TSP

algorithm

Section 2

Greedy load balancing.

- Short presentations by students on clustering.

- Taxonomy of optimization: approximate optimization (greedy, iterated

improvement) and exact optimization.

- Greedy load balancing algorithm.

- Theoretical lower bound of the solution quality.

[Lab 2] Implementation of the greedy load balancing algorithm. Creation of simple

and difficult problem instances.

Section 3

Sorted greedy load balancing.

- Short presentations by students on greedy load balancing.

- Dependency of the performance of the greedy load balancing algorithm on the

order of jobs.

- Sorted greedy load balancing algorithm.

- Theoretical lower bound of the solution quality

[Lab 3] Implementation of the sorted greedy load balancing algorithm. Creation of

simple and difficult problem instances.

Section 4

Center selection.

- Short presentations by students on sorted greedy load balancing.

- Virtual center selection algorithm.

- Center selection algorithm.

- Theoretical lower bound of the solution quality.

[Lab 4] Implementation of the center selection algorithm. Creation of simple and

difficult problem instances.

Section 5

Clustering.

- Short presentations by students on center selection.

- Dependency of the result of the center selection algorithm on the choice of the

first site.

- k-means algorithm.

- Choice of initial cluster centers.

- Choice of the number of clusters.

[Lab 5] Implementation of the k-means algorithm. Design of an initialization

method.

Section 6

Fuzzy clustering.

- Short presentations by students on clustering.

- Fuzzy c-means algorithm.

- Comparison between k-means and fuzzy c-means.

- Effect of the parameter m in the fuzzy c-means algorithm on clustering results.

[Lab 6] Implementation of the fuzzy c-means algorithm. Creation of a data set to

clearly demonstrate the difference between c-means and fuzzy k-means. Creation

of a data set to clearly demonstrate the effect of m on clustering results by fuzzy k-

means.

Section 7

Set cover.

- Short presentations by students on fuzzy clustering.

- Greedy set cover algorithm.

- Theoretical lower bound of the solution quality.

[Lab 7] Implementation of the greedy set cover algorithm. Creation of simple and

difficult problem instances.

Section 8

Vertex cover.

- Short presentations by students on set cover.

- Reformulation of vertex cover problems as set cover problems.

- Pricing method.

- Theoretical lower bound of the solution quality.

[Lab 8] Implementation of the pricing method. Creation of simple and difficult

problem instances. Comparison between the greedy set cover algorithm and the

pricing method for vertex cover.

Section 9

Greedy set cover algorithm and pricing method.

- Short presentations by students on vertex cover.

- Comparison between the greedy set cover algorithm and the pricing method.

- Linear programming.

[Lab 9] Download of some linear programming software packages. Their

comparison on large-scale linear programming problem instances.

Section 10

Linear programming-based relaxation method for vertex cover.

- Short presentations by students on linear programming.

- Relaxation problems of integer programming problems.

- Linear programming-based relaxation method for vertex cover.

- Theoretical lower bound of the solution quality.

[Lab 10] Comparison among the greedy set cover algorithm, the pricing method

and the linear programming-based relaxation method for vertex cover by creating a

difficult problem instance for each method.

Section 11

Generalized load balancing.

- Short presentations by students on the performance comparison of the three

methods.

- Generalization of the load balancing problem.

- Linear programming-based relaxation method for generalized load balancing.

- Theoretical lower bound of the solution quality.

[Lab 11] Creation of a problem instance where a graph with no cycle is obtained.

Creation of another problem where a graph with one or two cycles are obtained.

Section 12

Disjoint paths problem with the edge capacity c = 1.

- Short presentations by students on generalized load balancing.

- Greedy disjoint paths algorithm.

- Theoretical lower bound of the solution quality.

[Lab 12] Creation of easy and difficult problem instances.

Section 13

Disjoint paths problem with the edge capacity c > 1.

- Short presentations by students on disjoint paths with c = 1.

- Pricing method for disjoint paths with c > 1.

- Theoretical lower bound of the solution quality.

[Lab 13] Creation of easy and difficult problem instances for the pricing method

with c = 2.

Section 14

Knapsack Problem: Greedy algorithm

- Short presentations by students on disjoint paths with c = 2.

- Greedy algorithm.

- Theoretical lower bound of the solution quality.

[Lab 14] Implementation of the greedy algorithm. Creation of easy and difficult

problem instances.

Section 15

Knapsack Problem: Exact optimization algorithms and local search

- Short presentations by students on the greedy algorithm for knapsack

problems.

- Branch-and-bound algorithm.

- Implementation issues of branch-and-bound.

- Local search.

- Neighborhood structure.

- Variable neighborhood search.

- Iterated local search.

- Constraint handling.

- Representation of solutions: 0-1 variables, real number variables, and

permutations.

[Lab 15] Preparation for the final presentation on algorithms.

Section 16

Final presentation on algorithms.

[Lab 16] Final presentation on algorithms (continue).

11.

课程考核

Course Assessment

（

○

1

考核形式 Form of examination；

○

2

.分数构成 grading policy；

○

3

如面向本科生开放，请注明区分内容。

If the course is open to undergraduates, please indicate the difference.）

Class performance including attendance, assignments and presentations: 40%

Final presentation: 10%

Final examination: 50%

(no difference between postgraduate and undergraduate students)

12.

教材及其它参考资料

Textbook and Supplementary Readings

Supplementary Readings:

Book Title: Algorithm Design

Authors: Jon Kleinberg and Eva Tardos

Publisher: PEARSON Addison Wesley