Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 9 of 301
Back to Result List

Discrete Relaxations of Combinatorial Programs

Please always quote using this URN: urn:nbn:de:0297-zib-3230
  • This paper investigates {\em relations\/} among combinatorial optimization problems. To establish such relations we introduce a transformation technique \mbox{---{\em aggregation}---} that allows to relax an integer program by means of another integer program. We prove that various families of prominent inequalities for the acyclic subdigraph problem, the multiple knapsack problem, the max cut, graph, and the clique partitioning problem, the set covering problem, and the set packing problem can be derived and separated in polynomial time in this way. Our technique is algorithmic. It has been implemented and used in a set partitioning code.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Ralf BorndörferORCiD, Robert Weismantel
Document Type:ZIB-Report
Date of first Publication:1997/11/07
Series (Serial Number):ZIB-Report (SC-97-54)
ZIB-Reportnumber:SC-97-54
Published in:Rev. vers. appeared in: Discrete Appl. Math. 112 (2001) 11-26
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.