論文の概要: 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ハードであることを示す。
関連論文リスト
- Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。
得られた解法は数値的に安定かつ高速であることを示す。
論文 参考訳(メタデータ) (2024-04-25T12:09:16Z) - Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳(メタデータ) (2023-11-18T23:55:59Z) - 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) - Memory-Constrained Algorithms for Convex Optimization via Recursive
Cutting-Planes [23.94542304111204]
勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。
規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
論文 参考訳(メタデータ) (2023-06-16T17:00:51Z) - 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) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳(メタデータ) (2021-01-29T18:57:52Z) - 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) - A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with
Constraints [8.849815837266977]
制約付きマルコフ決定プロセス(CMDP)は、シーケンシャルな意思決定問題を定式化する。
本稿では, 有限水平CMDPの線形計画法を利用して, 繰り返し楽観的な計画を立てるオンラインアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-09-23T19:30:46Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳(メタデータ) (2020-04-16T19:16:38Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。