Matching works

11 works

math.PR — Probability

Lower bounds for the Beardwood–Halton–Hammersley constant

Contributed by Tejasvi Singh Tomar

Let β\beta be the Beardwood–Halton–Hammersley constant: the shortest tour through nn independent uniform random points in the unit square has length asymptotic to βn\beta\sqrt n almost surely. Dong and Cao proved β≥0.6421\beta\ge0.6421 from an inequality β≥5/8+∑k=3KCk\beta\ge5/8+\sum_{k=3}^{K}C_k, where CkC_k is an integral over configurations of kk points in the plane that form a connected graph when points at distance at most 11 are joined. For C3C_3, C4C_4 and C5C_5, sharper bounds come from a first-order expansion of the area of the union of the unit disks on boxes of configurations. For C6+⋯+C22C_6+\dots+C_{22}, which Dong and Cao did not use, a lower bound comes from comparing each point only with the three points before it in the order of their first coordinates. We obtain β≥0.6496\beta\ge0.6496, and β≥0.6508\beta\ge0.6508 if the exponential function of the C library used to evaluate the bound for C6+⋯+C22C_6+\dots+C_{22} has a relative error below 10−910^{-9}. The proofs are computer-assisted; the bound 0.64960.6496 is proved in Lean 4, with finite checks evaluated by compiled code, from the inequality of Dong and Cao and two statements about unions of disks that we prove but do not formalize.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716094

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202621 pages
PDFView work

math.CO — Combinatorics

The Steiner ratio is at least 0.8564

Contributed by Tejasvi Singh Tomar

The Steiner ratio is the infimum, over finite sets of points in the Euclidean plane, of the length of a Steiner minimal tree divided by the length of a minimum spanning tree. Gilbert and Pollak conjectured in 1968 that it equals 3/2≈0.8660\sqrt3/2\approx0.8660, and the conjecture is open. We prove that it is at least 2141/2500=0.85642141/2500=0.8564, improving the bound 0.85590.8559 of Ke, Huang, Shu, He, Gai and Wang. Their method reduces the induction step of Du and Hwang's 1983 proof of the bound 0.80.8 to finitely many inequalities on boxes in a space of local configurations of a Steiner minimal tree, which are checked by computer. These inequalities use estimates for the positions of terminals outside the local configuration. We prove all the geometric lemmas that our certificate uses, filling gaps in two proofs of Ke et al., and we add two such estimates that hold for more parameter values than the published ones. Within this method some new estimate is necessary: with the published estimates, no certificate of this kind reaches 0.8560.856, whatever the boxes. The computer-assisted part is also verified in Lean 4, by a proof whose checks all run in Lean's kernel; the rest of the argument enters the formal proof as hypotheses.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716009

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202619 pages
PDFView work

cs.DS — Data Structures and Algorithms

A certified exponent of 0.48758 for worst-case Subset Sum, and limits of the alias–checksum analysis

Contributed by Jennifer Voitle

For more than fifty years, since Horowitz and Sahni's meet-in-the-middle algorithm of 1974, the best exponent for worst-case Subset Sum was 1/21/2. In October 2026 that barrier fell twice within a week, with OpenAI's 20.49n2^{0.49n} algorithm and, independently, Li and Ye's 2(1/2−1/450000)n≈20.4999978n2^{(1/2 - 1/450000)n} \approx 2^{0.4999978n}, and improvements have followed quickly since: within three weeks A. Kapila's modification of the OpenAI approach ("Base") reached 0.4877, a retuning of Base by JoshuaQFEX reached 0.487676, and a refinement by Y. Bills reached 0.4876723. Here we push this line of work further and examine what limits it. Conditional on the cited non-numerical proofs, we give a certified parameter point with threshold T=0.4875754036T=0.4875754036: for every fixed T′>TT'>T, the uniform randomized algorithm uses O(2T′n)O(2^{T'n}) word operations on inputs of polynomial bit length, with success probability at least 2/32/3. In particular, it runs in time O(20.4875755n)O(2^{0.4875755n}). A single asymmetric filter replaces Base's family of 43 filters. Independent interval computations certify all required numerical conditions, including both filtering moments and their quadrature errors. We prove a lower bound on the first filtering moment, valid for all positive continuous densities, that excludes every parameter choice with τ≤0.484\tau\le0.484 in the original OpenAI proof's sufficient budget. Three algebraic bounds explain the costs at our improved point. Separately, an enumeration phase that inserts at least 2(1−η−o(1))n2^{(1-\eta-o(1))n} alias classes, spending a counted step on each, and uses checksum gap at most Δ\Delta needs exponent at least (1−Δ)/2(1-\Delta)/2. This is a conditional operation-count bound; a global upper bound on achievable checksum capacity remains open. Finally, we isolate a small-layer statement that would yield threshold 0.48734075280.4873407528, prove combinatorial special cases, and identify the remaining questions.

