論文の概要: Unbounded knapsack problem and double partitions

• arxiv url: http://arxiv.org/abs/2506.23499v1
• Date: Mon, 30 Jun 2025 03:44:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-01 21:27:53.910238
• Title: Unbounded knapsack problem and double partitions
• Title（参考訳）: 非有界クナップサック問題と二重分割
• Authors: Boris Y. Rubinstein,
• Abstract要約: クナプサック問題(knapsack problem)は、整数係数を持つ2つの線型ディオファント方程式の系に対する多くの非負の整数解を求める。 19世紀半ば、シルヴェスターとケイリーは、スカラー分割の和に二重分割を還元できる変数除去に基づくアプローチを提案した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The unbounded knapsack problem can be considered as a particular case of the double partition problem that asks for a number of nonnegative integer solutions to a system of two linear Diophantine equations with integer coefficients. In the middle of 19th century Sylvester and Cayley suggested an approach based on the variable elimination allowing a reduction of a double partition to a sum of scalar partitions. This manuscript discusses a geometric interpretation of this method and its application to the knapsack problem.
• Abstract（参考訳）: 非有界なクナプサック問題は、整数係数を持つ2つの線型ディオファントス方程式の系に対して、多くの非負の整数解を求める二重分割問題の特別な場合とみなすことができる。 19世紀半ば、シルヴェスターとケイリーは、スカラー分割の和に二重分割を還元できる変数除去に基づくアプローチを提案した。 本書では, この手法の幾何学的解釈とknapsack問題への応用について論じる。

関連論文リスト

• Non-variational Quantum Combinatorial Optimisation [3.6538093004443155]
  本稿では,多種多様な最適化問題を解くために,非変分量子アルゴリズムを提案する。 アルゴリズムの汎用性は、様々な問題に適用することで実証される。 各問題インスタンスに対して、アルゴリズムは少数の反復で大域的に最適な解を求める。
  論文  参考訳（メタデータ） (2024-04-04T02:36:24Z)
• Reverse em-problem based on Bregman divergence and its application to classical and quantum information theory [53.64687146666141]
  近年,反復を必要とせずにチャネル容量を計算できる解析手法が提案されている。 トヨタが提案した逆のEm-problemに注意を向けます。 逆の Em-problem の非定型式を導出する。
  論文  参考訳（メタデータ） (2024-03-14T10:20:28Z)
• Approximate Integer Solution Counts over Linear Arithmetic Constraints [2.28438857884398]
  本稿では,ポリトープ内の格子数に近似する新しいフレームワークを提案する。 我々のアルゴリズムは、数十次元のポリトープを解くことができ、最先端のカウンタを著しく上回る。
  論文  参考訳（メタデータ） (2023-12-14T09:53:54Z)
• Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces [5.534626267734822]
  本稿では,低次元空間における2つの点間のGromov-Wasserstein問題を計算するための枠組みを提案する。 これは、AIと機械学習における一般的な問題である2つの構成または形状の類似性を定量化するために使用できる。
  論文  参考訳（メタデータ） (2023-07-18T08:20:56Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  我々は、点的不等式が非負の kSoS 関数のクラス内で等式となることを示す。 また, 等式制約に焦点をあてることで, 散乱不等式を用いることで, 制約のサンプリングにおける次元性の呪いを軽減することができることを示す。
  論文  参考訳（メタデータ） (2023-01-16T10:30:04Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• Partitioned Least Squares [3.372747046563984]
  新たな定式化は凸ではなく,この問題に対処するための2つの代替手法を提供する。 完全性のために、分割数が大きすぎる場合に正確な方法の代わりに使用できる代替分岐および有界アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-06-29T17:10:32Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。