Fugu-MT 論文翻訳(概要): On the Cyclic Assumption of the Cow-Path Search Algorithm

論文の概要: On the Cyclic Assumption of the Cow-Path Search Algorithm

arxiv url: http://arxiv.org/abs/2610.10253v1
Date: Wed, 07 Oct 2026 15:32:23 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-08 21:58:22.994455
Title: On the Cyclic Assumption of the Cow-Path Search Algorithm
Title（参考訳）: カウパス探索アルゴリズムの周期的推定について
Abstract要約: 牛道問題では、牛は原点のみに接続された$w$の経路の1つに未知の距離で横たわるゴールを見つけなければならず、性能は競争率で測定される。 Kao, Reif, Tateは、牛が一定周期で経路を訪れる効率的なランダム化アルゴリズムを設計した。彼らはアルゴリズムが$w=2$に対して最適であることを証明し、その後、Kao, Ma, Sipser, Yinはすべての$w$に対して最適であることを証明した。
参考スコア（独自算出の注目度）: 6.710420595304904
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In the cow-path problem, a cow must find a goal lying at an unknown distance on one of $w$ paths connected only at the origin, and performance is measured by competitive ratio. Kao, Reif and Tate designed an efficient randomized algorithm in which the cow visits the paths in a fixed cyclic order. They proved the algorithm is optimal for $w=2$, and subsequently Kao, Ma, Sipser and Yin proved its optimality for all $w$, with a claim that no algorithm does better than the best cyclic one. This note provides a detailed proof of that claim.
Abstract（参考訳）: 牛道問題では、牛は原点のみに接続された$w$の経路の1つに未知の距離で横たわるゴールを見つけなければならず、性能は競争率で測定される。 Kao, Reif, Tateは、牛が一定周期で経路を訪れる効率的なランダム化アルゴリズムを設計した。彼らはアルゴリズムが$w=2$に対して最適であることを証明し、その後、Kao, Ma, Sipser, Yinはすべての$w$に対して最適であることを証明した。このメモは、その主張の詳細な証拠を提供する。

関連論文リスト

Optimal and Efficient Online Inverse Optimization [72.20380065366825]
逆線形最適化では、学習者はアクションを推奨し、$mathbbRd$上で固定された未知の線形目的を最大化する専門家の選択を観察する。我々の決定論的アルゴリズムはすべての地平線に対して$O(sqrt d)$を後悔し、時間内に$d$と$T$を実行していることを示す。
論文参考訳（メタデータ） (2026-10-06T17:37:24Z)
Optimal Top-$k$ Identification from Pairwise Comparisons [0.0]
雑音のあるペアワイズ比較から, 固定信頼トップ=k$識別の能動的学習問題について検討した。この問題では、アイテムのペアを逐次選択して比較し、結果を観察し、エラー確率が最大$$$でトップ$k$アイテムのセットを返すことができる場合に停止する。
論文参考訳（メタデータ） (2026-07-09T22:55:16Z)
Online Algorithms for Repeated Optimal Stopping: Achieving Both Competitive Ratio and Regret Bounds [7.858819231575403]
古典的最適停止問題を未知分布で一般化する反復最適停止問題について検討する。我々は,各ラウンドにおける競争率を保証するアルゴリズムを設計し,全ラウンドにおけるサブ線形後悔を実現することを目的としている。我々は,不等式,秘書問題,および逆数モデル,ランダムモデルおよびi.d.入力モデルの下でのそれらの変種など,我々のフレームワークが正準問題に広く適用可能であることを実証する。
論文参考訳（メタデータ） (2025-11-06T16:04:56Z)
Pathfinding with Lazy Successor Generation [12.02023514105999]
位置のみを付与し,エッジを暗黙的に定義するパスフィンディング問題について検討する。単純な構造にもかかわらず、この問題は膨大な数の位置で非自明になる。そこで我々は,LaCAS*アルゴリズムを提案する。これは,全ての後継を一度に生成するのではなく,探索が進むにつれて徐々に後継を生成できる。
論文参考訳（メタデータ） (2024-08-27T23:25:25Z)
A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文参考訳（メタデータ） (2024-02-09T19:01:48Z)
Extending relax-and-round combinatorial optimization solvers with quantum correlations [0.0]
量子近似最適化アルゴリズム (QAOA) を$pgeq 1$ の層に埋め込む。 Sherrington-Kirk メガネを含む多くの問題に対して、$p=1$とすると、その古典的な問題と同じくらい正確であることを示す。古典的アルゴリズムに匹敵するパフォーマンスで、量子リラクゼーションとラウンドを網羅するフレームワークの道を開いた。
論文参考訳（メタデータ） (2023-07-11T22:02:01Z)
Robust affine point matching via quadratic assignment on Grassmannians [50.366876079978056]
Robust Affine Matching with Grassmannians (RoAM) は点雲のアフィン登録を行うアルゴリズムである。このアルゴリズムは、グラスマンの2つの要素間のフロベニウス距離を最小化することに基づいている。
論文参考訳（メタデータ） (2023-03-05T15:27:24Z)
Efficient Projection-Free Algorithms for Saddle Point Problems [39.88460595129901]
複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$tildeO (1/sqrtepsilon)$評価と$tildeO (1/epsilon2)$線形最適化しか必要としないことを示す。
論文参考訳（メタデータ） (2020-10-21T15:05:53Z)
Corralling Stochastic Bandit Algorithms [54.10645564702416]
相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
論文参考訳（メタデータ） (2020-06-16T15:33:12Z)
Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文参考訳（メタデータ） (2020-02-26T16:19:09Z)

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