Author comments: 30 pages, 2 figures. The main result is conditional on the written proofs of OpenAI (4 Oct 2026) and A. Kapila (commit 44c34961); its numerical conditions are certified in interval arithmetic. The companion file SECTION_T_v3.pdf (full proofs of the ternary alias step, Appendix A) is included with the source. Code, certificates, verification scripts and a timestamped research record: https://github.com/jv1000/subset-sum. AI use is described in Section 11.

A mix of human-written and AI-generated textHuman understanding: some partsAI-assisted mathematicsFourier filteringSubset Sumcomputer-assisted proofexact algorithmsinterval arithmeticmeet-in-the-middlerepresentation techniqueworst-case complexity
Nov 07, 202630 pages
PDFView work

math.CO — Combinatorics

Finite Field Grothendieck Inequality, Finite Field Johnson-Lindenstrauss Flattening and Finite Field Bourgain-Tzafriri Restricted Invertibility Problems

Contributed by K. MAHESH KRISHNA

We ask for finite field versions of following three: (1) Grothendieck Inequality, (2) Johnson-Lindenstrauss Flattening Lemma, (3) Bourgain-Tzafriri Restricted Invertibility Theorem.

Primarily human-written textHuman understanding: all partsBourgain-Tzafriri Restricted InvertibilityFinite Field.Grothendieck InequalityJohnson-Lindenstrauss Lemma
Nov 05, 20265 pages
PDFView work

cs.DS — Data Structures and Algorithms

The Exact One-Half Threshold for Arbitrary-Capacity Bottleneck Multiple Subset Sum

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

In bottleneck multiple subset sum, items with weights are packed into knapsacks with capacities, possibly leaving items unpacked, so as to maximize the minimum load. For identical capacities the best possible approximation ratio is 2/32/3, and Chen et al.\ asked whether 2/32/3 is also achievable for arbitrary capacities. We show that it is not: for arbitrary capacities we give a 1/21/2-approximation using O(nlog⁡(n+1)+mlog⁡(m+1))O(n\log(n+1)+m\log(m+1)) arithmetic and comparison operations for nn items and mm knapsacks, and prove that no fixed ratio above 1/21/2 is achievable unless P=NP\mathsf P=\mathsf{NP}. We also give a short proof of the classical 1/21/2 guarantee of Friesen and Langston for unit profits.

Primarily AI-generated textHuman understanding: some partsapproximation thresholdbipartite matchingbottleneck multiple subset sumknapsacknumerical matching
Nov 04, 20269 pages
PDFView work

cs.CC — Computational Complexity

The Siriaisa Algorithm for Minimum Independent Dominating Set

Contributed by Frank Vega

