論文の概要: How Unbalanced Must a Latin Rectangle Be?
- arxiv url: http://arxiv.org/abs/2611.06003v1
- Date: Wed, 04 Nov 2026 05:52:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-06 03:25:57.992775
- Title: How Unbalanced Must a Latin Rectangle Be?
- Title（参考訳）: ラテン長方形はどのように不均衡でなければならないか?
- Abstract要約: 我々は3つの面から最小の不均衡について研究する。
コンピュータ支援分岐とバウンドは、3倍の9$長方形の最小不均衡が56$であることを証明する。
さらに私たちは,リーンとMathlibのバウンドが低いことも証明しています。
- 参考スコア（独自算出の注目度）: 8.606929066348565
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We view a $k\times n$ Latin rectangle as $n$ points in the grid $[n]^k$. Each symbol gives one point, whose coordinates are the columns it occupies. The rectangle is balanced when these points are pairwise equidistant in the $\ell_1$ metric. Its imbalance measures the distance from this ideal. We study the minimum imbalance from three sides. Constructively, we use a simulated annealing that moves symbols within rows and only penalises column clashes. Against the reference table of Voboril et al. (2025), it improves 33 of the 51 non-square values for $8\le n\le 13$, by up to 39.4%, and matches the rest. A cheap invariant, the row group, certifies that none of the 33 new rectangles is isotopic to rows of a group table, so the earlier column-swapping local search cannot reach any of them. Exactly, a computer-assisted branch and bound proves that the minimum imbalance of a $3\times 9$ rectangle is $56$. Díaz et al. found this value, but its optimality was open. A sharper pruning bound, derived from the identity $I=2\sum(d-t)^+$, reduces the search tree by a factor of $2.4$ to $3.3$ on the instances with $k\ge3$ that we solve. Asymptotically, the minimum imbalance is $Θ(n^3)$ for every fixed $k$. A pigeonhole argument gives a lower constant of order $k\,4^{-k}$, and random rectangles give an upper constant of order $\sqrt k$. For $k=2$, the limit of $\min I/n^3$ exists, a permuton attains it, and it lies between $4/375$ and $0.1196$. Perfect balance is an $\ell_1$-equilateral problem, so it forces $k=Ω(n/\log n)$ rows. For $2\times n$ rectangles, single two-minute annealing runs improve five of the seven six-hour MIP upper bounds for $14\le n\le 20$. Finally, the Lean 4 kernel checks every rectangle reported in this paper against a 74-line specification that imports only Lean's core library. We also prove the pigeonhole lower bound in Lean with Mathlib.
- Abstract（参考訳）: 我々は、$k\times n$ Latin rectangle を、グリッド $[n]^k$ 内の$n$ポイントとみなす。
各記号は1つの点を与え、その座標はそれが占有する列である。
この長方形は、これらの点が$\ell_1$の計量において対同値であるときに均衡する。
その不均衡はこの理想からの距離を測る。
我々は3つの面から最小の不均衡について研究する。
構造的には、シミュレートされたアニーリングを使用して、シンボルを行内で移動させ、ペナリだけが衝突する。
Voboril et al (2025) の参照表に対して、51の非平方値のうち 33 を 8\le n\le 13$ で、39.4% まで改善し、残りの値と一致する。
安い不変量である行群は、33の新しい矩形のうちのどれも群テーブルの行に等方的でないことを証明しているので、初期のカラムスワッピング局所探索はそのどれにも到達できない。
正確には、コンピュータ支援分岐とバウンドは、$3\times 9$ 長方形の最小不均衡が$56であることを示す。
Díazらはこの値を発見したが、最適性は開かれた。
I=2\sum(d-t)^+$から導かれるよりシャープなプルーニングバウンドは、解決した$k\ge3$のインスタンス上で、検索ツリーを2.4$から3.3$に還元する。
漸近的に、最小の不均衡は、すべての固定された$k$に対して$(n^3)$である。
ハトホールの引数は位数$k\,4^{-k}$の低い定数を与え、ランダムな矩形は位数$\sqrt k$の上限を与える。
k=2$の場合、$\min I/n^3$の極限が存在し、パームトンが到達し、$4/375$から$0.1196$の間にある。
完全均衡は$\ell_1$-equilateral問題であり、$k=Ω(n/\log n)$ rowを強制する。
2\times n$ 長方形の場合、シングル2分間のアニーリングは7つの6時間のMIP上限のうち5つを14\le n\le 20$で改善する。
最後に、Lean 4カーネルは、この論文で報告されているすべての矩形を、Leanのコアライブラリのみをインポートする74行の仕様に対してチェックする。
さらに私たちは,リーンとMathlibのバウンドが低いことも証明しています。
関連論文リスト
- The Four-Qubit Hyperbolic Quadric Has Contextuality Degree 315 [7.178150846704679]
すべての最適割り当てのコンテキストが双対極空間$DW(5,2)$を形成することを示す。
等式は局所的であり、割り当ては1つのグリッドの1つの決定に違反する場合に最適である。
論文 参考訳（メタデータ） (2026-10-19T14:16:01Z) - Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization [55.29259818039367]
支持領域がより均一な選択を許すにつれて、認証された近似係数がどのように改善されるかを示す。
明示的なパラメータの選択は、非遅延認証プロファイルに$underline_k()$を与える。
値保持丸めは、これらの保証をマトロイドとクナプサックの制約に転送する。
論文 参考訳（メタデータ） (2026-10-02T20:52:38Z) - Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。
学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。
定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
論文 参考訳（メタデータ） (2026-09-30T18:26:29Z) - Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws [4.211691393530721]
最小ノルム学習者を持つ有限重み付き最小二乗に対して、$lceil3d/2rceilleq nleq2d-1$ の厳密な法則を証明します。
この保証は、観測されたすべての特徴ランクをカバーし、全特徴範囲を保存する選択を使用する。
論文 参考訳（メタデータ） (2026-09-08T20:44:50Z) - On the Capacity Region of Individual Key Rates in Vector Linear Secure Aggregation [55.126702858312456]
すべてのユーザがキーを保持する必要はないことを示し、それによって文学における最もよく知られた到達可能な領域を厳密に拡大する。
以上の結果から,各ユーザがキーを保持する必要はないという新たな事実が明らかになった。
論文 参考訳（メタデータ） (2026-01-06T18:34:07Z) - Quantum Latin squares with all possible cardinalities [11.305754681609002]
量子ラテン平方次数$n$(QLS$(n)$)は$ntimes n$配列である。
2つの単位ベクトル $|urangle, |vranglein MathcalH_n$ が、実数$theta$ が存在する場合、同一視される。
QLS$(n)$ の濃度 $c$ は配列内の異なるベクトルの数である。
論文 参考訳（メタデータ） (2025-07-08T03:40:19Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - A note on estimating the dimension from a random geometric graph [2.3020018305241337]
グラフの隣接行列にアクセスする際に、基礎空間の次元$d$を推定する問題について検討する。
また、密度の条件がなければ、$d$の一貫した推定子は$n r_nd to infty$と$r_n = o(1)$が存在することを示す。
論文 参考訳（メタデータ） (2023-11-21T23:46:44Z) - Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。
最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。
これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
論文 参考訳（メタデータ） (2020-04-16T22:57:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。