Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

| Crea un account

Del Pia, Alberto (2009) On matrices with the Edmonds-Johnson property. [Tesi di dottorato]

Full text disponibile come:

[img]
Anteprima
Documento PDF
608Kb

Abstract (inglese)

The strong Chvátal rank of a rational matrix A is the smallest number t such that the polyhedron defined by the system b <= A x <= c, l <= x <= u has Chvátal rank at most t for all integral vectors b,c,l,u. Matrices with strong Chvátal rank at most 1 are said to have the Edmonds-Johnson property. There are two main classes of matrices known to have the Edmonds-Johnson property, one was introduced by Edmonds and Johnson, and the other by Gerards and Schrijver.

Characterizing integral matrices with the Edmonds-Johnson property seems complicated. However, Gerards and Schrijver noticed that there are some openings if we restrict ourselves to totally half-modular matrices, and they conjectured a characterization of totally half-modular matrices with the Edmonds-Johnson property. In this thesis we introduce two new classes of totally half-modular matrices with the Edmonds-Johnson property, that prove the validity of the conjecture by Gerards and Schrijver in two particular cases.

In Chapter 3 we study systems of the from b <= Mx <= d, l <= x <= u, where M is obtained from a totally unimodular matrix with two nonzero elements per row by multiplying by 2 some of its columns, and b,d,l,u are integral vectors. We give an explicit description of a totally dual integral system that describes the integer hull of the polyhedron P defined by the above inequalities. Since the inequalities of such totally dual integral system are Chvátal inequalities for P, our result implies that the matrix M has the Edmonds-Johnson property.

In Chapter 4 we consider the class of totally half-modular matrices obtained from matrices 0, ± 1 with at most two nonzero entries per column by multiplying by 2 some of the columns. In this class we characterize, in terms of excluded minors, the matrices that have the Edmonds-Johnson property.

Abstract (italiano)

Il rango forte di Chvátal di una matrice razionale A è il più piccolo numero t tale che il poliedro definito dal sistema b <= A x <= c, l <= x <= u ha rango di Chvátal al più t per tutti i vettori interi b,c,l,u. Matrici con rango forte di Chvátal al più 1 si dicono avere la proprietà di Edmonds-Johnson. Ci sono due principali classi note di matrici con la proprietà di Edmonds-Johnson, una fu introdotta da Edmonds e Johnson, e l'altra da Gerards e Schrijver.

Caratterizzare le matrici intere con la proprietà di Edmonds-Johnson sembra complicato. Tuttavia, Gerards e Schrijver notarono che ci sono più possibilità se ci restringiamo alle matrici totalmente 1/2-modulari, e congetturarono una caratterizzazione delle matrici totalmente 1/2-modulari con la proprietà di Edmonds-Johnson. In questa tesi introduciamo due nuovi classi di matrici totalmente 1/2-modulari con la proprietà di Edmonds-Johnson, che provano la validità della congettura di Gerards e Schrijver in due casi particolari.

Nel Capitolo 3 studiamo sistemi nella forma b <= Mx <= d, l <= x <= u, dove M è ottenuta da una matrice totalmente unimodulare con due elementi diversi da zero per riga moltiplicando per 2 alcune colonne, e b,d,l,u sono vettori interi. Noi diamo una descrizione esplicita di un sistema totally dual integral che descrive l'inviluppo convesso dei punti interi del poliedro P definito dalle disuguaglianze precedenti. Dato che le disuguaglianze di tale sistema totally dual integral sono disuguaglianze di Chvátal per P, questo implica che la matrice M ha la proprietà di Edmonds-Johnson.

Nel Capitolo 4 consideriamo la classe delle matrici totalmente 1/2-modulari ottenute da matrici 0, ± 1 con al più due elementi non zero per colonna moltiplicando per 2 alcune colonne. In questa classe caratterizziamo, in termini di minori esclusi, le matrici che hanno la proprietà di Edmonds-Johnson.

