論文の概要: Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network

• arxiv url: http://arxiv.org/abs/2502.14536v2
• Date: Thu, 28 Aug 2025 08:34:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-29 13:55:30.843925
• Title: Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network
• Title（参考訳）: プレオーダー問題に対するアルゴリズムとそのソーシャル・ネットワークのアカウントのクラスタリング・順序付け作業への応用
• Authors: Jannik Irmai, Maximilian Moeller, Bjoern Andres,
• Abstract要約: NP-ハード最大値事前順序問題(NP-hard maximum value preordering problem)は、クリッド分割問題(クラスタリング問題)と部分順序問題との結合緩和とハイブリッドである。 本稿では,部分グラフの最大ディカットを構築し,局所探索を定義する線形時間 4-近似アルゴリズムを提案する。 我々はこれらのアルゴリズムを共同でクラスタリングし、公開ソーシャルネットワークのアカウントを部分的に注文するタスクに適用し、そのアウトプットと効率を質的かつ定量的に比較する。
• 参考スコア（独自算出の注目度）: 8.436874393402158
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The NP-hard maximum value preordering problem is both a joint relaxation and a hybrid of the clique partition problem (a clustering problem) and the partial ordering problem. Toward approximate solutions and lower bounds, we introduce a linear-time 4-approximation algorithm that constructs a maximum dicut of a subgraph and define local search heuristics. Toward upper bounds, we tighten a linear program relaxation by the class of odd closed walk inequalities that define facets, as we show, of the preorder polytope. We contribute implementations of the algorithms, apply these to the task of jointly clustering and partially ordering the accounts of published social networks, and compare the output and efficiency qualitatively and quantitatively.
• Abstract（参考訳）: NPハード最大値事前順序問題(NP-hard maximum value preordering problem)は、結合緩和と、クリッド分割問題(クラスタリング問題)と部分順序問題とのハイブリッドである。 近似解と下界に向けて,部分グラフの最大ディカットを構築し,局所探索ヒューリスティックスを定義する線形時間 4-近似アルゴリズムを導入する。 上界に向けて、我々は、前順序ポリトープのファセットを定義する奇妙な閉ウォーク不等式のクラスによる線形プログラム緩和を厳格化する。 我々はアルゴリズムの実装に貢献し、これらを共同でクラスタリングし、公開ソーシャルネットワークのアカウントを部分的に注文するタスクに適用し、そのアウトプットと効率を質的かつ定量的に比較する。

関連論文リスト

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering [0.0]
  本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。 提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
  論文  参考訳（メタデータ） (2024-03-17T21:43:19Z)
• Constrained Hierarchical Clustering via Graph Coarsening and Optimal Cuts [1.5591858554014466]
  単語を階層的にクラスタリングする問題について検討する。 特に,水平および垂直構造制約によるクラスタリングの問題に着目する。 提案手法は,既存のアルゴリズムと非常によく比較され,計算学的に軽量であることを示す。
  論文  参考訳（メタデータ） (2023-12-07T10:52:06Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods [23.948126336842634]
  合成非滑らかな最適化問題の解法として, 1次FOMのより低い複雑性境界を確立するための最初の試みを行う。 本手法と提案したIGG法は,ほぼ改善可能であることがわかった。
  論文  参考訳（メタデータ） (2023-07-14T19:59:18Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。 我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
  論文  参考訳（メタデータ） (2023-07-04T16:55:41Z)
• Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
  本稿では,候補アルゴリズムの集合に有効な手法を提案する。 内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。 提案手法は,他のアルゴリズムのスコアを大幅に改善する。
  論文  参考訳（メタデータ） (2023-05-26T21:49:37Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Near-Optimal Correlation Clustering with Privacy [37.94795032297396]
  相関クラスタリングは教師なし学習における中心的な問題である。 本稿では,相関クラスタリング問題と証明可能なプライバシ保証のための,シンプルで効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-02T22:30:19Z)
• Faster Deterministic Approximation Algorithms for Correlation Clustering and Cluster Deletion [5.584060970507507]
  相関クラスタリングは、ペアの類似性と相似性スコアに基づいてデータセットをパーティショニングするフレームワークである。 本稿では, 相関クラスタリング問題とエッジラベリング問題との新たな関係性を示す。 我々は,決定論的定数係数近似の保証を有する相関クラスタリングのための新しい近似アルゴリズムを開発し,標準線形プログラミング緩和を回避する。
  論文  参考訳（メタデータ） (2021-11-20T22:47:19Z)
• Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programming [5.126924253766052]
  提案手法は,高い確率で鋭いインスタンスを解くための線形収束率を示す。 また、制約のない双線型問題に対する効率的な座標ベースのオラクルを提案する。
  論文  参考訳（メタデータ） (2021-11-10T04:56:38Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  逆例は機械学習モデルにおいて広く研究されている現象である。 そこで本研究では,$k$-nearest 近傍分類の逆ロバスト性を評価するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-19T08:49:10Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems [117.44028458220427]
  ゼロオーダーのオラクルを用いてサドルポイント問題を解くアルゴリズムをいくつか提案する。 解析により、この項の収束率は、一階法よりも$log n$因子の方が悪いことが示されている。 また、混合構成を考慮し、その部分に対してゼロ階のオラクルを使用する1/2階法を開発する。
  論文  参考訳（メタデータ） (2020-09-21T14:26:48Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• The {0,1}-knapsack problem with qualitative levels [2.0943517417159763]
  古典的なknapsack問題の変種は、各項目が整数の重みと定性的レベルと関連付けられていると考えられる。 この関係が事前注文を定義することを示す。 本研究では,非支配的な階数濃度ベクトルの集合全体を計算するための動的プログラミングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-12T09:00:29Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。