論文の概要: Cut Facets and Cube Facets of Lifted Multicut Polytopes
- arxiv url: http://arxiv.org/abs/2402.16814v2
- Date: Mon, 18 Mar 2024 19:19:40 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-20 23:12:03.451780
- Title: Cut Facets and Cube Facets of Lifted Multicut Polytopes
- Title(参考訳): マルチカット多面体の切削面と立方体面
- Authors: Lucas Fabian Naumann, Jannik Irmai, Shengxian Zhao, Bjoern Andres,
- Abstract要約: 線形プログラミングに基づく厳密なアルゴリズムは、持ち上げられたマルチカットポリトープを理解する必要がある。
必要かつ十分かつ効率的に決定可能な条件を確立することで、最初の質問に答える。
カット不等式のファセット定義性を決定することはNPハードであることを示す。
- 参考スコア(独自算出の注目度): 2.531156266686649
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The lifted multicut problem has diverse applications in the field of computer vision. Exact algorithms based on linear programming require an understanding of lifted multicut polytopes. Despite recent progress, two fundamental questions about these polytopes have remained open: Which lower cube inequalities define facets, and which cut inequalities define facets? In this article, we answer the first question by establishing conditions that are necessary, sufficient and efficiently decidable. Toward the second question, we show that deciding facet-definingness of cut inequalities is NP-hard. This completes the analysis of canonical facets of lifted multicut polytopes.
- Abstract(参考訳): 昇降型マルチカット問題はコンピュータビジョンの分野で様々な応用がある。
線形プログラミングに基づく厳密なアルゴリズムは、持ち上げられたマルチカットポリトープを理解する必要がある。
最近の進歩にもかかわらず、これらのポリトープに関する基本的な2つの疑問は未解決のままである: どの低い立方体不等式がファセットを定義するのか、どの不等式がファセットを定義するのか?
本稿では, 必要な条件, 十分かつ効率的に決定可能な条件を確立することで, 最初の質問に答える。
第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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。