論文の概要: Independence-System Realisations in Single-Source Unsplittable Flow
- arxiv url: http://arxiv.org/abs/2609.17568v1
- Date: Mon, 27 Jul 2026 01:19:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-28 05:09:55.569932
- Title: Independence-System Realisations in Single-Source Unsplittable Flow
- Title（参考訳）: 単ソース非分離性流れにおける独立系の実現
- Abstract要約: そこで本稿では,主端末のゼロコスト選択による独立系の実現という経路閉概念を,有向非循環フローインスタンスに導入する。
任意の有限ループレス独立系は、その最小の禁制集合の入射サイズで測定される三角形サイズの実現を持つ。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Additive-congestion constraints in single-source unsplittable flow can enforce stable-set structure. This note isolates and generalises that mechanism. We introduce a path-closed notion of realising an independence system by the zero-cost choices of primary terminals in a directed acyclic flow instance. The definition quantifies over every directed source-terminal path and therefore remains valid under prefix borrowing, suffix splicing, and hybrid routes.Our main result extends the triangle mechanism: every finite loopless independence system has a polynomial-size realisation, measured in the incidence size of its minimal forbidden sets. Hence every finite simple graph, and more generally every hypergraph independence system without singleton forbidden hyperedges, is representable by an acyclic single-source gadget. We then specialise the construction to odd cycles. For C_{2k+1}, a uniform rational family produces a fractional cheap-selection vector that violates the odd-cycle inequality. A potential shift converts a signed connector separator into nonnegative arc costs and gives the exact cost-preserving additive-congestion threshold tau = 1 - bq. Within the symmetric family, the supremum threshold is (k+2)/(2(k+1)), which tends to 1/2. For C5, an exact certificate independently derives all source-terminal paths and enumerates all 3^10 = 59049 unsplittable routings using rational arithmetic.
- Abstract（参考訳）: 単一ソース・アンスプリタブルフローにおける加法共役制約は安定セット構造を強制することができる。
このメモはそのメカニズムを分離して一般化する。
そこで本稿では,主端末のゼロコスト選択による独立系の実現という経路閉概念を,有向非循環フローインスタンスに導入する。
この定義は、すべての方向のソース終端経路を定量化し、したがってプレフィックスの借用、接尾辞のスプライシング、ハイブリッドルートの下では有効であり、我々の主な結果は三角形のメカニズムを拡張している: すべての有限ループレス独立系は、最小の禁じられた集合の入射サイズで測定される多項式サイズの実化を持つ。
したがって、全ての有限単純グラフ、より一般的にはシングルトン禁止のハイパーエッジのないすべてのハイパーグラフ独立系は、非循環的な単一ソースガジェットによって表現可能である。
次に、建設を奇妙なサイクルに専門化します。
C_{2k+1} に対して、一様有理族は奇サイクルの不等式に反する分数的な安価な選択ベクトルを生成する。
ポテンシャルシフトは、符号付きコネクタセパレータを非負のアークコストに変換し、正確なコスト保存の加算-混雑しきい値 tau = 1 - bq を与える。
対称族の中では、上限閾値は (k+2)/(2(k+1)) であり、1/2 となる傾向がある。
C5 の場合、正確な証明は独立にすべてのソース終端経路を導出し、有理算術を用いて全ての 3^10 = 59049 の分割不能なルーティングを列挙する。
関連論文リスト
- On the SoS Certifiability of Log-Concave Distributions [51.56484100374058]
圏 $(Cm)m|v|m - mathbbE_Xsim Plangle X,vranglem$ は、すべての偶数 mge2$ に対する平方の和であり、$C>0$ は普遍定数である。
これにより、コタリとシュタインハルト(arXiv:1711.07465)の定理におけるポアンカレ定数への依存を排除し、対数凹面分布の最適モーメント境界を回復する。
論文 参考訳（メタデータ） (2026-09-24T16:48:02Z) - Exact Local Optimality Does Not Compose: The Complexity of Chronological Realization [2.1248439796866228]
正規化実現は行確率遷移行列と終端効果を用いて宣言された根語応答を再現する。
独立局所現実化、独立クエリ効果を持つ静的共有キャリア、時系列共有現実化の3つの実化複雑性を比較した。
明示的に列挙された有理メニューでは、正確な共有実現性は$existsmathbbR$-completeであり、逆多項式とゼロ欠陥を区別する約束問題は$mathsfPromiseNP$-completeである。
論文 参考訳（メタデータ） (2026-09-17T05:01:32Z) - Dimension Dependent Correlation Gap Bounds under Restricted Independence [0.0]
最悪の場合、ペアの独立な相関ギャップが$e/(e-1)$allyに達することを示す。
対の独立は、$t$-wiseの独立階層の中で、最も制限的な独立形態であるにもかかわらず、最悪の場合において、相互独立と同様に制限的である。
論文 参考訳（メタデータ） (2026-09-02T14:33:55Z) - Joint symmetry and dynamical accessibility in compact Hamiltonian encodings of set cover [0.0]
最小集合被覆のコンパクトなマルチレジスタ符号化を提案する。
我々は、その固定対称許容空間と、プロトコルによって生成される概して小さい巡回空間とを区別する。
結果は、大域的、対称性に許容され、動的にアクセス可能なスペクトル構造の厳密な分離である。
論文 参考訳（メタデータ） (2026-08-11T23:39:28Z) - Bounds for Pure Disjoint $(r,δ)$-Quantum Locally Recoverable Codes [37.00616293796624]
安定化器構造を仮定することなく, 純粋不整合$(r,)$-quantum局所回復可能符号 (qLRCs) について検討する。
回収ブロック内において, 局所的なKnill-Laflamme条件を最大1ドルまでの消去条件で定式化する。
ブロックワイドショアラフラムとユニタリウェイト列挙器を導入し、リカバリセット間でエラーウェイトがどのように分散されているかをキャプチャする。
論文 参考訳（メタデータ） (2026-08-11T13:48:28Z) - Frame-Dependent Traces and the Third-Particle Paradox [45.88028371034407]
本稿では,第3粒子のパラドックスが量子基準トラクションの観点からサブシステム記述を比較する際に生じることを示す。
我々は、我々の条件がパラドックスの内容を捉えていると主張する:状態空間全体に一貫性を与えるのではなく、その状態が保持する状態を完全に再現する。
論文 参考訳（メタデータ） (2026-07-23T18:00:01Z) - All you need is log [0.42671348654734564]
次数 $in[0,infty]$ の Rényi の発散は、データ処理および独立製品への添加物の下でのユニークな族単調であることを示す。
多くの問題は一度に2つ以上の分布を比較する - マルチポピュレーションフェアネス、マルチプライオリPAC-Bayes境界、マルチヒポテシステスト。
レニイ族の右多分布一般化は開問題である。
論文 参考訳（メタデータ） (2026-06-25T17:54:49Z) - The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems [46.657699628769336]
絡み合いと干渉は量子力学の最も基本的な性質の一つである。
我々は絡み合いが確率的検証に余分な力を与えないことを証明する。
論文 参考訳（メタデータ） (2026-05-15T17:52:33Z) - Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations [49.702772230127465]
有限状態マルコフ鎖を$n$状態と遷移行列$P$で研究する。
すべての非退化モードが実周辺不変部分空間 $mathcalK(P)$ によってキャプチャされ、商空間 $mathbbRn/mathcalK(P) 上の誘導作用素が厳密に収縮し、ユニークな商解が得られることを示す。
論文 参考訳（メタデータ） (2026-01-31T02:57:01Z) - A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube [26.777025730534756]
ハイパーキューブ上の一様分布に関して、ハーフスペースを学習するための最初のフルタイムアルゴリズムを与える。
誤り保証は$etaO(1)+epsilon$で、$eta$はノイズレートです。
より一般的に、我々のフレームワークは、個別分布に関する教師あり学習が以前考えられていたほど難しくないことを示している。
論文 参考訳（メタデータ） (2025-11-10T15:58:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。