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 14 of 280 problems in Operations research

GRAPH-004

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-003

Beardwood–Halton–Hammersley planar TSP constant

MajorExact constant problem1959

Let

X_{1}, X_{2}, \dots

be independent random points uniformly distributed on

[0, 1]^{2}

, and let

L_{n}

be the minimum Euclidean length of a closed polygonal tour visiting

X_{1}, \dots, X_{n}

. The almost-sure limit

β_{2} = n \to \infty lim \frac{L _{n}}{n}

exists and is a deterministic positive constant. Determine

β_{2}

exactly.

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).

TCS-009

Exponential Time Hypothesis

LandmarkConjecture1999

No deterministic algorithm decides satisfiability of

3

-CNF formulas with

n

variables in time

2^{o (n)}

, where a

3

-CNF is a conjunction of clauses, each containing at most three literals.

TCS-010

Strong Exponential Time Hypothesis

MajorConjecture2001

For every

ε > 0

there exists an integer

k \geq 3

such that

k

-SAT—satisfiability of CNF formulas whose clauses contain at most

k

literals—on

n

variables cannot be decided by a deterministic algorithm in time

O ((2 - ε)^{n}) .

TCS-019

Li–Li Undirected Network Coding Conjecture

MajorConjecture2004

For every finite undirected capacitated network with any finite collection of unicast source--sink pairs, the maximum common rate achievable by arbitrary network coding equals the maximum common rate achievable by fractional multicommodity routing.

GAME-001

Uniform $\varepsilon$ -equilibrium in finite multiplayer stochastic games

MajorConjecturec. 1981

Consider any stochastic game with a finite player set

I

, finite state set

S

, finite nonempty action set

A_{i} (s)

for each player

i

at state

s

, bounded stage payoff

g_{i} (s, a)

for each action profile

a \in \prod_{i \in I} A_{i} (s)

, and transition law

q (\cdot ∣ s, a)

S

. For every

ε > 0

and initial state

s_{0}

, there exist a behavioral-strategy profile

σ

and

N \in N

such that, for every horizon

n \geq N

, every player

i

, and every unilateral behavioral deviation

τ_{i}

E_{s_{0}, σ} [\frac{1}{n} t = 1 \sum n g_{i} (s_{t}, a_{t})] \geq E_{s_{0}, (τ_{i}, σ_{- i})} [\frac{1}{n} t = 1 \sum n g_{i} (s_{t}, a_{t})] - ε,

where

(s_{t}, a_{t})

is the state--action process generated by the indicated strategy profile and transition law.