論文の概要: 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で必然的に実行される射影ケースに対するアルゴリズムを導出する。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Faster Algorithms for Structured Linear and Kernel Support Vector
Machines [10.815243076341526]
木幅が小さい場合や、低ランクの分解を許容する場合に、2次プログラムを解くための最初のニア線形時間アルゴリズムを設計する。
正方形のデータセット半径が大きくなると、$Omega(n2-o(1))$ timeが要求される。
論文 参考訳(メタデータ) (2023-07-15T07:19:29Z) - Low Rank Matrix Completion via Robust Alternating Minimization in Nearly
Linear Time [9.62296035593105]
我々は、より効率的でエラーの少ない最小化フレームワークに向けて、大きな一歩を踏み出します。
我々のアルゴリズムは時間$widetilde O(|Omega| k)$で実行され、解の検証にはほぼ線形である。
論文 参考訳(メタデータ) (2023-02-21T23:49:36Z) - 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) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳(メタデータ) (2021-06-09T05:39:05Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳(メタデータ) (2021-05-17T16:40:48Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。