Packing and covering with integral feasible flows in integral supply-demand networks | Zendy

Robert E. Bixby | Zendy; Odile Marcotte | Zendy; L. E. Trotter | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Packing and covering with integral feasible flows in integral supply-demand networks

Author(s) -

Robert E. Bixby,

Odile Marcotte,

L. E. Trotter

Publication year - 1987

Publication title -

mathematical programming

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 2.358

H-Index - 131

eISSN - 1436-4646

pISSN - 0025-5610

DOI - 10.1007/bf02592074

Subject(s) - unimodular matrix , matroid , mathematics , set packing , packing problems , mathematical optimization , integral equation , integral geometry , combinatorics , computer science , mathematical analysis , set (abstract data type) , programming language

Polynomial-time algorithms are presented for solving combinatorial packing and covering problems defined from the integral feasible flows in an integral supply-demand network. These algorithms are also shown to apply to packing and covering problems defined by the minimal integral solutions to general totally unimodular systems. Analogous problems arising from matroid bases are also discussed and it is demonstrated that a means for solving such problems is provided by recent work of Cunningham.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research