日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細

登録内容を編集ファイル形式で保存
一時保存へ追加
 タグ情報を表示リリース履歴を表示詳細要約
  A Compact Linear Program for Testing Optimality of Perfect Matchings

Ventura, P., & Eisenbrand, F. (2003). A Compact Linear Program for Testing Optimality of Perfect Matchings. Operations Research Letters, 31, 429-434.

Item is

 

表示: 全項目 非表示: 全項目

基本情報

表示: 非表示:
アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-2BEA-A 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0024-C0EC-A
資料種別: 学術論文

ファイル

表示: ファイル

関連URL

表示:

作成者

表示:
非表示:
 作成者:
Ventura, Paolo1, 著者           
Eisenbrand, Friedrich2, 著者           
所属:
1Machine Learning, MPI for Informatics, Max Planck Society, ou_1116552              
2Discrete Optimization, MPI for Informatics, Max Planck Society, ou_1116548              

内容説明

表示:
非表示:
キーワード: -
 要旨: It is a longstanding open problem whether there exists a polynomial size description of the perfect matching polytope. We give a partial answer to this question by proving the following result. The polyhedron defined by the constraints of the perfect matching polytope which are active at a given perfect matching can be obtained as the projection of a compact polyhedron. Thus there exists a compact linear program which is unbounded if and only if the perfect matching is not optimal with respect to a given edge weight. This result provides a simple reduction of the maximum weight perfect matching problem to compact linear programming.

資料詳細

表示:
非表示:
言語: eng - English
 日付: 2004-07-012003
 出版の状態: 出版
 ページ: -
 出版情報: -
 目次: -
 査読: 査読あり
 識別子（DOI, ISBNなど）: eDoc: 201880
その他: Local-ID: C1256BDD00205AD6-4A3D46B34DD76218C1256D09002D6698-VE2003
 学位: -

関連イベント

表示:

訴訟

表示:

Project information

表示:

出版物 1

表示:
非表示:
出版物名: Operations Research Letters
種別: 学術雑誌
 著者・編者:
所属:
出版社, 出版地: Amsterdam : North-Holland
ページ: - 巻号: 31 通巻号: - 開始・終了ページ: 429 - 434 識別子（ISBN, ISSN, DOIなど）: ISSN: 0167-6377
CoNE: https://pure.mpg.de/cone/journals/resource/954925483661