論文の概要: 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-近似アルゴリズムを導入する。 上界に向けて、我々は、前順序ポリトープのファセットを定義する奇妙な閉ウォーク不等式のクラスによる線形プログラム緩和を厳格化する。 我々はアルゴリズムの実装に貢献し、これらを共同でクラスタリングし、公開ソーシャルネットワークのアカウントを部分的に注文するタスクに適用し、そのアウトプットと効率を質的かつ定量的に比較する。

関連論文リスト

• 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)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• 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)
• 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)
• 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)

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

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