論文の概要: Adaptive Sparsification for Linear Programming
- arxiv url: http://arxiv.org/abs/2510.08348v1
- Date: Thu, 09 Oct 2025 15:36:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-10 17:54:15.166219
- Title: Adaptive Sparsification for Linear Programming
- Title（参考訳）: リニアプログラミングのための適応スパシフィケーション
- Authors: Étienne Objois, Adrian Vladu,
- Abstract要約: 線形プログラムを多くの制約で解くための一般的なフレームワークを適応的なスペーシングにより$(n gg d)$で導入する。
制約行列に対して$tildeO(sqrtn d3)$ row-queries を用いて、LPの正確な解を求めるクラークソンのアルゴリズムの量子バージョンを示す。
第二に、我々のフレームワークは、パッキング制約が単純であるときに、混成パッキングと問題をカバーするための新しい最先端のアルゴリズムを生み出します。
- 参考スコア（独自算出の注目度）: 3.735586259382096
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce a generic framework for solving linear programs (LPs) with many constraints $(n \gg d)$ via adaptive sparsification. Our approach provides a principled generalization of the techniques of [Assadi '23] from matching problems to general LPs and robustifies [Clarkson's '95] celebrated algorithm for the exact setting. The framework reduces LP solving to a sequence of calls to a ``low-violation oracle'' on small, adaptively sampled subproblems, which we analyze through the lens of the multiplicative weight update method. Our main results demonstrate the versatility of this paradigm. First, we present a quantum version of Clarkson's algorithm that finds an exact solution to an LP using $\tilde{O}(\sqrt{n} d^3)$ row-queries to the constraint matrix. This is achieved by accelerating the classical bottleneck (the search for violated constraints) with a generalization of Grover search, decoupling the quantum component from the classical solver. Second, our framework yields new state-of-the-art algorithms for mixed packing and covering problems when the packing constraints are ``simple''. By retaining all packing constraints while sampling only from the covering constraints, we achieve a significant width reduction, leading to faster solvers in both the classical and quantum query models. Our work provides a modular and powerful approach for accelerating LP solvers.
- Abstract（参考訳）: 本稿では,線形プログラム (LP) を適応スパシフィケーションにより,多くの制約を$(n \gg d)$で解くための汎用フレームワークを提案する。
提案手法は,[Assadi '23] の手法をマッチング問題から一般LPに一般化し,[Clarkson's '95] の有望なアルゴリズムを正確な設定のために強化する。
このフレームワークは,LP解法を小型で適応的なサブプロブレム上での'low-violation oracle''への一連の呼び出しに還元し,乗算重み更新法のレンズを通して解析する。
私たちの主な結果は、このパラダイムの汎用性を示しています。
まず、制約行列に対して$\tilde{O}(\sqrt{n} d^3)$ row-queries を用いてLPの正確な解を求めるクラークソンのアルゴリズムの量子バージョンを示す。
これは、古典的ボトルネック(違反した制約の探索)をグローバー探索の一般化で加速させ、古典的解法から量子成分を分離することで達成される。
第二に、我々のフレームワークは、パッキング制約が `simple'' である場合に、混合パッキングと問題をカバーするために、新しい最先端のアルゴリズムを生成する。
カバー制約のみをサンプリングしながら、すべてのパッキング制約を保持することにより、大きな幅削減を実現し、古典的および量子的クエリモデルの両方において、より高速な解法を実現する。
我々の研究は、LPソルバを高速化するためのモジュール的で強力なアプローチを提供する。
関連論文リスト
- A competitive NISQ and qubit-efficient solver for the LABS problem [0.0]
パウリ相関。
(PCE)は、近年、変分量子アルゴリズムにおける問題を最適化するための量子ビット効率のアプローチとして導入されている。
我々はPCEベースのフレームワークを拡張し、LABS(Low Autocorrelation Binary Sequences)問題を解決する。
論文 参考訳（メタデータ） (2025-06-20T18:00:02Z) - Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。
既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。
これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-21T17:15:48Z) - A Quantum Constraint Generation Framework for Binary Linear Programs [0.0]
量子コンピュータを用いたバイナリ線形プログラミング(BLP)のための新しい手法を提案する。
量子最適化アルゴリズム(ハイブリッドまたは量子専用)は現在、ICPのためのスタンドアロンの解法である。
本研究では,任意の量子最適化アルゴリズムを量子情報古典制約生成フレームワークにラップする。
論文 参考訳（メタデータ） (2025-03-27T07:24:33Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression [65.8785736964253]
本稿では,線形制約付きコンテキスト帯域(CBwLC)について考察する。これは,アルゴリズムが全消費の線形制約を受ける複数のリソースを消費するコンテキスト帯域の変種である。
この問題はknapsacks (CBwK) を用いてコンテキスト的帯域幅を一般化し、制約のパッケージ化とカバー、および正および負のリソース消費を可能にする。
本稿では,回帰オラクルに基づくCBwLC(CBwK)のアルゴリズムについて述べる。このアルゴリズムは単純で,計算効率が良く,統計的に最適である。
論文 参考訳（メタデータ） (2022-11-14T16:08:44Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。
学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。
また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
論文 参考訳（メタデータ） (2021-05-14T11:31:14Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。