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 <>
Submitted on : Wednesday, May 24, 2006 - 3:14:21 PM
Last modification on : Thursday, February 11, 2021 - 2:50:07 PM
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