Statistiche Download - Aggiungi a RefWorks
Tipo di EPrint:Tesi di dottorato
Relatore:Zambelli, Giacomo
Dottorato (corsi e scuole):Ciclo 21 > Scuole per il 21simo ciclo > SCIENZE MATEMATICHE > MATEMATICA COMPUTAZIONALE
Data di deposito della tesi:28 Gennaio 2009
Anno di Pubblicazione:Gennaio 2009
Parole chiave (italiano / inglese):Combinatorial optimization, Integer programming, Total dual integrality, Strong Chvátal rank, Edmonds-Johnson property
Settori scientifico-disciplinari MIUR:Area 01 - Scienze matematiche e informatiche > MAT/09 Ricerca operativa
Struttura di riferimento:Dipartimenti > Dipartimento di Matematica Pura e Applicata
Codice ID:1557
Depositato il:28 Gen 2009
Simple Metadata
Full Metadata
EndNote Format

Bibliografia

I riferimenti della bibliografia possono essere cercati con Cerca la citazione di AIRE, copiando il titolo dell'articolo (o del libro) e la rivista (se presente) nei campi appositi di "Cerca la Citazione di AIRE".
Le url contenute in alcuni riferimenti sono raggiungibili cliccando sul link alla fine della citazione (Vai!) e tramite Google (Ricerca con Google). Il risultato dipende dalla formattazione della citazione.

[1] P. Camion, Caract¶erisation des matrices unimodulaires, Cahiers du Cen- Cerca con Google

tre d' ¶ Etudes de Recherche Op¶erationnelle 5 (1963) 181-190. Cerca con Google

[2] P. Camion, Matrices totalement unimodulaires et problµemes combi- Cerca con Google

naioires, Ph.D. Thesis, Universit¶e Libre de Bruxelles, Brussels, 1963. Cerca con Google

[3] P. Camion, Characterizations of totally unimodular matrices, Proceed- Cerca con Google

ings of the American Mathematical Society 16 (1965) 1068-1073. Cerca con Google

[4] R. Chandrasekaran, Polynomial algorithms for totally dual integral sys- Cerca con Google

tems and extensions, in Studies on Graphs and Discrete Programming Cerca con Google

(P. Hansen, ed.), Annals of Discrete Mathematics 11 (1981) 39-51. Cerca con Google

[5] V. Chvatal, Edmonds polytopes and a hierarchy of combinatorial prob- Cerca con Google

lems, Discrete Mathematics 4 (1973) 305-337. Cerca con Google

[6] M. Conforti, M. Di Summa, F. Eisenbrand, and L.A. Wolsey, Network Cerca con Google

formulations of mixed-integer programs, accepted in Mathematics of Cerca con Google

Operations Research, 2006. Cerca con Google

[7] M. Conforti, A.M.H. Gerards, and G. Zambelli, Mixed-integer vertex Cerca con Google

covers on bipartite graphs, in Integer Programming and Combinatorial Cerca con Google

Optimization (M. Fischetti and D.P. Williamson eds.), proceedings of Cerca con Google

IPCO 2007, LNCS Vol. 4513, Springer, 2007, 324-336. Cerca con Google

[8] W. Cook, A.M.H. Gerards, A. Schrijver, and ¶E. Tardos, Sensitivity the- Cerca con Google

orems in integer linear programming, Mathematical Programming 34 Cerca con Google

(1986) 251-264. Cerca con Google

[9] G. Cornu¶ejols, J. Fonlupt, and D. Naddef, The Traveling Salesman Prob- Cerca con Google

lem on a Graph and some Related Integer Polyhdra, Mathematical Pro- Cerca con Google

