論文の概要: Graph Partitioning with Demands: Generalized Conductance and its Applications

• arxiv url: http://arxiv.org/abs/2607.13218v1
• Date: Tue, 14 Jul 2026 19:27:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-16 16:39:12.573794
• Title: Graph Partitioning with Demands: Generalized Conductance and its Applications
• Title（参考訳）: 需要を伴うグラフ分割:一般化導電性とその応用
• Abstract要約: 一般需要モデルに基づくグラフ分割問題について検討する。 私たちの主な焦点は、削減された$(S, barS)$その量を最小限にする問題です。 我々の主な貢献は、この目的に対する$mathcalO(log n)$-approximationの保証を持つアルゴリズムである。
• 参考スコア（独自算出の注目度）: 0.8594140167290095
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we study various graph partitioning problems under a general demand model. In each such task, we are given a graph $G=(V,E,c,w)$ with a capacity function $c\colon E\to \mathbb{N}$ and a demand function $w\colon V\times V\to \mathbb{N}$. Our main focus is the problem of finding a cut $(S, \bar{S})$ minimizing the quantity \[ ψ_w( S ) = \frac{c( S, \bar{S} )}{w( S, V )\cdot w( \bar{S}, V )}. \] Here, $c( S, \bar{S} )$ is the cost of edges between $S$ and the complement of $S$, $\bar{S}$, and $w( S, V )=w( S )+w( S, \bar{S} )$ is the sum of the internal demand within $S$, $w( S )$, and the demand between vertices of $S$ and $\bar{S}$, $w( S, \bar{S} )$. We call $ψ_w( S )$ the \emph{generalized conductance} of the cut $(S, \bar{S})$, and the task of minimizing $ψ_w( S )$ the Generalized Conductance Problem. Our main contribution is an algorithm with an $\mathcal{O}(\log n)$-approximation guarantee for this objective. Our result is achieved via a two-way reduction: first to the well-known Generalized $k$-Multicut Problem, and then to a constrained variant of the classic Sparsest-Cut Problem, with an additional upper-bound constraint on the amount of demand that may be cut. Moreover, we show that the above procedure can be used to obtain an $\mathcal{O}(\log n)$-bicriteria approximation for Graph Partitioning with Demands, where the goal is to find a minimum-cost subset of edges $C$ such that for every component $H$ of $G\setminus C$, $w( H )\leq ρ\cdot w( V )$. This, in turn, yields an $\mathcal{O}(\log n)$-approximation for Hierarchical Clustering with Demands, the problem of finding a hierarchy of cuts that partitions the graph into increasingly refined clusters. For multiplicative demand functions, we improve these guarantees to $\mathcal{O}(\sqrt{\log n})$ and for trees we get an $\mathcal{O}(1)$-approximation for all of our objectives.
• Abstract（参考訳）: 本研究では,一般需要モデルに基づくグラフ分割問題について検討する。 各タスクにおいて、容量関数 $c\colon E\to \mathbb{N}$ と要求関数 $w\colon V\times V\to \mathbb{N}$ のグラフ $G=(V,E,c,w)$ が与えられる。 我々の主な焦点は、カットされた$(S, \bar{S})$ を求める問題である: 量 \[[ >_w(S ) = \frac{c(S, \bar{S} )}{w(S, V )\cdot w( \bar{S}, V )} を最小化する。 ここで、$c(S, \bar{S} )$は$S$と$S$、$\bar{S}$、$w(S, V )=w(S )+w(S, \bar{S} )$の間のエッジのコストであり、$S$、$w(S )$および$\bar{S}$、$w(S, \bar{S} )の頂点間の需要の和である。 カットされた $(S, \bar{S})$ の \emph{ Generalized Conductance} と、一般化コンダクタンス問題を最小化するタスクを $ _w(S )$ と呼ぶ。 我々の主な貢献は、この目的に対して$\mathcal{O}(\log n)$-approximationが保証されるアルゴリズムである。 まず、よく知られた$k$-Multicut問題に、次に古典的なSparsest-Cut問題の制約付き変種に、削減される可能性のある需要量に上限を加える。 さらに、上述の手順は、$\mathcal{O}(\log n)$-bicriteria approximation for Graph Partitioning with Demands, そこでゴールは、すべてのコンポーネントに対して$H$ of $G\setminus C$, $w( H )\leq ρ\cdot w(V )$となるような、エッジの最小コストサブセットを見つけることである。 これにより、階層的クラスタリングとデマンドに対する$\mathcal{O}(\log n)$-approximationが得られ、グラフをより洗練されたクラスタに分割するカットの階層を見つけるという問題が発生する。 乗法的需要関数に対しては、これらの保証を$\mathcal{O}(\sqrt{\log n})$に改善し、木に対しては、すべての目的に対して$\mathcal{O}(1)$-approximationを得る。

関連論文リスト

• On the Capacity Region of Individual Key Rates in Vector Linear Secure Aggregation [55.126702858312456]
  すべてのユーザがキーを保持する必要はないことを示し、それによって文学における最もよく知られた到達可能な領域を厳密に拡大する。 以上の結果から,各ユーザがキーを保持する必要はないという新たな事実が明らかになった。
  論文  参考訳（メタデータ） (2026-01-06T18:34:07Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
  論文  参考訳（メタデータ） (2025-06-06T20:33:57Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  制約付き部分空間近似のための一般的なフレームワークを導入する。 分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
  論文  参考訳（メタデータ） (2025-04-29T15:56:48Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  我々は、$rho$が$mtext-d$集合の近くに集中しているとき、これをノイズのあるデータを持つ多様体学習問題と解釈できることを示した。 Monge-Kantorovich $p$-cost $mathbbW_pp(rho, nu)$を介して$rho$を近似する際の$nu$のパフォーマンスを定量化し、$mathrmsupp nu$を$f : mathbbRmでカバーできるようにすることで複雑さを制限します。
  論文  参考訳（メタデータ） (2024-09-25T01:30:16Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• Partially Unitary Learning [0.0]
  ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。 この最適化問題の大域的な最大値を求める反復アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-05-16T17:13:55Z)
• The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning [6.416429054645991]
  近似の理論と応用は、最適化と強化学習の応用により、ますます関連性が高まっている。 本稿では, ステップサイズ$alpha>0$のSAを再帰で定義し, $$theta_n+1 = theta_n+ alpha f(theta_n,Phi_n+1)$$$, $theta_ninmathbbRd$と$Phi_n$をマルコフ連鎖とする。
  論文  参考訳（メタデータ） (2023-09-06T12:22:32Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
  分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs [1.0435741631709405]
  グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。 この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
  論文  参考訳（メタデータ） (2021-10-29T07:35:46Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。 任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
  論文  参考訳（メタデータ） (2021-03-17T00:59:33Z)

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

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