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

Lecture

Lower Bounds for Analytical TSP

Description

This lecture covers two lower bounds for the analytical Traveling Salesman Problem (TSP), focusing on the H(K) and H'(r) functions, the Bishop-Jones theorem, and the compactness of KSC sets. The instructor discusses the relationship between H(K) and H'(r), the properties of universal curves, and the application of these bounds in TSP analysis.

Official source

Related concepts (17)

Chernoff bound

In probability theory, a Chernoff bound is an exponentially decreasing upper bound on the tail of a random variable based on its moment generating function. The minimum of all such exponential bounds forms the Chernoff or Chernoff-Cramér bound, which may decay faster than exponential (e.g. sub-Gaussian). It is especially useful for sums of independent random variables, such as sums of Bernoulli random variables. The bound is commonly named after Herman Chernoff who described the method in a 1952 paper, though Chernoff himself attributed it to Herman Rubin.

Upper and lower bounds

In mathematics, particularly in order theory, an upper bound or majorant of a subset S of some preordered set (K, ≤) is an element of K that is greater than or equal to every element of S. Dually, a lower bound or minorant of S is defined to be an element of K that is less than or equal to every element of S. A set with an upper (respectively, lower) bound is said to be bounded from above or majorized (respectively bounded from below or minorized) by that bound.

Concentration inequality

In probability theory, concentration inequalities provide bounds on how a random variable deviates from some value (typically, its expected value). The law of large numbers of classical probability theory states that sums of independent random variables are, under very mild conditions, close to their expectation with a large probability. Such sums are the most basic examples of random variables concentrated around their mean. Recent results show that such behavior is shared by other functions of independent random variables.

Infimum and supremum

In mathematics, the infimum (abbreviated inf; plural infima) of a subset of a partially ordered set is the greatest element in that is less than or equal to each element of if such an element exists. In other words, it is the greatest element of that is lower or equal to the lowest element of . Consequently, the term greatest lower bound (abbreviated as ) is also commonly used. The supremum (abbreviated sup; plural suprema) of a subset of a partially ordered set is the least element in that is greater than or equal to each element of if such an element exists.

Dust

Dust is made of fine particles of solid matter. On Earth, it generally consists of atmospheric particulates (particles in the atmosphere) that come from various sources such as soil lifted by wind (an aeolian process), volcanic eruptions, and pollution. Dust in homes is composed of about 20–50% dead skin cells. The rest, and in offices, and other human environments is composed of small amounts of plant pollen, human hairs, animal fur, textile fibers, paper fibers, minerals from outdoor soil, burnt meteorite particles, and many other materials which may be found in the local environment.

Related lectures (6)

Relations, Sequences and Summations

Covers topics on relations, sequences, and summations, including lattices, recurrence relations, and sigma notation.

Distribution Estimation

Explores distribution estimation methods, fitness functions, and the importance of selecting the right estimator for accurate results.

Exact Methods for Integer Optimization MOOC: Optimization: principles and algorithms - Network and discrete optimization

Covers exact methods for integer optimization, emphasizing Branch and Bound techniques.