Fugu-MT 論文翻訳(概要): The {0,1}-knapsack problem with qualitative levels

論文の概要: The {0,1}-knapsack problem with qualitative levels

arxiv url: http://arxiv.org/abs/2002.04850v1
Date: Wed, 12 Feb 2020 09:00:29 GMT
ステータス: 処理完了
システム内更新日: 2023-01-01 20:32:21.850796
Title: The {0,1}-knapsack problem with qualitative levels
Title（参考訳）: 定性レベルを持つ {0,1}-knapsack 問題
Authors: Luca E. Sch\"afer, Tobias Dietz, Maria Barbati, Jos\'e Rui Figueira, Salvatore Greco, Stefan Ruzika
Abstract要約: 古典的なknapsack問題の変種は、各項目が整数の重みと定性的レベルと関連付けられていると考えられる。この関係が事前注文を定義することを示す。本研究では,非支配的な階数濃度ベクトルの集合全体を計算するための動的プログラミングアルゴリズムを提案する。
参考スコア（独自算出の注目度）: 2.0943517417159763
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: A variant of the classical knapsack problem is considered in which each item is associated with an integer weight and a qualitative level. We define a dominance relation over the feasible subsets of the given item set and show that this relation defines a preorder. We propose a dynamic programming algorithm to compute the entire set of non-dominated rank cardinality vectors and we state two greedy algorithms, which efficiently compute a single efficient solution.
Abstract（参考訳）: 古典的なknapsack問題の変種は、各項目が整数の重みと定性的レベルと関連付けられていると考えられる。与えられた項目集合の可能な部分集合に対する支配関係を定義し、この関係が事前順序を定義することを示す。我々は,非支配ランク濃度ベクトル全体の計算を行う動的プログラミングアルゴリズムを提案し,1つの効率的な解を効率的に計算する2つのグリーディアルゴリズムを述べる。

関連論文リスト

Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
本研究は,knapsack制約下での非モジュラーサイズに対する効率的な並列アルゴリズムを提案する。我々のアルゴリズムは, 既存の並列処理を 8+epsilon$ から 7+epsilon$ に改良し, 適応複雑性を$O(log n)$ にする。
論文参考訳（メタデータ） (2024-09-06T17:17:52Z)
Addressing The Knapsack Challenge Through Cultural Algorithm Optimization [0.0]
我々は,0-1knapsack問題の解法に特化して設計された,新しい文化アルゴリズムの変種を紹介する。提案アルゴリズムは,集団を改良するための信念空間と,交叉率と突然変異率を動的に調節する2つの重要な機能を導入している。我々は,このアルゴリズムがグローバルな最適点を一貫して見つけ出す上で,顕著な効率性を示す証拠を提供する。
論文参考訳（メタデータ） (2023-10-30T17:05:19Z)
Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文参考訳（メタデータ） (2023-06-21T17:03:22Z)
First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。これらのアルゴリズムに対する漸近的理論的保証を提供する。
論文参考訳（メタデータ） (2022-04-07T00:11:05Z)
Set-valued prediction in hierarchical classification with constrained representation complexity [4.258263831866309]
階層的多クラス分類問題に焦点をあて、有効集合が階層の内部ノードに対応する。我々は3つの手法を提案し、それらをベンチマークデータセット上で評価する。
論文参考訳（メタデータ） (2022-03-13T15:13:19Z)
Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文参考訳（メタデータ） (2022-01-05T13:37:27Z)
Combining K-means type algorithms with Hill Climbing for Joint Stratification and Sample Allocation Designs [0.0]
これは、基本層のすべての可能な成層集合から最適成層を探索するサンプル問題である。それぞれのソリューションのコストを評価するのに費用がかかります上記のアルゴリズムと最近の3つのアルゴリズムの多段階組み合わせを比較し、ソリューションコスト、評価時間、トレーニング時間を報告する。
論文参考訳（メタデータ） (2021-08-18T08:41:58Z)
Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity [13.416309759182635]
我々は、ほぼ最適の$O(log n)$適応複雑性を持つ非単調部分モジュラーアルゴリズムに対する最初の定数近似を得る。我々のアルゴリズムは$tildeO(n2)$の値クエリを要求するが、代わりに$tildeO(n)$で実行するように修正できる。これはまた、この問題に対して線形適応的な複雑性を持つ最初のアプローチであり、濃度制約や単調な目的の特別な場合であっても、最先端の手法に匹敵する。
論文参考訳（メタデータ） (2021-02-16T18:15:51Z)
Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文参考訳（メタデータ） (2020-02-26T16:19:09Z)
Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文参考訳（メタデータ） (2020-01-29T09:40:58Z)
Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。最小クラスタ回復誤差率のアルゴリズムを考案する。適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文参考訳（メタデータ） (2019-10-14T09:18:26Z)

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