論文の概要: Box Facets and Cut Facets of Lifted Multicut Polytopes
- arxiv url: http://arxiv.org/abs/2402.16814v3
- Date: Fri, 12 Apr 2024 11:38:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-15 17:23:29.238685
- Title: Box Facets and Cut Facets of Lifted Multicut Polytopes
- Title（参考訳）: マルチカット多面体の箱面と切削面
- Authors: Lucas Fabian Naumann, Jannik Irmai, Shengxian Zhao, Bjoern Andres,
- Abstract要約: 昇降型マルチカット問題の線形プログラム定式化について検討する。
2進線形プログラムのカット不等式がファセットを定義するかどうかを決定することはNPハードであることを示す。
- 参考スコア（独自算出の注目度）: 2.531156266686649
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The lifted multicut problem is a combinatorial optimization problem whose feasible solutions relate one-to-one to the decompositions of a graph $G = (V, E)$. Given an augmentation $\widehat{G} = (V, E \cup F)$ of $G$ and given costs $c \in \mathbb{R}^{E \cup F}$, the objective is to minimize the sum of those $c_{uw}$ with $uw \in E \cup F$ for which $u$ and $w$ are in distinct components. For $F = \emptyset$, the problem specializes to the multicut problem, and for $E = \tbinom{V}{2}$ to the clique partitioning problem. We study a binary linear program formulation of the lifted multicut problem. More specifically, we contribute to the analysis of the associated lifted multicut polytopes: Firstly, we establish a necessary, sufficient and efficiently decidable condition for a lower box inequality to define a facet. Secondly, we show that deciding whether a cut inequality of the binary linear program defines a facet is NP-hard.
- Abstract（参考訳）: 持ち上げマルチカット問題は、グラフ $G = (V, E)$ の分解に 1 対 1 の可能な解を関連付ける組合せ最適化問題である。
augmentation $\widehat{G} = (V, E \cup F)$ of $G$ と与えられたコスト $c \in \mathbb{R}^{E \cup F}$ を与えられた場合、その$c_{uw}$ の和を $uw \in E \cup F$ で最小化することが目的である。
F = \emptyset$ の場合、問題はマルチカット問題に特化し、$E = \tbinom{V}{2}$ の場合はクリッド分割問題に特化する。
昇降型マルチカット問題の線形プログラム定式化について検討する。
より具体的には、我々は、関連する持ち上げマルチカットポリトープの分析に寄与する: まず、ファセットを定義するために、下位ボックスの不等式に必要な十分かつ効率的に決定可能な条件を確立する。
第二に、二項線形プログラムのカット不等式がファセットを定義するかどうかを決定することはNPハードであることを示す。
関連論文リスト
- 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]
近似の性能をMonge-Kantorovich $p$-costで定量化する。
次に、ソボレフ予算の制約の下で、機能的$mathscrJ_p(f)$を最小化するものとして問題を再構築する。
論文 参考訳（メタデータ） (2024-09-25T01:30:16Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - 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) - On Partially Unitary Learning [0.0]
ヒルベルト空間の最適写像 $IN$ of $left|psirightrangle$ と $OUT$ of $left|phirightrangle$ が提示される。
この最適化問題の大域的な最大化を求めるアルゴリズムを開発し,多くの問題に適用した。
論文 参考訳（メタデータ） (2024-05-16T17:13:55Z) - A polynomial quantum computing algorithm for solving the dualization
problem [75.38606213726906]
2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。
本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-08-28T18:12:54Z) - Mutually unbiased bases: polynomial optimization and symmetry [1.024113475677323]
mathbb Cd$ の正則基底の集合 $k$ は互いに非バイアスな $|langle e,frangle |2 = 1/d$ と呼ばれ、$e$ と $f$ は異なる基底の基底ベクトルである。
この対称性を(解析的に)利用して、半定値プログラムのサイズを縮小し、取り外し可能とする。
論文 参考訳（メタデータ） (2021-11-10T14:14:53Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Private Learning of Halfspaces: Simplifying the Construction and
Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。
学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文 参考訳（メタデータ） (2020-04-16T16:12:10Z) - Latent Factor Analysis of Gaussian Distributions under Graphical
Constraints [5.575141499952048]
CMTFA のランクは 1 ドル、ランクは n-1 ドルのいずれかであり、その間には何の問題もない。
特に、CMTFA のランクは 1 ドル、ランクは n-1 ドルのいずれかであり、その間には何も持たないことが示されている。
論文 参考訳（メタデータ） (2020-01-08T19:36:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。