論文の概要: The canonical facets of multi-separator polytopes

• arxiv url: http://arxiv.org/abs/2608.16861v1
• Date: Mon, 17 Aug 2026 17:44:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-18 19:59:03.827782
• Title: The canonical facets of multi-separator polytopes
• Title（参考訳）: マルチセパレータポリトープの正準面
• Abstract要約: 画像セグメンテーションの課題に適用するために, 昇降型マルチカット問題の代替として, グラフマルチセグレータ問題について検討する。 奇数サイクルの不等式によって引き起こされる面は一般的には移動せず, 持ち上げられたマルチカットポリトープに対して, いずれの面も他方の面の突起であることを示す。
• 参考スコア（独自算出の注目度）: 9.797564482274634
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We initiate a polyhedral study of the graph multi-separator problem proposed by Irmai et al. (2024) as an alternative to the lifted multicut problem for application to the task of image segmentation. Starting with an integer linear program (ILP) formulation and the multi-separator polytope spanned by its feasible solutions, we characterize in terms of efficiently-decidable, graph-theoretic conditions all facets induced by inequalities of the ILP. We proceed by strengthening these inequalities and describing additional facets of some multi-separator polytopes induced by the stronger inequalities. Specifically, we obtain a totally dual integral description of the multi-separator polytope for paths in the case where separation is considered for all vertex pairs. Finally, we relate the multi-separator polytope to the boolean quadric polytope, showing that facets induced by odd-cycle inequalities do not transfer generally, and to the lifted multicut polytope, showing that either polytope is a projection of a face of the other.
• Abstract（参考訳）: 本稿では,Irmai et al (2024) が提案するグラフマルチセパレータ問題の多面的研究を,画像セグメンテーションのタスクに適用するためのリフトマルチカット問題の代替として開始する。 整数線形プログラム(ILP)の定式化と,その実現可能な解によって分散されたマルチセパレータポリトープから始めて,ILPの不等式によって引き起こされる全ての面を,効率よく決定可能なグラフ理論条件で特徴づける。 我々は、これらの不等式を強化し、より強い不等式によって引き起こされる多重セパレータポリトープの追加面を記述する。 具体的には、全ての頂点対に対して分離を考慮した場合、経路に対する多重分離ポリトープの完全双対積分記述を得る。 最後に, 多面体ポリトープとブール二次ポリトープを関連づけ, 奇数サイクルの不等式によって引き起こされる面が一般的に移動しないことを示すとともに, 持ち上げられた多面体ポリトープに対して, いずれの面も他方の面の突起であることを示す。

関連論文リスト

• The Complexity of Min-Max Optimization for Quadratic Polynomials [71.85811744604827]
  我々は、超キューブ上での min-max 最適化の近似定常点の計算が二次数に対してPPAD-hardであることを示す。 その結果, 2-team 0-sum polymatrix に対するPPAD-hardness 結果が得られた。
  論文  参考訳（メタデータ） (2026-06-15T17:37:13Z)
• MePoly: Max Entropy Polynomial Policy Optimization [11.868099733113452]
  本稿では,エネルギーモデルに基づく新しいポリシーパラメータ化であるMePolyを提案する。 MePolyは明示的でトラクタブルな密度を提供し、正確な確率を可能にする。
  論文  参考訳（メタデータ） (2026-02-19T20:52:41Z)
• Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes [18.454334675619936]
  積ポリトープ上のFrank-Wolfeアルゴリズムの線形収束について検討する。 約$mu$-Polyak-Lojasiewicz の凸対象に対しては、結果の条件数で定量化される線形収束率を示す。
  論文  参考訳（メタデータ） (2025-05-16T13:50:55Z)
• Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias [55.72269695392027]
  本稿では,線形系を解くためにエントロピックミラー降下を適用することに焦点を当てる。 収束解析の主な課題は、領域の非有界性に起因する。 制限的な仮定を課さずにこれを克服するために、Polyak型階段の変種を導入する。
  論文  参考訳（メタデータ） (2025-05-05T12:33:18Z)
• The moment polytope of matrix multiplication is not maximal [3.1593341358400737]
  行列乗算テンソルのモーメントポリトープと単位テンソルの分離を証明した。 その結果,行列乗法モーメントポリトープは最大値ではないことがわかった。 我々はこれらの手法を拡張し、行列乗法のための最適境界部分ランク境界の新たな証明を得る。
  論文  参考訳（メタデータ） (2025-03-28T17:25:06Z)
• Upper bound hierarchies for noncommutative polynomial optimization [1.2249546377051437]
  この研究は、有限個の非可換制約に対する非可換の固有値の最小化に焦点を当てている。 コンパクト集合を最小化するためのラッサール問題による上界の収束階層を導出する。
  論文  参考訳（メタデータ） (2024-02-03T11:53:57Z)
• The polygon relation and subadditivity of entropic measures for discrete and continuous multipartite entanglement [0.6759148939470331]
  エントロピーの多角形関係と部分付加率の関係について検討した。 我々の研究は多粒子状態の豊富な構造をよりよく理解する。
  論文  参考訳（メタデータ） (2024-01-04T05:09:37Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。 アルファベットのサイズについては、定値対分離の複雑さがある。
  論文  参考訳（メタデータ） (2023-01-22T22:08:28Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  断片的な離散化は既存の離散化問題と矛盾しないことを示す。 この理論を2つの画像のマッチング問題に適用する。
  論文  参考訳（メタデータ） (2021-07-13T12:31:06Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。 新規な構造化融合正規化に基づく一般グラフ推定器を提案する。 提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T04:42:32Z)
• Rethinking conditional GAN training: An approach using geometrically structured latent manifolds [58.07468272236356]
  条件付きGAN(cGAN)は、生成された出力の多様性の欠如などの重大な欠点に悩まされる。 本稿では,バニラcGANの多様性と視覚的品質を両立させる新しいトレーニング機構を提案する。
  論文  参考訳（メタデータ） (2020-11-25T22:54:11Z)

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

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