論文の概要: 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))$ に減少する。
関連論文リスト
- 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) - Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed
Rewards [40.99322897009357]
トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。
我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。
我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
論文 参考訳（メタデータ） (2023-10-28T13:01:10Z) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳（メタデータ） (2023-10-23T18:26: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) - 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) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。