論文の概要: A Tie-breaking based Local Search Algorithm for Stable Matching Problems
- arxiv url: http://arxiv.org/abs/2409.10575v1
- Date: Sun, 15 Sep 2024 13:36:55 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-18 21:09:36.325415
- Title: A Tie-breaking based Local Search Algorithm for Stable Matching Problems
- Title（参考訳）: 安定マッチング問題に対するTie-breakingに基づく局所探索アルゴリズム
- Authors: Junyuan Qiu,
- Abstract要約: 不完全リストと結びつき(SMTI)の安定な結婚問題に対するタイブレーキングに基づく局所探索アルゴリズム(TBLS)と病院・居住者間の結びつき(HRT)問題(HRT)を導入する。
TBLSは最も高いマッチングサイズを達成する一方、TBLS-Eは最も低い性平等コストを示す。
どちらのアルゴリズムも、大規模インスタンスの解法において、他の局所探索アルゴリズムよりも高速な計算速度を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The stable marriage problem with incomplete lists and ties (SMTI) and the hospitals/residents problem with ties (HRT) are important in matching theory with broad practical applications. In this paper, we introduce a tie-breaking based local search algorithm (TBLS) designed to achieve a weakly stable matching of maximum size for both the SMTI and HRT problems. TBLS begins by arbitrarily resolving all ties and iteratively refines the tie-breaking strategy by adjusting the relative order within ties based on preference ranks and the current stable matching. Additionally, we introduce TBLS-E, an equity-focused variant of TBLS, specifically designed for the SMTI problem. This variant maintains the objective of maximizing matching size, while enhancing equity through two simple modifications. In comparison with ten other approximation and local search algorithms, TBLS achieves the highest matching size, while TBLS-E exhibits the lowest sex equality cost. Significantly, TBLS-E preserves a matching size comparable to that of TBLS. Both our algorithms demonstrate faster computational speed than other local search algorithms in solving large-sized instances.
- Abstract（参考訳）: 不完全リストと結びつき (SMTI) による安定した結婚問題と, 関係のある病院・居住者問題 (HRT) は, 幅広い実践的応用に適合する理論において重要である。
本稿では,SMTIとHRTの両問題に対して,最大サイズの弱安定マッチングを実現するために,タイブレーキングに基づく局所探索アルゴリズム(TBLS)を提案する。
TBLSは、すべてのネクタイを任意に解決することから始まり、好みのランクと現在の安定したマッチングに基づいて、ネクタイ内の相対順序を調整することにより、ネクタイ破り戦略を反復的に洗練する。
さらに,SMTI問題に特化して設計されたTBLS-Eについて紹介する。
この変種は、マッチングサイズを最大化する目的を維持しつつ、2つの単純な修正を通じて株式を拡大する。
他の10の近似アルゴリズムや局所探索アルゴリズムと比較して、TBLSは最も高いマッチングサイズを達成し、TBLS-Eは最も低い性平等コストを示す。
TBLS-EはTBLSに匹敵する大きさを保っている。
どちらのアルゴリズムも、大規模インスタンスの解法において、他の局所探索アルゴリズムよりも高速な計算速度を示す。
関連論文リスト
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
既存の因果探索法を効率的に並列化することにより,数千次元まで拡張可能であることを示す。
具体的には、DirectLiNGAMの因果順序付けサブプロデューサに着目し、GPUカーネルを実装して高速化する。
これにより、遺伝子介入による大規模遺伝子発現データに対する因果推論にDirectLiNGAMを適用することで、競争結果が得られる。
論文 参考訳（メタデータ） (2024-03-06T15:06:11Z) - Sample-Efficient Clustering and Conquer Procedures for Parallel
Large-Scale Ranking and Selection [0.0]
並列コンピューティング環境では、相関ベースのクラスタリングは$mathcalO(p)$サンプル複雑性低減率を達成することができる。
ニューラルアーキテクチャ検索のような大規模AIアプリケーションでは、スクリーニングなしバージョンの手順が、サンプル効率の点で完全に順序づけられたベンチマークを驚くほど上回っている。
論文 参考訳（メタデータ） (2024-02-03T15:56:03Z) - Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。
我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。
本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
論文 参考訳（メタデータ） (2024-02-02T13:31:24Z) - Learning nonparametric DAGs with incremental information via high-order
HSIC [13.061477915002767]
そこで本研究では,DAGを同定するために,親の判断したサブセットに基づく識別可能性条件を提案する。
最適相では、一階のヒルベルト最適独立基準(HSIC)に基づく最適化問題により、推定骨格が初期決定された親部分集合として与えられる。
チューニングフェーズでは、骨格は削除、追加、DAG形式化戦略によって局所的に調整される。
論文 参考訳（メタデータ） (2023-08-11T07:07:21Z) - BiSLS/SPS: Auto-tune Step Sizes for Stable Bi-level Optimization [33.082961718280245]
既存のアルゴリズムは、ハイパーグラディエントを計算する際に近似誤差の影響を受け得る2つの結合学習率を含んでいる。
線形探索(SLS)とポリアクステップサイズ(SPS)という適応的なステップサイズ法を用いて,上層と下層の両方の学習率の計算を行う。
SGDとAdamの両バージョンで利用できる新しいアルゴリズムは、最小限のチューニングで大きな学習率を見つけ、対応するバニラBOアルゴリズムよりも高速に収束させることができる。
論文 参考訳（メタデータ） (2023-05-30T00:37:50Z) - Global Optimization for Cardinality-constrained Minimum Sum-of-Squares
Clustering via Semidefinite Programming [1.3053649021965603]
最小二乗クラスタリング(MSSC)は、最近、各クラスタの濃度に関する事前知識を活用するために拡張されている。
本稿では,分枝切断法に基づく大域的最適化手法を提案する。
上界に対して、各ノードで解いたSDP緩和の解を生かした局所探索手順を提案する。
論文 参考訳（メタデータ） (2022-09-19T10:19:06Z) - Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。
代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。
データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
論文 参考訳（メタデータ） (2021-12-06T20:34:55Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set
Similarity Under Skew [58.21885402826496]
全ペアセットの類似性は、大規模で高次元のデータセットであっても広く使われているデータマイニングタスクである。
我々は,全対集合の類似性を近似するために,新しい分散アルゴリズム LSF-Join を提案する。
LSF-Joinは、小さな類似度閾値やスキュー入力セットであっても、最も近いペアを効率的に見つける。
論文 参考訳（メタデータ） (2020-03-06T00:06:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。