Fugu-MT 論文翻訳(概要): Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection

論文の概要: Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection

arxiv url: http://arxiv.org/abs/2109.04809v1
Date: Fri, 10 Sep 2021 11:53:34 GMT
ステータス: 処理完了
システム内更新日: 2021-09-13 13:18:19.304713
Title: Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection
Title（参考訳）: スケジューリング,割り当て,公平選択のための局所最適数集合分割法
Authors: Kaan Gokcesu, Hakan Gokcesu
Abstract要約: 提案アルゴリズムは, ほぼ線形時間で局所最適解を求めることができることを示す。我々のアルゴリズムは入力集合に正の要素も整数の要素も必要としないので、より広く適用できる。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the optimization version of the set partition problem (where the difference between the partition sums are minimized), which has numerous applications in decision theory literature. While the set partitioning problem is NP-hard and requires exponential complexity to solve (i.e., intractable); we formulate a weaker version of this NP-hard problem, where the goal is to find a locally optimal solution. We show that our proposed algorithms can find a locally optimal solution in near linear time. Our algorithms require neither positive nor integer elements in the input set, hence, they are more widely applicable.
Abstract（参考訳）: 分割和の差が最小となる)集合分割問題の最適化版について検討し、決定論の文献に多くの応用がある。集合分割問題はNPハードであり、解くのに指数関数的複雑性(すなわち、難解)を必要とするが、このNPハード問題のより弱いバージョンを定式化し、そこでは局所最適解を求める。提案アルゴリズムは, ほぼ線形時間で局所最適解を求めることができることを示す。我々のアルゴリズムは入力集合に正の要素も整数の要素も必要とせず、より広く適用できる。

関連論文リスト

Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文参考訳（メタデータ） (2023-07-17T20:11:56Z)
A 2-opt Algorithm for Locally Optimal Set Partition Optimization [0.0]
我々は,最大$O(N2)$時間と$O(N)$空間で局所最適解を生成するアルゴリズムを開発した。アルゴリズムは任意の入力精度を処理でき、正や整数の入力を必要としない。
論文参考訳（メタデータ） (2023-03-14T20:25:56Z)
A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization [0.0]
マルチウェイ数分割最適化の問題について検討する。我々は、そのような局所最適解を生成できる線形時間複雑性$O(Nlog N)$アルゴリズムを提案する。
論文参考訳（メタデータ） (2022-03-10T20:07:21Z)
Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文参考訳（メタデータ） (2022-01-28T05:53:28Z)
A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization [0.0]
等濃度集合分割問題の最適化版(等値分割の和の絶対差を最小化する)について検討する。我々のアプローチでは正あるいは整数の入力は必要とせず、任意の入力精度で同じように機能する。
論文参考訳（メタデータ） (2021-09-16T11:25:18Z)
Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文参考訳（メタデータ） (2021-06-08T15:54:44Z)
Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文参考訳（メタデータ） (2021-04-19T17:22:11Z)
A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear Programs [0.4925222726301578]
本稿では、整数線形プログラムの解を見つけることができる任意の量子アルゴリズムをブランチ・アンド・プライス・アルゴリズムに統合する手法を提案する。量子アルゴリズムの役割は、ブランチ・アンド・プライスに現れるサブプロブレムに対する整数解を見つけることである。
論文参考訳（メタデータ） (2021-03-29T08:59:26Z)
Partitioned Least Squares [3.372747046563984]
新たな定式化は凸ではなく,この問題に対処するための2つの代替手法を提供する。完全性のために、分割数が大きすぎる場合に正確な方法の代わりに使用できる代替分岐および有界アルゴリズムを提供する。
論文参考訳（メタデータ） (2020-06-29T17:10:32Z)
Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文参考訳（メタデータ） (2020-05-10T19:52:03Z)
Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文参考訳（メタデータ） (2020-01-29T09:40:58Z)

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