gramming 33 (1985) 1{27. Cerca con Google

[10] A. Del Pia, A. Musitelli, and G. Zambelli, A class of matrices with the Cerca con Google

Edmonds-Johnson property, manuscript, 2008. Cerca con Google

100 BIBLIOGRAPHY Cerca con Google

[11] A. Del Pia and G. Zambelli, A class of matrices arising from bidirected Cerca con Google

graphs: total dual integrality and strong Chv¶atal rank, submitted, 2007. Cerca con Google

[12] A. Del Pia and G. Zambelli, A class of matrices with Strong Chv¶atal Cerca con Google

Rank 1, submitted, 2008. Cerca con Google

[13] J. Edmonds, Maximum matching and a polyhedron with 0; 1-vertices, Cerca con Google

Journal of Research of the National Bureau of Standards (B) 69 (1965) Cerca con Google

125-130. Cerca con Google

[14] J. Edmonds and R. Giles, A min-max relation for submodular functions Cerca con Google

on graphs, Annals of Discrete Mathematics 1 (1977) 185-204. Cerca con Google

[15] J. Edmonds and E.L. Johnson, Matching: a well-solved class of integer Cerca con Google

linear programs, in Combinatorial Structures and Their Applications Cerca con Google

(R.K. Guy, et al., eds.), Gordon and Breach, New York, 1970, 89-92. Cerca con Google

[16] J. Edmonds and E.L. Johnson, Matching, Euler tours and the Chinese Cerca con Google

postman, Mathematical Programming 5 (1973) 88-124. Cerca con Google

[17] F. Eisenbrand, On the membership problem for the elementary closure Cerca con Google

of a polyhedron, Combinatorica 19 (1999) 297-300. Cerca con Google

[18] A.M.H. Gerards, personal communication, 2007. Cerca con Google

[19] A.M.H. Gerards and A. Schrijver, Matrices with the Edmonds-Johnson Cerca con Google

property, Combinatorica 6 (1986) 365-379. Cerca con Google

[20] A. Ghouila-Houri, Charact¶erisations des Matrices Totalement Unimod- Cerca con Google

ulaires, Comptes Rendus de l'Acad¶emie des Sciences 254 (1962) 1192- Cerca con Google

1193. Cerca con Google

[21] F.R. Giles, and W.R. Pulleyblank, Total dual integrality and integer Cerca con Google

polyhedra, Linear Algebra and Its Applications 25 (1979) 191-196. Cerca con Google

[22] M.X. Goemans, Minimum Bounded Degree Spanning Trees, Proceed- Cerca con Google

ings of the 47th Annual IEEE Symposium on Foundations of Computer Cerca con Google

Science (2006) 273-282. Cerca con Google

[23] M. GrÄotschel, L. Lov¶asz, and A. Schrijver, Geometric Algorithms and Cerca con Google

Combinatorial Optimization, Springer-Verlag, Berlin, 1988. Cerca con Google

[24] I. Heller and C.B. Tompkins, An extension of a theorem of Danzig's, in Cerca con Google

Linear Inequalities and Related Systems (H. W. Kuhn and A. W. Tucker, Cerca con Google

eds.) Princeton University Press, Princeton, N.J., 1956, 247-254. Cerca con Google

BIBLIOGRAPHY 101 Cerca con Google

[25] A.J. Ho®man and J.B. Kruskal, Integral boundary points of convex poly- Cerca con Google

hedra, in Linear Inequalities and Related Systems (H. W. Kuhnand A. Cerca con Google

W. Tucker, eds.), Princeton Univ. Press, Princeton, N.J., 1956, 223-246. Cerca con Google

[26] C.A.J. Hurkens, L. Lov¶asz, A. Schrijver, and ¶E. Tardos, How to Tidy Up Cerca con Google

your Set System?, in: Combinatorics, Colloquia Mathematica Societatis Cerca con Google

J¶anos Bolyai, 52, North-Holland (1998) 309-314. Cerca con Google

[27] K. Jain, A Factor 2 Approximation Algorithm for the Generalized Cerca con Google

Steiner Network Problem, Combinatorica 21 (2001) 39-60. Cerca con Google

[28] R.R. Meyer, On the existence of optimal solutions to integer and mixed- Cerca con Google

integer programming problems, Mathematical Programming 7 (1974) Cerca con Google

223-235. Cerca con Google

[29] A. Schrijver, Theory of Linear and Integer Programming, Wiley, New Cerca con Google

York, 1986. Cerca con Google

[30] A. Schrijver, Combinatorial Optimization. Polyhedra and E±ciency, Cerca con Google

Springer-Verlag, Berlin-Heidelberg, 2003. Cerca con Google

[31] M. Singh, Iterative methods in Combinatorial optimization, Ph.D. The- Cerca con Google

sis, Carnegie Mellon University, Pittsburgh, 2008. Cerca con Google

[32] ¶E. Tardos, A strongly polynomial minimum cost circulation algorithm, Cerca con Google

Combinatorica 5 (1985) 247-255. Cerca con Google

[33] ¶E. Tardos, A strongly polynomial algorithm to solve combinatorial linear Cerca con Google

programs, Operations Research 34 (1986) 250-256. Cerca con Google

[34] D.B.West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Cerca con Google

Saddle River NJ, 2001. Cerca con Google

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record