Uusi opinto-opas (sisältäen myös opetusohjelmat) lukuvuodelle 2018-2019 sijaitsee osoitteessa https://opas.peppi.utu.fi . Tältä sivustolta löytyvät enää vanhat opinto-oppaat ja opetusohjelmat.

The new study guide (incl. teaching schedules) for academic year 2018-2019 can be found at https://studyguide.utu.fi. This site contains only previous years' guides.

x !
Arkistoitu opetussuunnitelma 2014–2016
Selaamasi opetussuunnitelma ei ole enää voimassa. Tarkista tiedot voimassa olevasta opetussuunnitelmasta.
SMAT5150 Combinatorial Optimization Algorithms 5 op
Organised by
Applied Mathematics
Person in charge
Department of Mathematics and Statistics, Yury Nikulin
Preceding studies
Recommended:

Learning outcomes

Combinatorial optimization is a branch of optimization dealing with problems where the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution. It includes various optimization problems operating with such combinatorial structures as graphs, networks, matroids, etc. The main aim of this course is to familiarize students with basic and advanced methods exploiting combinatorial topological properties. The complementary aim is to give students more precise understanding of interrelations between different branches of applied mathematics such as linear programming, graph theory and discrete optimization.

Contents

The course will consider the questions of designing efficient algorithms which efficiently exploit combinatorial properties of the problems. Starting with basics of linear programming and duality theory with emphasis on network flow interpretation, the course continues with modern fast algorithms for flow, matching etc. The course ends with highlighting techniques of dealing with practical intractable problems, approximation methods, branch-and-bound, dynamic programming etc.

Teaching methods

Teaching method Contact Online
Lectures 28 h 0 h
Exercises 12 h 0 h

Not lectured 2014-2016.

Teaching language

English

Modes of study

Option 1
Available for:
  • Degree Programme Students
  • Other Students
  • Doctoral Students
  • Exchange Students
Exercise(s)
  • In English
Written exam
  • In English

Evaluation

Numeric 0-5.

Study materials

C. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity; Handouts

Belongs to following study modules

Matematiikan ja tilastotieteen laitos
2014–2015
Teaching
Archived Teaching Schedule. Please refer to current Teaching Shedule.
Implementation details are unavailable.
Matematiikan ja tilastotieteen laitos
Opintokokonaisuudet
Tilastotiede