The Minimum Independent Dominating Set problem asks for a smallest maximal independent set of a graph. Unless P=NP\mathrm{P}=\mathrm{NP} it is not approximable within n1−εn^{1-\varepsilon} for any ε>0\varepsilon>0; it is NP-complete on cubic planar bipartite graphs and NP-hard to approximate within δB\delta B on bipartite graphs of maximum degree BB. We present version 0.0.9 of \textsc{Siriaisa}, an ensemble of eighteen strategies that adapts the vertex cover algorithm \textsc{Salvador} and the independent set algorithm \textsc{Esperanza} to independent domination: its exact subproblems are forests, solved by a conditioned tree dynamic program, in place of the bipartite structures of \textsc{Salvador}; one base strategy splits every vertex of degree larger than ⌊n⌋\lfloor\sqrt n\rfloor into unconnected copies; and the improvers include a weighted swap search. We prove that the output is an independent dominating set computed in O(n+m)O(n+m) expected time, with ratio at most Δ\Delta, optimal on forests, and with ratio at most n\sqrt n on three classes of graphs. The degree-splitting strategy computes a dominating set of size at most ⌊n⌋ (i(G)+s(G))\lfloor\sqrt n\rfloor\,(i(G)+s(G)) on every graph, for an explicit splitting excess s(G)s(G), and the output satisfies the same bound when the decoded set is independent. The excess is at most n(n+1)n(\sqrt n+1), largest on complete graphs, zero for n≥D2n\ge D^2 on every family of bounded degree DD, among them the NP-hard and UG-hard bounded-degree families, and O(n)O(\sqrt n) on planar graphs; on complete multipartite, crown, wheel and double-star graphs the output is optimal. We conjecture the ratio O(n)O(\sqrt n) on all graphs; a proof would imply P=NP\mathrm{P}=\mathrm{NP}. In a reduction from satisfiability, every independent dominating set of the graph of a formula with NN variables and tt copies of every clause, tt at least the largest clause width WW, is a satisfying assignment, with NN vertices, or has at least t+Nt+N vertices; with t=Wt=W, every independent dominating set of ratio smaller than 1+W/N1+W/N is a satisfying assignment. This proves the n1−εn^{1-\varepsilon} inapproximability directly from satisfiability, without a gap from the PCP theorem. Through a reduction of Chleb{\'\i}k and Chleb{\'\i}kov{\'a}, with an explicit edge gadget that turns a graph HH into a graph h(H)h(H) with i(h(H))=τ(H)+2∣E(H)∣i(h(H))=\tau(H)+2|E(H)|, where τ(H)\tau(H) is the minimum vertex cover size, every output on h(H)h(H) decodes into a vertex cover of HH; we state the conditional consequences under the Unique Games Conjecture, for which a proof has been reported but not yet peer reviewed, on general graphs and, through the result of Austrin, Khot and Safra, on bounded-degree graphs. In reproducible experiments the output is optimal on 9 9999\,999 of 10 00010\,000 graphs with an exact integer-program optimum, on all 9595 of 112112 bipartite graphs whose optimum was proved, on all 1818 instances of the set cover reduction, and on 22 of the 3030 instances of the vertex cover reduction with a proved optimum; on ten Khot--Regev YES instances the decoded vertex cover has ratio between 1.251.25 and 1.86651.8665. We also report the results on the 6868 complements of the DIMACS clique benchmark.

Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBoolean satisfiabilityForest Dynamic ProgrammingMinimum Independent Dominating SetMinimum Maximal Independent SetP versus NPUnique Games Conjecturebipartite graphslocal search
Nov 03, 202630 pages
PDFView work

cs.CC — Computational Complexity

The Esperanza Algorithm for Maximum Independent Set

Contributed by Frank Vega

The maximum independent set problem asks for the largest set of pairwise non-adjacent vertices in an undirected graph. It is NP-hard to approximate within n1−εn^{1-\varepsilon} for every ε>0\varepsilon>0, and under the Unique Games Conjecture it is hard to approximate within O(Δ/log⁡2Δ)O(\Delta/\log^2\Delta) on graphs of maximum degree Δ\Delta; the Khot--Regev form of the conjecture, for which a proof has been reported but not yet peer reviewed, also rules out a (2−ε)(2-\varepsilon)-approximation of Minimum Vertex Cover. We present version 0.1.6 of \textsc{Esperanza}, which takes the better of a dynamic minimum-degree (Caro--Wei) greedy set and the complement of the \textsc{Salvador} vertex cover, and improves it by three budgeted local searches: repair-and-grow restarts at the cover vertices and at a maximum-degree vertex, chained local restarts realising (k,k+1)(k,k+1)-improvements, and an iterated (1,2)(1,2)-swap search. We prove that it runs in O((n+m) αA(n))O((n+m)\,\alpha_{\mathrm A}(n)) expected time for fixed budgets, with αA\alpha_{\mathrm A} the inverse Ackermann function. We prove that the output is a maximal independent set, that its complementary vertex cover has at most 2τ−r2\tau-r vertices, where τ\tau is the minimum cover size and rr the number of components with an edge, and that the ratio is at most (Δ+2)/3(\Delta+2)/3 on graphs of maximum degree Δ\Delta. We prove the ratio 2n2\sqrt n on every graph with Δ≤n\Delta\le\sqrt n and on three further classes, and state it for all graphs as a conjecture, whose proof would imply P=NP\mathrm{P}=\mathrm{NP}. We also state the conjecture that the complementary cover has at most 2τ−∣M∣2\tau-|M| vertices for the NetworkX minimum maximal matching MM; a proof would give a 3/23/2-approximation for Minimum Vertex Cover and refute the Unique Games Conjecture unless P=NP\mathrm{P}=\mathrm{NP}. In reproducible experiments the returned set is optimal on all 30 00030\,000 graphs of a suite certified by an exact integer program; on 4040 Khot--Regev YES instances with 640640 to 2 5602\,560 vertices the conjectured bound is certified on 3838 and open on 22; and on 3131 bounded-degree graphs the certified ratio is at most 1.07691.0769 on the families with a planted independent set.

Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBounded-degree GraphsLinear TimeMaximum Independent SetP versus NPUnique Games ConjectureVertex Coverlocal search
Nov 02, 202613 pages
PDFView work

math.NT — Number Theory

Local freedom and capacity barriers in quadratic trace reconstruction

Contributed by Brice Pouly

A completely multiplicative sign function is determined by its values on n2+1n^2+1, n2+2n^2+2, and n2−2n^2-2, but exact determination does not quantify how many readings detect a negative prime sign. We distinguish three losses of information: partial compatibility tests, geometric restrictions on certificates, and fractional relaxation of signed constraints. After fixing a prime head, we describe the exact fibre of a window and the parity constraints joining two windows. For any fixed head and any sequence HN=No(1)H_N=N^{o(1)}, one table with o(N)o(N) negative entries passes every HNH_N-window test and every two-reading test. A separate finite table passes these tests without any global source. We bound certificate capacity - fractional packing under unit reading loads - for narrow and binary certificates and for low-degree transport libraries whose links cancel odd prime valuations in pairs. A fixed algebraic curve of certificates for a target prime pp has at most logarithmic capacity, or capacity at most one when a reading is constant; in the infinite unanchored case its common poles have field Q(p)\mathbb{Q}(\sqrt p). Conversely, selected values of n2+1n^2+1 can force linearly many errors while the capacity of all certificates stays bounded. Two internally disjoint pair families compose without loss on their existing readings, whereas sixteen actual values exhibit Pack⁡=3<Cap⁡=4<μ=5\operatorname{Pack}=3<\operatorname{Cap}=4<\mu=5. The selected-sample constructions do not give an upper bound for the minimum on a complete prefix.

Primarily AI-generated textHuman understanding: no partsarithmetic certificatescertificate capacityforced errorsfractional packinglocal compatibilitymultiplicative reconstructionquadratic traces
Oct 20, 202641 pages
PDFView work

math.OC — Optimization and Control

Additive Rounding for LP-Tight Three-Item Bin Packing

Contributed by Ruixue Yuan, Da Teng, Zhenyu Sun

We consider bin-packing instances with 3m3m items of sizes in (1/4,1/2)(1/4,1/2), total size mm, and configuration linear programming value mm. Let dd be the relative dimension of the polytope of zero-sum multiplicity patterns obtained by centering sizes at 1/31/3. We determine the maximum additive integrality gap for every d≤10d\le10. It is zero for d≤4d\le4 and one for 5≤d≤105\le d\le10. More generally, a representation of the multiplicity vector by at most five zero-sum patterns admits an integral packing, and a representation by at most eleven patterns requires at most one additional bin. The integral-packing result has a structural proof; the additive-one result combines structural restrictions with exact finite enumeration. For arbitrary dd, we construct an LP-tight subinstance with at most 6d+36d+3 items and no smaller additive gap. An integer representation preserving the signs of triple sums then yields a finite rational family attaining the worst gap, which is computable in time 2O((d+1)2)2^{O((d+1)^2)}. Finally, we construct a sharp family with simplex pattern polytopes and a linearly growing zero-sum matching deficit. Its eleven-dimensional member violates the zero-sum remainder condition used in the ten-dimensional proof. Thus the bound of eleven fractional patterns in that condition is sharp.

Primarily human-written textHuman understanding: all partsbin packingconfiguration linear programminghypergraph matchinglattice polytopeszero-sum patterns
Oct 20, 202618 pages
PDFView work

cs.CC — Computational Complexity

An Approximate Solution to the Minimum Vertex Cover Problem: The Salvador Algorithm

Contributed by Frank Vega

Minimum Vertex Cover has a classical linear-time ratio of 22, and under the Unique Games Conjecture no polynomial-time algorithm achieves a fixed ratio below 22 unless P=NP\mathrm{P}=\mathrm{NP}. We present version 0.1.4 of \textsc{Salvador}, a linear-time ensemble of seventeen strategies, numbered in the order in which they are computed: twelve base strategies (component amplification before a maximal matching, the maximal matching itself, degree and weight heuristics, reductions to auxiliary problems that are solved exactly, a decomposition into bipartite layers, a weighted subdivision reduction and a bounded-treewidth dynamic program), followed by five improvers (a union pass, local search, reduce-and-search, consensus forcing and a swap-maximize refinement). We prove that every strategy runs in O((n+m) α(n))O((n+m)\,\alpha(n)) time, and that the returned cover has at most 2τ−r2\tau-r vertices, where rr is the number of components with an edge, so the ratio is at most 1.9999999991.999999999 whenever τ≤109r\tau\le10^{9}r. We prove exactness or a bounded ratio on several classes of graphs, among them every bipartite graph on which the Hopcroft--Karp phases of the layer strategy reach a maximum matching, and we give a per-instance certificate: a cover with at most 2L−∣M∣2L-|M| vertices, for a lower bound L≤τL\le\tau and the maximal matching MM, is within ratio 3/23/2 on that instance. In a reproducible suite the returned cover satisfies ∣C∣≤2τ−∣M∣|C|\le2\tau-|M| on all 291291 tested graphs with a known optimum and is certified on the six without one, although single strategies violate it; on the 6868 DIMACS clique complements it is never worse than Hvala and optimal on 3737 instances against 1818. Whether ∣C∣≤2τ−∣M∣|C|\le2\tau-|M| holds on every graph is stated as a conjecture: a proof would give a linear-time 3/23/2-approximation and would refute the Unique Games Conjecture unless P=NP\mathrm{P}=\mathrm{NP}.

Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBipartite LayersEnsemble HeuristicsLinear TimeMaximal MatchingP versus NPSplit GraphUnique Games ConjectureVertex Cover
Oct 18, 202631 pages
PDFView work

cs.DS — Data Structures and Algorithms

A Lean Certificate for the Single Source Unsplittable Flow Cost Counterexample

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We explain a standalone Lean 4 and Mathlib verification of the finite counterexample announced by Dmitry Rybin to the cost-preserving single-source unsplittable-flow conjecture. The instance has seven vertices, nine directed arcs, and three terminal demands. An exact rational path flow saturates every arc, has cost 58, and has largest demand 15. Exhaustive graph-path classification reduces every unsplittable routing to two choices per terminal. Three backbone-arc inequalities force any routing with load at most the fractional load plus 15 to use at least two paid routes, each costing 30. Thus every such routing costs at least 60, ruling out cost preservation even with a non-strict congestion bound. We present the numerical certificate, its graph realization, and the boundary between the pinned proved implementation and its statement-only verification interface. The contribution is an exposition of a source-based formal certificate; no new counterexample, first formalization, or general rounding algorithm is claimed.

Primarily AI-generated textHuman understanding: some partsGoemans cost conjectureLean 4MathlibRybin counterexamplefinite counterexampleformal verificationsingle-source unsplittable flow
Oct 01, 20266 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations