The catalog

All problems

Every statement in the catalog, readable in place. Filters apply instantly; search covers names, IDs, and the LaTeX statements themselves.

Showing 10 of 280 problems in Mathematical optimization

ANAL-FA-015

Kannan–Lovász–Simonovits (KLS) conjecture

LandmarkConjecture1995

There is a universal constant

C < \infty

such that for every

n

, every log-concave probability measure

μ

R^{n}

satisfying

\int x d μ (x) = 0

and

\int x_{i} x_{j} d μ (x) = δ_{ij}

, and every locally Lipschitz

f : R^{n} \to R

Var_{μ} (f) \leq C \int_{R^{n}} ∥\nabla f (x) ∥_{2}^{2} d μ (x) .

OR-001

Metric-TSP subtour-LP $4/3$ conjecture

LandmarkConjecturec. 1980

For every integer

n \geq 3

, let

K_{n} = (V, E)

, and let

c : E \to R_{\geq 0}

satisfy

c_{{u, v}} \leq c_{{u, w}} + c_{{w, v}}

for all distinct

u, v, w

. Let

TSP (c)

be the minimum

c

-length of a Hamilton cycle, and define

HK (c) = min ⎩ ⎨ ⎧ e \in E \sum c_{e} x_{e} : x_{e} \geq 0, e \in δ (v) \sum x_{e} = 2 (v \in V), e \in δ (S) \sum x_{e} \geq 2 (\emptyset \neq = S ⊊ V) ⎭ ⎬ ⎫,

where

δ (S)

is the set of edges having exactly one endpoint in

S

. Then, with the supremum restricted to instances satisfying

HK (c) > 0

n, c sup \frac{TSP ( c )}{HK ( c )} = \frac{4}{3} .

OR-002

Strongly polynomial finite Markov decision processes

MajorOpen problemc. 1983

There is a strongly polynomial algorithm which, given a finite state set

S

, finite nonempty action sets

A_{s}

, rational transition probabilities

p (t ∣ s, a)

, rational rewards

r (s, a)

, and rational

0 < γ < 1

, returns a stationary deterministic policy maximizing

E_{s}^{π} [k = 0 \sum \infty γ^{k} r (S_{k}, π (S_{k}))]

simultaneously for every initial state

s

, using a number of arithmetic operations polynomial only in

∣ S ∣ + \sum_{s} ∣ A_{s} ∣

and maintaining intermediate encoding lengths polynomial in the input length.

OR-004

Modified integer round-up property for bin packing

MajorConjecturec. 1985

Given item sizes

a_{1}, \dots, a_{n} \in (0, 1]

, let

P = {P \subseteq {1, \dots, n} : \sum_{i \in P} a_{i} \leq 1}

. Let

OPT

be the minimum number of patterns from

P

, with repetitions allowed, whose incidence vectors sum coordinatewise to at least

1

, and let

OPT_{f} = min {P \in P \sum x_{P} : x_{P} \geq 0, P ∋ i \sum x_{P} \geq 1 (i = 1, \dots, n)} .

Then

OPT \leq ⌈ OPT_{f} ⌉ + 1

OPT-001

Strongly polynomial linear programming

LandmarkOpen problem1983

There is an algorithm which, for every rational

A \in Q^{m \times n}

b \in Q^{m}

, and

c \in Q^{n}

, decides whether

max {c^{T} x : A x \leq b, x \in R^{n}}

is infeasible, unbounded, or has an optimum and, in the last case, returns an exact optimal solution, using at most

p (m, n)

elementary arithmetic operations and comparisons for one fixed polynomial

p

, while every intermediate rational number has encoding length polynomial in the total input encoding length.

OPT-002

Polynomial pivot rule for the simplex method

LandmarkOpen problemc. 1972

There exist a deterministic or randomized simplex pivot rule and a polynomial

p

such that, for every bounded nondegenerate rational linear program

max {c^{T} x : A x = b, x \geq 0}, A \in Q^{m \times n},

and every feasible starting basis, the simplex method using that rule reaches an optimal basis after at most

p (m, n)

pivots (in expectation over the rule's randomness in the randomized case).

OPT-003

Polynomial Hirsch conjecture

MajorConjecturec. 1992

There is a polynomial

p \in R [X, Y]

such that, for all integers

d \geq 1

n \geq d + 1

, and every

d

-dimensional convex polytope

P

having exactly

n

facets, the graph whose vertices and edges are the

0

- and

1

-dimensional faces of

P

has diameter at most

p (n, d)

TCS-008

Unique Games Conjecture

LandmarkConjecture2002

For every

ε, δ \in (0, 1)

, there is an alphabet size

q

, where

[q] = {1, \dots, q}

, such that the following promise problem is

NP

-hard. The input is a finite directed constraint graph in which every arc

u \to v

carries a permutation

π_{uv}

[q]

; a labeling

ℓ : V \to [q]

satisfies that arc when

ℓ (v) = π_{uv} (ℓ (u))

. Distinguish

YES: NO: some labeling satisfies at least 1 - ε of the constraints; every labeling satisfies at most δ of them.

MATH-PHYS-007

Optimal Lieb–Oxford constant

MajorExact constant problemc. 1981

For each

N \geq 1

, let

P_{N}

be the symmetric probability measures

P

(R^{3})^{N}

with finite Coulomb energy and one-particle density

ρ_{P}

, normalized by

\int_{R^{3}} ρ_{P} = N

. Define

E_{ind} (P) = \int_{(R^{3})^{N}} i < j \sum \frac{1}{∣ x _{i} - x _{j} ∣} d P (x_{1}, \dots, x_{N}) - \frac{1}{2} \iint_{R^{3} \times R^{3}} \frac{ρ _{P} ( x ) ρ _{P} ( y )}{∣ x - y ∣} d x d y

and

C_{LO} = N \geq 1 sup P \in P_{N} sup \frac{- E _{ind} ( P )}{\int _{R^{3}} ρ _{P} ( x ) ^{4/3} d x} .

Q_{L} = [- L /2, L /2]^{3}

, define

e_{UEG} = L \to \infty L^{3} \in N lim L^{- 3} in f {E_{ind} (P) : P \in P_{L^{3}}, ρ_{P} = 1_{Q_{L}}} .

Then

C_{LO} = - e_{UEG}

CTRL-001

Generalized Belgian Chocolate Problem

MajorExact constant problem1994

Call a nonzero real polynomial Hurwitz stable if all of its complex zeros have strictly negative real part. Define

δ_{*} = sup {δ \in (0, 1) : there exist nonzero Hurwitz-stable x, y \in R [s] such that (s^{2} - 2 δs + 1) x (s) + (s^{2} - 1) y (s) is Hurwitz stable} .

Determine

δ_{*}

exactly.