English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2BEA-A Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-C0EC-A
Genre: Journal Article

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Ventura, Paolo1, Author           
Eisenbrand, Friedrich2, Author           
Affiliations:
1Machine Learning, MPI for Informatics, Max Planck Society, ou_1116552              
2Discrete Optimization, MPI for Informatics, Max Planck Society, ou_1116548              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2004-07-012003
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 201880
Other: Local-ID: C1256BDD00205AD6-4A3D46B34DD76218C1256D09002D6698-VE2003
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Operations Research Letters
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: Amsterdam : North-Holland
Pages: - Volume / Issue: 31 Sequence Number: - Start / End Page: 429 - 434 Identifier: ISSN: 0167-6377
CoNE: https://pure.mpg.de/cone/journals/resource/954925483661