Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Integer Optimization: Theory and Applications

In course

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years. ...

Description

This lecture covers the fundamentals of integer optimization, including integer programming, dynamic programming, approximation algorithms, and set-cover problems. The instructor discusses the complexity of integer programming, the linear programming relaxation, branch & bound, and the knapsack problem. The lecture also explores topics such as Steinitz Lemma, GCD, Euclidean Algorithm, lattices, Minkowski's Theorem, and transference bounds. Additionally, the lecture delves into the application of integer programming in fixed dimension and algorithms for the Shortest Vector Problem (SVP).

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Ontological neighbourhood

Theoretical computer science

Theory of computation: Computational complexity theory

Related concepts (32)

Integer programming

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.

Knapsack problem

The knapsack problem is the following problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

Complexity class

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements.

Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time.

Linear programming

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

Related lectures (46)

Approximation Algorithms

Covers approximation algorithms for optimization problems, LP relaxation, and randomized rounding techniques.

Solving Parity Games in Practice

Explores practical aspects of solving parity games, including winning strategies, algorithms, complexity, determinism, and heuristic approaches.

Complex Systems: Critical Phenomena

Explores critical phenomena in complex systems, including stochastic objects, percolation, and combinatorial optimization.

Minimum Spanning Trees: Prim's Algorithm

Explores Prim's algorithm for minimum spanning trees and introduces the Traveling Salesman Problem.

Complexity & Induction: Algorithms & Proofs