論文の概要: Minimum projective linearizations of trees in linear time
- arxiv url: http://arxiv.org/abs/2102.03277v2
- Date: Wed, 17 Feb 2021 14:20:33 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-05 00:31:18.267042
- Title: Minimum projective linearizations of trees in linear time
- Title（参考訳）: 線形時間における木の最小射影線型化
- Authors: Llu\'is Alemany-Puig, Juan Luis Esteban, Ramon Ferrer-i-Cancho
- Abstract要約: 我々は$O(n)$-timeで間違いなく実行される射影ケースのアルゴリズムを導出する。
また、射影に制約のあるルート木の線形配置についても検討する。
- 参考スコア（独自算出の注目度）: 1.611401281366893
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The minimum linear arrangement problem (MLA) consists of finding a mapping
$\pi$ from vertices of a graph to integers that minimizes $\sum_{uv\in
E}|\pi(u) - \pi(v)|$. For trees, various algorithms are available to solve the
problem in polynomial time; the best known runs in subquadratic time in
$n=|V|$. There exist variants of the MLA in which the arrangements are
constrained to certain classes of projectivity. Iordanskii, and later Hochberg
and Stallmann (HS), put forward $O(n)$-time algorithms that solve the problem
when arrangements are constrained to be planar. We also consider linear
arrangements of rooted trees that are constrained to be projective. Gildea and
Temperley (GT) sketched an algorithm for the projectivity constraint which, as
they claimed, runs in $O(n)$ but did not provide any justification of its cost.
In contrast, Park and Levy claimed that GT's algorithm runs in $O(n \log
d_{max})$ where $d_{max}$ is the maximum degree but did not provide sufficient
detail. Here we correct an error in HS's algorithm for the planar case, show
its relationship with the projective case, and derive an algorithm for the
projective case that runs undoubtlessly in $O(n)$-time.
- Abstract（参考訳）: 最小線形配置問題(MLA)は、グラフの頂点から整数への写像 $\pi$ を求め、$\sum_{uv\in E}|\pi(u) - \pi(v)|$ を最小化する。
木の場合、多項式時間で問題を解くための様々なアルゴリズムが利用可能であり、最もよく知られた実行時間は$n=|V|$である。
MLA の変種には、アレンジメントがある種の射影性のクラスに制約されるものがある。
Iordanskii と後に Hochberg と Stallmann (HS) が提案した$O(n)$-time アルゴリズムは、アレンジが平面であるように制約されたときに問題を解決する。
また、射影に制約のあるルート木の線形配置についても検討する。
Gildea と Temperley (GT) は、プロジェクティビティ制約のアルゴリズムをスケッチした。
対照的に、パークとレヴィは、gt のアルゴリズムは $o(n \log d_{max})$ で実行され、ここで $d_{max}$ は最大次数であるが十分な詳細は示されていないと主張した。
ここでは、平面ケースに対するHSのアルゴリズムの誤差を補正し、射影ケースとの関係を示し、$O(n)$-timeで必然的に実行される射影ケースに対するアルゴリズムを導出する。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering [18.29151197560866]
我々は[Makarychev, Makarychev and Vijayaraghavan, STOC'12] の半ランダムグラフモデルを考える。
時間アルゴリズムは、カットされた$(A, B)$がサイズ$Omega(alpha)$である限り、alphad Cutの問題を最大$O(alpha)$ [MMV'12]に近似することが知られている。
この問題の微細な複雑さについて検討し,[MMV'12]と同じような性能を示す最初のニア線形時間サブルーチンを提示する。
論文 参考訳（メタデータ） (2024-06-07T11:40:54Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - 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) - Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。
重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-02T05:26:10Z) - A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs [1.0435741631709405]
グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。
この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
論文 参考訳（メタデータ） (2021-10-29T07:35:46Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Quantum complexity of minimum cut [0.2538209532048867]
隣接行列モデルにおける最小カット問題の量子クエリと時間複雑性を特徴付ける。
我々のアルゴリズムは、Apers and de Wolf (FOCS 2020) によるグラフスカラー化のための量子アルゴリズムを用いており、Kawarabayashi and Thorup (STOC 2015) と Rubinstein, Schramm and Weinberg (ITCS 2018) による準最小カットの構造に関する結果である。
論文 参考訳（メタデータ） (2020-11-19T13:51:49Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。