論文の概要: On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling
Problem
- arxiv url: http://arxiv.org/abs/2203.07280v1
- Date: Mon, 14 Mar 2022 16:54:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-15 18:46:28.783602
- Title: On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling
Problem
- Title(参考訳): 最小遅延マルチロボットパロリング問題に対する周期解について
- Authors: Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Loffler,
Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, Hao-Tsung Yang
- Abstract要約: 問題は、ロボットの最小遅延のパトロールスケジュールを計算することである。
k=1$のとき、問題は旅行セールスマン問題(TSP)と等価であり、NPハードである。
我々のアルゴリズムは実際にはユークリッド設定における一般的な問題に対するPTASである。
- 参考スコア(独自算出の注目度): 8.115135096974047
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the following surveillance problem: Given a set $P$ of $n$ sites
in a metric space and a set of $k$ robots with the same maximum speed, compute
a patrol schedule of minimum latency for the robots. Here a patrol schedule
specifies for each robot an infinite sequence of sites to visit (in the given
order) and the latency $L$ of a schedule is the maximum latency of any site,
where the latency of a site $s$ is the supremum of the lengths of the time
intervals between consecutive visits to $s$. When $k=1$ the problem is
equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. We
have two main results. We consider cyclic solutions in which the set of sites
must be partitioned into $\ell$ groups, for some~$\ell \leq k$, and each group
is assigned a subset of the robots that move along the travelling salesman tour
of the group at equal distance from each other. Our first main result is that
approximating the optimal latency of the class of cyclic solutions can be
reduced to approximating the optimal travelling salesman tour on some input,
with only a $1+\varepsilon$ factor loss in the approximation factor and an
$O\left(\left( k/\varepsilon \right)^k\right)$ factor loss in the runtime, for
any $\varepsilon >0$. Our second main result shows that an optimal cyclic
solution is a $2(1-1/k)$-approximation of the overall optimal solution. Note
that for $k=2$ this implies that an optimal cyclic solution is optimal overall.
The results have a number of consequences. For the Euclidean version of the
problem, for instance, combining our results with known results on Euclidean
TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields
a $(2(1-1/k)+\varepsilon)$-approximation of the optimal unrestricted solution.
If the conjecture mentioned above is true, then our algorithm is actually a
PTAS for the general problem in the Euclidean setting.
- Abstract(参考訳): メートル法空間内のP$$$n$サイトと、同じ最大速度のロボットのセット$k$が与えられたら、ロボットの最小遅延のパトロールスケジュールを計算する。
ここで、パトロールスケジュールは、各ロボットが(所定の順序で)訪問するサイトの無限のシーケンスを特定し、スケジュールのレイテンシ$l$は、任意のサイトの最大レイテンシであり、サイトの$s$は、連続する訪問の間の時間間隔の長さの上限である。
k=1$のとき、問題は旅行セールスマン問題(TSP)と等価であり、NPハードである。
主な結果が2つあります
サイトの集合を$\ell$グループに分けなければならない巡回解を、ある~$$\ell \leq k$に対して検討し、各群は、各グループの旅行セールスマンツアーに沿って同じ距離で移動するロボットのサブセットを割り当てる。
最初の大きな結果は、サイクリックソリューションのクラスの最適なレイテンシを近似して、ある入力で最適なトラベルセールスマンツアーを近似し、近似係数の1+\varepsilon$ factor損失と、実行時の$o\left(\left(k/\varepsilon \right)^k\right)$ factor損失を、任意の$\varepsilon >0$に対して削減できるということです。
第2の主な結果は、最適巡回解が全体の最適解の2(1-1/k)$近似であることを示している。
k=2$ に対して、これは最適巡回解が最適全体であることを意味する。
結果はいくつかの結果をもたらす。
この問題のユークリッドバージョンでは、例えば、この結果とユークリッド tsp の既知の結果とを組み合わせることで、最適な巡回解を近似するための ptas が得られ、最適な非制限解の $(2(1-1/k)+\varepsilon)$-approximation が得られる。
上記の予想が真であれば、我々のアルゴリズムは実際にはユークリッド設定における一般的な問題に対するPTASである。
関連論文リスト
- Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳(メタデータ) (2023-11-18T23:55:59Z) - The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳(メタデータ) (2023-10-13T14:52:46Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳(メタデータ) (2022-12-03T02:45:23Z) - On Robust Optimal Transport: Computational Complexity, Low-rank
Approximation, and Barycenter Computation [14.80695185915604]
我々は、最適なトランスポートの2つの頑健なバージョン、$textitRobust Semi-constrained Optimal Transport$ (RSOT) と $textitRobust Unconstrained Optimal Transport$ (ROT) を考える。
離散設定における両方の問題に対して、$widetildemathcalO(fracn2varepsilon)$timeでRSOTとROTの$varepsilon$-approximationsを生成するSinkhornベースのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-02-13T03:55:52Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-20T04:29:18Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z) - Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max
Latency [8.115135096974047]
我々は、メートル法空間内の所定の$n$のサイトを訪れるために、$k$ロボットのパトロールスケジュールを見つけることの問題を考察する。
それぞれのロボットの最大速度は同じで、その目標は、どのサイトでも最大遅延を最小化することだ。
我々は,各サイトにおける最大重量と最小重量をそれぞれ$O(k2 log fracw_max$)と$w_min$の近似係数を持つa-timeアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-05-05T23:18:53Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳(メタデータ) (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。