By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

The approximation threshold for metric k-median

For every fixed ε>0\varepsilon > 0, there is a deterministic polynomial-time algorithm which, given a finite rational metric kk-median instance with specified candidate facilities and 1≤k≤∣F∣1 \le k \le |F|, returns S⊆FS \subseteq F with ∣S∣≤k|S| \le k such that ∑j∈Jd(j,S)≤(1+2e+ε)OPTk\sum_{j \in J} d(j, S) \le \left(1 + \frac{2}{e} + \varepsilon\right) \mathrm{OPT}_k, where the running time is polynomial in the binary encoding length of the instance (with the polynomial possibly depending on ε\varepsilon).

If P≠NPP \neq NP, the infimum of deterministic polynomial-time approximation factors for metric kk-median with specified candidate facilities is 1+2/e1 + 2/e.

For every η>0\eta > 0, there is a constant Δ0\Delta_0 such that for any constant even integer Δ≥Δ0\Delta \ge \Delta_0 and g=1/Δg = 1/\Delta, there is a randomized procedure running in expected polynomial time on rational inputs that rounds feasible rational openings 0≤yi≤10 \le y_i \le 1 to grid openings y~i∈[0,1]∩gZ\widetilde{y}_i \in [0, 1] \cap g\mathbb{Z} (allowing polynomially many co-located labeled facility pieces) with 1≤∑iy~i≤∑iyi+3g1 \le \sum_i \widetilde{y}_i \le \sum_i y_i + 3g for every output and expected nearest-unit assignment cost of every client jj at most (1+η)Vj(1 + \eta)V_j.

On a finite index set II with probability weights (πi)i∈I(\pi_i)_{i \in I} and Di≥0D_i \ge 0 satisfying EiDi=1\mathbb{E}_i D_i = 1, for fixed 0≤x≤10 \le x \le 1, 0<y≤10 < y \le 1, qti∈[0,1]q_{ti} \in [0, 1], and Ri≥0R_i \ge 0 satisfying Ri(1−Pqti)≤Di+DtR_i(1 - P q_{ti}) \le D_i + D_t whenever qti<1q_{ti} < 1, and any si∈[0,1]s_i \in [0, 1] with ri=Etqtir_i = \mathbb{E}_t q_{ti} and Ci=1−PsiC_i = 1 - P s_i, the finite comparison inequality (4.4) holds with upper bound 2Θ=2P(y−x)2/y2\Theta = 2P(y-x)^2/y.

For every fixed τ>0\tau > 0 and all sufficiently large constant integers Δ\Delta (g=1/Δg = 1/\Delta), given openings y~i∈[0,1]∩gZ\widetilde{y}_i \in [0, 1] \cap g\mathbb{Z} of total mass M≥1M \ge 1, there is a constant C=C(τ,Δ)C = C(\tau, \Delta) and a randomized algorithm of expected polynomial running time that outputs a set OO of facilities with ∣O∣≤M+C|O| \le M + C and Ed(j,O)≤(1+2/e+τ)Vj,0\mathbb{E} d(j, O) \le (1 + 2/e + \tau) V_{j,0} for every client jj.

For every fixed ε>0\varepsilon > 0, there is an instance-independent integer c≥0c \ge 0 and a deterministic polynomial-time algorithm for metric kk-median that opens at most k+ck + c facilities and has total connection cost at most (1+2/e+ε)LP≤(1+2/e+ε)OPTk(1 + 2/e + \varepsilon)\mathrm{LP} \le (1 + 2/e + \varepsilon)\mathrm{OPT}_k.

Methods

Constant-grid preparation using separated representatives, disjoint bundles, coupled supplier stars, dependent rounding (Lemma 3.2), and deficit clipping.

Source excerpts

“We first put the fractional openings on a sufficiently fine constant grid. The use of separated representatives and bundles is motivated by the discretization approach in [6]. The construction below rounds a bundle’s missing assignment mass together with the facilities that can supply it.” · Show in paper

Tapered iterative rounding with distance-dependent edge marginals, balanced and biased unbalanced batches, and forced openings for heavy sources.

Source excerpts

“The source-opening and neighbor-erasure operation follows the framework of Byrka et al. [6, Definitions 3.2 and 5.1]. We specify the graph, taper, and batches here because their precise properties will be used in the sub-two drift analysis.” · Show in paper

Finite comparison inequality and charging/potential analysis for sub-two drift, certified by exact rational polynomial minorants and Bernstein coefficients.

Source excerpts

“The cost analysis uses an inequality on a finite probability space. Its comparison matrix need not be symmetric. The proof allows a positive contribution at one index only by charging indices with smaller values; the negative contributions at those indices pay the entire charge.” · Show in paper

“The argument uses two finite tables of rational polynomial minorants. We give the coefficient rule and the Bernstein conversion formula explicitly, so the tables can be verified using only rational arithmetic” · Show in paper

Deterministic derandomization via affine support reduction (Carathéodory compression) on polynomial-size rational distribution lists with polynomial bit-complexity control.

Source excerpts

“The next lemma is the constructive finite-dimensional Carathéodory argument for preserving an expectation. Its connection with moment matching is classical [3]; we include the exact elimination and its bit bound because both are needed by the algorithm.” · Show in paper

Rational implementation of Li-Svensson's additive-to-ordinary reduction, including zero-optimum recognition and exact rational enumeration of deletion thresholds.

Source excerpts

“We also make explicit a rational implementation of the deletion threshold in the proof of Li–Svensson’s reduction [16, Section 2, Algorithm 2]. That proof analyzes a threshold determined by the unknown optimum. Its numerical value need not be computed.” · Show in paper