Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/inria-00074405
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

Identifiers

  • HAL Id : inria-00074405, version 1

Collections

Citation

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

Share

Metrics

Record views

94

Files downloads

148