SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Pseudo-Boolean Optimization - NTIN096
Title: Pseudo-Booleovská optimalizace
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2019
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: not taught
Language: English
Teaching methods: full-time
Teaching methods: full-time
Guarantor: prof. RNDr. Ondřej Čepek, Ph.D.
Class: Informatika Mgr. - volitelný
Informatika Mgr. - Teoretická informatika
Classification: Informatics > Informatics, Software Applications, Computer Graphics and Geometry, Database Systems, Didactics of Informatics, Discrete Mathematics, External Subjects, General Subjects, Computer and Formal Linguistics, Optimalization, Programming, Software Engineering, Theoretical Computer Science, Theoretical Computer Science
Annotation -
Last update: T_KTI (16.05.2011)
This course is suitable for all master and doctoral students who have acquired at least basic knowledge of mathematical logic, graph theory, network flows, and complexity of algorithms. The course covers several areas of interesting problems centerted around Pseudo-Boolean functions. A particular emphasis will be given to applications of Pseudo-Boolean functions to solving hard optimization problems.
Aim of the course -
Last update: RNDr. Jan Hric (07.06.2019)


Course completion requirements -
Last update: RNDr. Jan Hric (07.06.2019)


Literature -
Last update: prof. RNDr. Ondřej Čepek, Ph.D. (30.04.2015)

Selected papers from journals, which are relevant for the covered materiál, in particular from Discrete Applied Mathematics and from

Annals of Mathematics and Artificial Intelligence.

Syllabus -
Last update: T_KTI (16.05.2011)

1. Basic definitions and notation, examples of optimization problems which can be formulated as Pseudo-Boolean minimization or maximization.

2. Representations of Pseudo-Boolean functions (multi=linear polynomials, posiforms) and transformations between them.

3. Rounding, derandomization, local optima.

4. Reductions of general optimization to quadratic one.

5. Posiform maximization.

6. Applications to game theory.

7. Quadratic optimization and roof duality.

8. Persistency and the connection to network flows.

9. Generalizations of roof duality, hierarchy of bounds.

10. Aproximations.

11. Special classes.

Charles University | Information system of Charles University |