HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Revisiting subgradient techniques applied to 3d linear assignment problem

Abstract : A subgradient technique which relies on a local approximation of AP3 polytope is proposed. On the one hand, it improves over standard subgradient enhanced with a whole class of facets, since it requires far less facets; furthermore, the selected facets are more accurate with respect to the gap between a relaxed solution and a feasible one. On the other hand, it compares favorably to Bundle-Trust method which is based on a subgradient approximation. Apart from this method, a Monge sequence is devised on a substructure local to relaxed/feasible gap, that affords us to recover from zig-zagging in some pathological cases.
Document type :
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 3:14:21 PM
Last modification on : Friday, February 4, 2022 - 3:18:43 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 4:52:58 PM


  • HAL Id : inria-00074405, version 1



Alexandre Tusera, Dominique Fortin. Revisiting subgradient techniques applied to 3d linear assignment problem. [Research Report] RR-2266, INRIA. 1994. ⟨inria-00074405⟩



Record views


Files downloads