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

Lecture

Integer Programming: John's Theorem

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 concept of integer programming, focusing on John's Theorem and its application to compute the John ellipsoid for complete shortest vector computations in convex bodies. It also discusses how general integer programming can be reduced to shortest vector computations, highlighting the open problem of solving integer programming as efficiently as for ellipsoids.

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

Related concepts (32)

Earth ellipsoid

An Earth ellipsoid or Earth spheroid is a mathematical figure approximating the Earth's form, used as a reference frame for computations in geodesy, astronomy, and the geosciences. Various different ellipsoids have been used as approximations. It is a spheroid (an ellipsoid of revolution) whose minor axis (shorter diameter), which connects the geographical North Pole and South Pole, is approximately aligned with the Earth's axis of rotation.

Hayford ellipsoid

The Hayford ellipsoid is a geodetic reference ellipsoid, named after the US geodesist John Fillmore Hayford (1868–1925), which was introduced in 1910. The Hayford ellipsoid was also referred to as the International ellipsoid 1924 after it had been adopted by the International Union of Geodesy and Geophysics IUGG in 1924, and was recommended for use all over the world. Many countries retained their previous ellipsoids. The Hayford ellipsoid is defined by its semi-major axis a = 6378388.000m and its flattening f = 1:297.

Ellipsoid

An ellipsoid is a surface that can be obtained from a sphere by deforming it by means of directional scalings, or more generally, of an affine transformation. An ellipsoid is a quadric surface; that is, a surface that may be defined as the zero set of a polynomial of degree two in three variables. Among quadric surfaces, an ellipsoid is characterized by either of the two following properties. Every planar cross section is either an ellipse, or is empty, or is reduced to a single point (this explains the name, meaning "ellipse-like").

Geodesics on an ellipsoid

The study of geodesics on an ellipsoid arose in connection with geodesy specifically with the solution of triangulation networks. The figure of the Earth is well approximated by an oblate ellipsoid, a slightly flattened sphere. A geodesic is the shortest path between two points on a curved surface, analogous to a straight line on a plane surface. The solution of a triangulation network on an ellipsoid is therefore a set of exercises in spheroidal trigonometry .

Bessel ellipsoid

The Bessel ellipsoid (or Bessel 1841) is an important reference ellipsoid of geodesy. It is currently used by several countries for their national geodetic surveys, but will be replaced in the next decades by modern ellipsoids of satellite geodesy. The Bessel ellipsoid was derived in 1841 by Friedrich Wilhelm Bessel, based on several arc measurements and other data of continental geodetic networks of Europe, Russia and the British Survey of India.

Related lectures (48)

Unweighted Bipartite Matching

Introduces unweighted bipartite matching and its solution using linear programming and the simplex method.

Approximation Algorithms

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

Hamiltonian dynamics on convex polytopes

Explores Hamiltonian dynamics on convex polytopes, covering symplectic capacities, EHZ capacity, and systolic ratio maximizers.

Coordinates and Projection Systems MOOC: Geographical Information Systems 1

Explores scales, coordinate systems, map projections, and legal positioning references.

Harmonic Forms: Main Theorem