論文の概要: Fast and Efficient Matching Algorithm with Deadline Instances
- arxiv url: http://arxiv.org/abs/2305.08353v2
- Date: Mon, 12 Feb 2024 21:17:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 20:09:09.011099
- Title: Fast and Efficient Matching Algorithm with Deadline Instances
- Title（参考訳）: デッドラインインスタンスを用いた高速かつ効率的なマッチングアルゴリズム
- Authors: Zhao Song, Weixin Wang, Chenbo Yin, Junze Yin
- Abstract要約: まず、$mathrmdeadline$の市場モデルを紹介します。
最適化された2つのアルゴリズム(textscFastGreedy と textscFastPostponedGreedy)を提示する。
同時に、我々のアルゴリズムは元の2つのアルゴリズムよりも高速に動作します。
- 参考スコア（独自算出の注目度）: 7.613259578185218
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The online weighted matching problem is a fundamental problem in machine
learning due to its numerous applications. Despite many efforts in this area,
existing algorithms are either too slow or don't take $\mathrm{deadline}$ (the
longest time a node can be matched) into account. In this paper, we introduce a
market model with $\mathrm{deadline}$ first. Next, we present our two optimized
algorithms (\textsc{FastGreedy} and \textsc{FastPostponedGreedy}) and offer
theoretical proof of the time complexity and correctness of our algorithms. In
\textsc{FastGreedy} algorithm, we have already known if a node is a buyer or a
seller. But in \textsc{FastPostponedGreedy} algorithm, the status of each node
is unknown at first. Then, we generalize a sketching matrix to run the original
and our algorithms on both real data sets and synthetic data sets. Let
$\epsilon \in (0,0.1)$ denote the relative error of the real weight of each
edge. The competitive ratio of original \textsc{Greedy} and
\textsc{PostponedGreedy} is $\frac{1}{2}$ and $\frac{1}{4}$ respectively. Based
on these two original algorithms, we proposed \textsc{FastGreedy} and
\textsc{FastPostponedGreedy} algorithms and the competitive ratio of them is
$\frac{1 - \epsilon}{2}$ and $\frac{1 - \epsilon}{4}$ respectively. At the same
time, our algorithms run faster than the original two algorithms. Given $n$
nodes in $\mathbb{R} ^ d$, we decrease the time complexity from $O(nd)$ to
$\widetilde{O}(\epsilon^{-2} \cdot (n + d))$.
- Abstract（参考訳）: オンライン重み付けマッチング問題は、多くの応用のために機械学習の基本的な問題である。
この領域での多くの努力にもかかわらず、既存のアルゴリズムは遅すぎるか、$\mathrm{deadline}$(ノードがマッチできる最長時間)を考慮に入れない。
本稿では,まず$\mathrm{deadline}$という市場モデルを紹介する。
次に、2つの最適化アルゴリズム(\textsc{fastgreedy} と \textsc{fastpostponedgreedy})を提示し、アルゴリズムの時間複雑性と正確性に関する理論的証明を提供する。
textsc{FastGreedy}アルゴリズムでは、ノードが買い手なのか売り手なのかをすでに知っています。
しかし、 \textsc{FastPostponedGreedy} アルゴリズムでは、各ノードの状態は最初不明である。
次に、スケッチマトリクスを一般化し、実際のデータセットと合成データセットの両方でオリジナルのアルゴリズムとアルゴリズムを実行する。
$\epsilon \in (0,0.1)$ は各辺の実重みの相対誤差を表す。
元の \textsc{Greedy} と \textsc{PostponedGreedy} の競合比は、それぞれ $\frac{1}{2}$ と $\frac{1}{4}$ である。
これら2つのアルゴリズムに基づいて, \textsc{fastgreedy} と \textsc{fastpostponedgreedy} のアルゴリズムを提案し,その競合比はそれぞれ $\frac{1 - \epsilon}{2}$ と $\frac{1 - \epsilon}{4}$ である。
同時に、我々のアルゴリズムは元の2つのアルゴリズムよりも高速に動作します。
n$ ノードが $\mathbb{r} ^ d$ で与えられると、時間の複雑さは $o(nd)$ から $\widetilde{o}(\epsilon^{-2} \cdot (n + d))$ に減少する。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。
このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。
一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文 参考訳（メタデータ） (2024-11-23T23:13:24Z) - 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) - 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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - A Faster $k$-means++ Algorithm [11.428775569173638]
ほぼ最適な実行時間で$k$-means++問題を解決するアルゴリズムを提案する。
我々は、$widetildeO(nd + nk2)$時間しかかからない新しいアルゴリズムtextscFastKmeans++を提案する。
論文 参考訳（メタデータ） (2022-11-28T08:17:12Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Well Separated Pair Decomposition and power weighted shortest path
metric algorithm fusion [0.0]
私たちは、あるポイントセットで$s$-wellの分離ペアを$mathbbrn$, $n$$$>$$1で計算するアルゴリズムを考えています。
また、ダイクストラのアルゴリズムの置換であるアルゴリズムについても検討し、特定のパワー重み付き最短経路メトリックを用いてk$-nearestの隣人を計算し、$mathbbrn$,$n$$$$$$$$$$で計算する。
論文 参考訳（メタデータ） (2021-03-20T17:38:13Z) - Fast Classical and Quantum Algorithms for Online $k$-server Problem on
Trees [0.19573380763700712]
木上の$k$サーバ問題に対するオンラインアルゴリズムを検討する。
Chrobak と Larmore は最適な競合比を持つこの問題に対して$k$-competitive アルゴリズムを提案した。
本稿では,前処理に要するO(nlog n)$時間複雑性を持つ新しい時間効率アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-08-01T14:21:45Z) - Improved quantum algorithm for A-optimal projection [4.248054546466641]
本稿では、Duan emphet al.のアルゴリズムの時間的複雑さを$(frackappa4ssqrtks epsilonsmathrmpolylog)$に補正する。
我々のアルゴリズムは、Duan emphet al.のアルゴリズムと比較して少なくとも1つのスピードアップを達成する。
論文 参考訳（メタデータ） (2020-06-10T09:31:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。