論文の概要: Approximation Algorithms for ROUND-UFP and ROUND-SAP
- arxiv url: http://arxiv.org/abs/2202.03492v1
- Date: Mon, 7 Feb 2022 20:15:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-10 07:21:01.685362
- Title: Approximation Algorithms for ROUND-UFP and ROUND-SAP
- Title（参考訳）: ラウンドufpとラウンドsapの近似アルゴリズム
- Authors: Debajyoti Kar, Arindam Khan, Andreas Wiese
- Abstract要約: 古典的パッキング問題の2つの一般化であるROUND-UFPとROUND-SAPについて検討する。
ROUND-UFPでは、すべての矩形を与えられた経路の最小のコピー(ラウンド)にまとめることが目的である。
ROUND-SAP では、これらのタスクは長方形と見なされ、その目標はこれらの長方形を最小数のラウンドに重ね合わせることにある。
- 参考スコア（独自算出の注目度）: 0.06875312133832077
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study ROUND-UFP and ROUND-SAP, two generalizations of the classical BIN
PACKING problem that correspond to the unsplittable flow problem on a path
(UFP) and the storage allocation problem (SAP), respectively. We are given a
path with capacities on its edges and a set of tasks where for each task we are
given a demand and a subpath. In ROUND-UFP, the goal is to find a packing of
all tasks into a minimum number of copies (rounds) of the given path such that
for each copy, the total demand of tasks on any edge does not exceed the
capacity of the respective edge. In ROUND-SAP, the tasks are considered to be
rectangles and the goal is to find a non-overlapping packing of these
rectangles into a minimum number of rounds such that all rectangles lie
completely below the capacity profile of the edges.
We show that in contrast to BIN PACKING, both the problems do not admit an
asymptotic polynomial-time approximation scheme (APTAS), even when all edge
capacities are equal. However, for this setting, we obtain asymptotic
$(2+\varepsilon)$-approximations for both problems. For the general case, we
obtain an $O(\log\log n)$-approximation algorithm and an
$O(\log\log\frac{1}{\delta})$-approximation under $(1+\delta)$-resource
augmentation for both problems. For the intermediate setting of the no
bottleneck assumption (i.e., the maximum task demand is at most the minimum
edge capacity), we obtain absolute $12$- and asymptotic
$(16+\varepsilon)$-approximation algorithms for ROUND-UFP and ROUND-SAP,
respectively.
- Abstract（参考訳）: ROUND-UFP と ROUND-SAP は,経路 (UFP) 上の不安定な流れ問題に対応する古典的 BIN パッキング問題の2つの一般化である。
エッジに能力を持ったパスと,各タスクに対して要求とサブパスが与えられる一連のタスクが与えられます。
ROUND-UFPでは、すべてのタスクを与えられたパスの最小数のコピー(ラウンド)にまとめることが目標であり、それぞれのコピーに対して、エッジ上のタスクの総需要がそれぞれのエッジの容量を超えない。
ROUND-SAP では、これらのタスクは長方形と見なされ、その目標は、すべての矩形がエッジの容量プロファイルを完全に下回るように、これらの長方形を最小数のラウンドに重ね合わせることにある。
ビンパッキングとは対照的に,すべてのエッジ容量が等しい場合でも,両問題は漸近多項式時間近似スキーム(aptas)を認めないことを示した。
しかし、この設定では、両方の問題に対する漸近的な$(2+\varepsilon)$-approximationsを得る。
一般的な場合、どちらの問題に対しても$O(\log\log n)$-approximationアルゴリズムと$O(\log\log\frac{1}{\delta})$-approximationを$(1+\delta)$-resource augmentationで得られる。
ボトルネックのない仮定の中間設定(つまり、最大タスク要求は最低限のエッジ容量)では、それぞれROUND-UFP と ROUND-SAP の絶対 12$- と漸近 $ 16+\varepsilon の近似アルゴリズムを得る。
関連論文リスト
- Differentially Private Bilevel Optimization [4.07926531936425]
両レベル最適化のための差分プライベート(DPright)アルゴリズムを提案する。
これらは、任意の所望の経験的設定を提供することができる、このタスクのための最初のアルゴリズムである。
我々の分析は、制約のある問題や未調査の問題もカバーしている。
論文 参考訳（メタデータ） (2024-09-29T21:52:38Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Minimum Width for Deep, Narrow MLP: A Diffeomorphism Approach [3.218087085276242]
本稿では,奥行きの狭義の最小幅の探索を単純化し,$w(d_x, d_y)$と表される純粋幾何学関数を決定するフレームワークを提案する。
最小幅の上限は$namemax (2d_x+1, d_y) + alpha(sigma)$で、$0 leq alpha(sigma) leq 2$はアクティベーション関数に依存する定数を表す。
論文 参考訳（メタデータ） (2023-08-30T08:58:23Z) - Optimal Approximation of Zonoids and Uniform Approximation by Shallow
Neural Networks [2.7195102129095003]
以下の2つの問題について検討する。
1つ目は、$mathbbRd+1$の任意のソノイドがハウスドルフ距離で$n$の線分で近似できる誤差を決定することである。
2つ目は、変動空間上の浅いReLU$k$ニューラルネットワークの均一ノルムにおける最適近似率を決定することである。
論文 参考訳（メタデータ） (2023-07-28T03:43:17Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - On Subspace Approximation and Subset Selection in Fewer Passes by MCMC
Sampling [3.1822873305165618]
サンプリングベースのサブセット選択技術は、データに複数のパスを持つ適応的なサンプリングイテレーションを必要とする。
従来のサブセット選択アルゴリズムで必要となるパス数を削減するMCMCアルゴリズムを提案する。
このアルゴリズムは$mathrmpoly(k/epsilon)$のサブセットを選び、最適部分空間に$(1+epsilon)$近似を与えます。
論文 参考訳（メタデータ） (2021-03-20T06:07:30Z) - Fully Gap-Dependent Bounds for Multinomial Logit Bandit [5.132017939561661]
マルチノミアルロジット (MNL) バンディット問題について検討し、各ステップごとに、販売者は、N$アイテムのプールから最大でK$のサイズを提供する。
i) $widetildeO(sum_i = 1N Delta_i-2)$ time steps with high probability, (ii) $O(sum_i notin S* KDelta_i)というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-11-19T17:52:12Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。