András Sebő

Optimisation Combinatoire, Grenoble

Key-words : Combinatorial Optimization, Graph Theory, Approximation Algorithms

Polyhedral Combinatorics, Integer Programming, Discrete Mathematics

bureau C308
46, avenue Félix Viallet
38000 Grenoble
France

mail

Last update: January 2019.  Remarks are welcome

Publications Popularization Courses CV (by Zoli) Links

You find a .pdf file of the journal version of my papers, whenever available. I leave them on my page until we, researchers in France, have free and easy access to all the documents we need for our work. Right now we have obstacles. Each time we want to access an article we have to know which of the parallel public institutions subscribed to the journal, which publishing company the journal belongs to, and if our home institutions subscribed to it, under which names and passwords we can access each. Many of our colleagues in the world get all articles they need with simple cliques for free, and I hope all researchers in France, in Europe and in the world will soon be on the list of these lucky places. Free and easy access to scientific information is an elementary necessary condition for efficient research.

Selected Publications

Approximation Algorithms for the TSP, Integrality Gap, Uniform covers

• An improved approximation algorithm for minimum size 2-edge connected spanning subgraph, in ``Integer Programming and Combinatorial Optimization 6'', Springer Verlag, Lecture Notes in Computer Science, 1412, June 1998, joint work with J. Cheriyan, and Z. Szigeti pdf
• Eight-Fifth Approximation for the Path TSP, ArXIv (September 2012) detailed ArXiv pdf, Version IPCO (Integer Programming and Combinatorial Optimization) 16, LNCS 7801 (Goemans and Correa eds), March 2013, pp 362-374. extended abstract pdf
• Shorter Tours by Nicer Ears: 7/5-appoximation for the Graph-TSP, 3/2 for the Path Version, and 4/3 for two-edge-connected subgraphs (joint work with Jens Vygen), Combinatorica 34 (5) (2014) 597-629 Combinatorica’s on line version pdf
• Problems about Uniform Covers, with Tours and Detours, Oberwolfach Report 51 (2015) pdf
• The Salesman’s Improved Paths: A 3/2+1/34 Approximation, Foundations of Computer Science, FOCS 2016, October 2016 , joint work with Anke van Zuylen pdf
• Layers and Matroids for the Travelling Salesman's Paths, joint work with Frans Schalekamp, Vera Traub and Anke van Zuylen, Operations Research Letters 46 (2018), 60—63 pdf NEW
• The Salesman’s Improved Paths, detailed journal version of the FOCS extended abstract, joint work with Anke van Zuylen, ArXiv August 28, 2018 pdf NEW
• The Salesman’s Improved Tours for Fundamental Classes, joint work with Sylvia Boyd, Integer Programming and Combinatorial Optimization, LNCS 10328, pp 111-122, June 2017 pdf Journal version ArXiv October 29, 2018 pdf NEW

General Combinatorics (Group Testing, Metric Reconstruction, Extremal Problems)

• Sequential Search using question sets with bounded intersections, Journal of Statistical Planning and Inference , 7, 1982, 932-156 pdf
• On two random search problems, Journal of Statistical Planning and Inference , 11, 1985, 23-31 pdf
• On the geodesic structure of graphs: a polyhedral approach to metric decomposition, in ``Integer Programming and Combinatorial Optimization III'', Rinaldi and Wolsey editors, Centro Ettore Majorana, Erice (1993), (in common with Michael Lomonosov). pdf (scan)
• Optimal binary trees with order constraints, joint work with Zeev Vaxman, Discrete Applied Mathematics, 91 (1998) 305--311. pdf
• The metric dimension of Graphs, joint work with Eric Tannier, Mathematics of Operations Research, (29), 2 (May 2004), pp 383--393. pdf , ipco extended abstract pdf
• Optimizing Diversity, extended abstract in Electronic Notes in Discrete Mathematics, joint work with Yannick Frein and Benjamin Lévêque, 29 (2007) 73-77 pdf
• “Generalizing all sets with bounded unions”, joint work with Yannick Frein and Benjamin Lévêque, Combinatorics, Probability and Computing, (2008) 17, 641-660. pdf

Structures and Algorithms in Combinatorial Optimization

• Finding the t-join structure of graphs, Mathematical Programming , 36, 1986, 123-134. pdf
• Undirected shortest paths and the postman-structure of graphs, Journal of Combinatorial Theory/B, 49, No 1, June 1990 pdf
• Recognizing Greedy Structures, Journal of Algorithms, 20, 1996, 137--156 (with Y.Caro and M.Tarsi). pdf
• The Path Packing Structure of Graphs Integer Programming and Combinatorial Optimization 10, New York Columbia (D. Bienstock ed.), June 2004, (with László Szegő). pdf
• A Berge-keeping operation for Graphs, volume in honor of Claude Berge edited by A. Bondy and V. Chvátal, Discrete Mathematics 306 (2006), 2582--2592. pdf

Matchings in Graphs and Generalizations, Multiflows

• A quick proof of Seymour's theorem on T-joins, Discrete Mathematics , 64, 1987, 101-103. pdf
• Covering directed and odd cuts, Mathematical Programming Study, 22, 1984, 99-112, joint work with András Frank and Éva Tardos pdf
• Cographic multicommodity flow problems: an epilogue, DIMACS Vol 1, Polyhedral Combinatorics (W. Cook and P. D. Seymour AMS, ACM eds., 1991). pdf (scan)
• Circuit packings in graphs embedded into surfaces with at most three cross-caps, in ``Integer Programming and Combinatorial Optimization III'', Rinaldi and Wolsey editors, Centro Ettore Majorana, Erice (1993). pdf (scan)
• General antifactors of graphs, Journal of Combinatorial Theory , Series B, 58, 2, July 1993. pdf
• Plane multiflows with a fixed number of demands, Journal of Combinatorial Theory/B , 59,163-171, Novembre 1993. pdf
• A generalized cut condition for multiflows in matroids, (with Werner Schwärzler), Discrete Mathematics , 113, (1993) 207-221. pdf
• On multiflow maximization, SIAM Journal of Discrete Mathematics, February 1997, 158-170, (with A.Frank and A.Karzanov). ps
• Potentials in Undirected Graphs and Planar multiflows, SIAM J. Computing, March 1997, 582-603 pdf
• On integer multiflows and metrics in binary Matroids, in `Combinatorics and Computer Science', Lecture Notes in Computer Science 1120 (Springer), 1997, 218-233 (with K. Marcus). pdf
• Integer multiflows and metric packings beyond the cut condition with Karina Marcus), Discrete Mathematics, 239 (1-3) (2001) pp. 13-31 pdf
• Connected Joins in Graphs, (joint work with Eric Tannier), Integer Programming and Combinatorial Optimization, LNCS 2081, May 2001. pdf
• Minsquare Factors and Maxfix Covers of Graphs (with Nicola Apollonio), Integer Programming and Combinatorial Optimization 10, New York Columbia (D. Bienstock ed.), June 2004. pdf
• Multiflows and Klein’s bottle (with Bert Gerards, in preparation)
• Disjoint Paths Problems: an Annotated Tableau (with Guyslain Naves), accepted for William Cook, László Lovász, Jens Vygen (Editors), Research Trends in Combinatorial Optimization.Springer, Berlin 2009, The original publication is available at www.springer.com/978-3-540-76795-4 , pdf
• How many matchings cover the nodes of a graph ? , joint work with D. Ait Ferhat, Z. Király and G. Stauffer, ArXiv November 18, 2018 pdf NEW

Polyhedral Combinatorics, Packing, Covering

• Covering directed and odd cuts, Mathematical Programming Study, 22, 1984, 99-112 (with András Frank and Éva Tardos) pdf
• Total dual integrality implies local strong unimodularity, (with Bert Gerards), Mathematical Programming , 38 (1987), 69-73. pdf
• Dual integrality in parity constrained subgraph polyhedra, in ''Infinite and Finite Sets" (eds.: Hajnal, T. Sós) Proceedings of the conference held in Eger, July 1987.
• The Schrijver system of odd join polyhedra, Combinatorica , 8 (1) (1988), 103-116. pdf
• Hilbert bases, Caratheodory's theorem and Combinatorial Optimization, in ``Integer Programming and Combinatorial Optimization I'', University of Waterloo Press, R. Kannan and W. Pulleyblank eds, ISBN 0-88898-099-X, (1990). pdf
• On combinatorial properties of binary spaces Integer Programming and Combinatorial Optimization 5'', Springer Verlag, Lecture Notes in Computer Science, E. Balas and J. Clausen editors, Springer Verlag, May 1995, ISBN-3-540-59408-6. (Vancouver), (with Beth Novick). pdf
• On Ideal Clutters, Metrics and Multiflows, in ``Integer Programming and Combinatorial Optimization 5'', Springer Verlag, Lecture Notes in Computer Science, 1084, June 1996 (Vancouver), (with Beth Novick). pdf
• Characterizing Noninteger Polyhedra with 0-1 constraints, in ``Integer Programming and Combinatorial Optimization 6'', Springer Verlag, Lecture Notes in Computer Science, 1412, June 1998 (Houston). pdf
• An introduction to empty lattice-simplices, in Lecture Notes in Computer Science 1610, (Cornuéjols, Burkard, Woeginger Eds.), Springer, June 1999. pdf
• Integer Polyhedra: Combinatorial Properties and Complexity (semi-plenary lecture and survey paper for the International Symposium on Mathematical Programming in Atlanta, august 2000), accepted draft to Math Programming, cf. Cahiers du Laboratoire Leibniz, 2001. On request
• Imperfect and nonideal clutters: a common approach, (with M. Preissmann and G. Gasparyan), Combinatorica, 23 (2) (2003) 283--302 pdf
• Minmax Theorems in Cyclically Ordered Graphs, Journal of Combinatorial Theory/B, 97 (4), July 2007. pdf
• Paintshop, Necklaces and Combinatorial Optimization (with Frédéric Meunier), Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.06.017 2008. pdf
• Cyclic Orders: Equivalence and Duality (with Pierre Charbit), Combinatorica 28 (2) (2008) 131–143. pdf

Coloring

• The clique rank and the coloration of perfect graphs, joint work with Jean Fonlupt, in ``Integer Programming and Combinatorial Optimization I , University of Waterloo Press, R. Kannan and W. Pulleyblank eds, (1990). --- scanned pdf
• Forcing Colorations and the Perfect graph conjecture, in ``Integer Programming and Combinatorial Optimization II'', Balas, Cornuéjols, Kannan eds, (1992), Carnegie Mellon University Press. pdf
• On critical edges in minimal imperfect graphs, Journal of Combinatorial Theory, B, 67, (1996), 62--85. pdf
• On the connectivity of minimal imperfect graphs, Journal of Graph Theory , 23, 1996, 77-85 pdf
• Coloring Precolored Perfect Graphs, Journal of Graph Theory, 25 (3), 1997, pp. 207-216 (with Jan Kratochvíl) pdf
• Flows, View Obstructions and the Lonely Runner, Journal of Combinatorial Theory, 72, 1, January 1998, (with W. Bienia, L. Goddyn, P. Gwozdiak, M. Tarsi). pdf
• Directed Versions of the Graham-Pollak Theorem, Cahiers du Laboratoire Leibniz , Octobre 2000 (with A. Gyárfás) On request
• Some aspects of minimally imperfect graphs, (with Myriam Preissmann), Chapter in Ramirez Alfonsin, J.L.(ed.); Reed, Bruce (ed.) Perfect graphs. Chichester: Wiley, (2001), pages 185--214. pdf
• Coloring the maximal cliques of graphs, SIAM Journal on Discrete Mathematics 17 (2004), 3, pp. 361-376, (with Bacsó, Gyárfás, Gravier, Preissmann) SIAM Journal of Discrete Mathematics, Vol 17, No 3, pp 361-376 pdf
• The Chromatic Gap and its Extremes, Journal of Combinatorial Theory, Series B, 102 (2012) 1155-1178 (with Gyárfás and Trotignon) pdf
• Complements of nearly perfect graphs, Journal of Combinatorics (with Gyárfás, Li, Machado, Thomassé, Trotignon), 4(3): 2013, pp 299-310. pdf

Scheduling and Applications to Physics

• A Particular Timetable Problem: Terminal Scheduling, Computers and Mathematics , vol 21, 1, 1991 (Selection of Hungarian Applied Mathematics). pdf
• Optimal cuts in graphs and statistical mechanics, Journal of Mathematical and Computer Modelling, Vol 26, No 8-10, 1997, pp. 1-11, (with J. C. Anglès d'Auriac and M. Preissmann). pdf
• Approximation algorithms and ear decompositions of graphs (in common with Cheriyan and Szigeti), SIAM J. Discrete Math. Vol 14, No 2 (2001), pp 130-180 pdf
• Optimal Cooperation and computing Pott's partition function with a large number of states, in common with Myriam Preissmann, Jean-Christian Anglès-d'Auriac and Ferenc Iglói, Journal of Theoretical Physics, 2002. pdf
• Batch Processing with Interval Graph Compatibilities Between Tasks , Discrete Applied Mathematics, Volume 156, issue 5, March 2008, pp 556-568 (with Gerd Finke, Vincent Jost and Maurice Queyranne). pdf
• Graphic Submodular Function Minimization:a Graphic Approach and Applications, (with Myriam Preissmann), William Cook, László Lovász, Jens Vygen (Editors): Research Trends in Combinatorial Optimization.Springer, Berlin 2009, The original publication is available at www.springer.com/978-3-540-76795-4 pdf (scan)

Popularization, Theses

• Combinatorial search problems, M.S. thesis, 1979, (in Hungarian).
• Solution of timetable problems with network flow methods, Ph.D. thesis, Eötvös Loránd University, 1983, (in Hungarian).
• Graph factors: Structures and Algorithms, Thesis for the 'Candidate of Sciences' degree (in Hungarian), 1987.
• `Peut-on trouver ce qu'on peut prouver ?', 'La Recherche', numéro spécial `Mathématiques', octobre 2001 (in French, first edition) scanned pdf
• Les quarante deux ans de la conjecture de Berge ','La Recherche', 'Hors Série' entitled 'La Preuve Scientifique', (in French) Juillet-Août-Septembre 2002 , scanned pdf de l’encadré ajouté à la republication de 'Peut-on trouver ce qu'on peut prouver'. scanned pdf (de la deuxième édition, corrigé, avec l’encadré, mais j’aime moins les dessins)
• Le charme discret des mathématiques, Image des mathématiques, Publication CNRS, édition 2006. (in French) --- pdf
• Parcours et Coupes, (with Frédéric Meunier), Chapter in "Graphes et Applications", textbook, Hermes (Jean-Claude Fournier ed), 2006. pdf

Courses

• Matching and Routing (Grenoble, Lausanne 1993-2003) ppt ; warm up exercises pdf
• Cyclic Orders (Tokyo, Budapest 2004-2005) ppt
• Integer Decomposition (Cargèse 2011) ppt
• Combinatorial Optimization : an Introduction (Grenoble, Xerox Research 2011) download . ppt
• Combinatorial Optimization : Matchings, Matroids and Application to the TSP (Buenos Aires 2013) pdf : 1 2 3 4 5
• Ideas from exact and approximative, classic and recent combinatorial optimization: Matchings, Edge-Colorings and the TSP 1 2 3 4

Useful pages : EGRES, C&O, CWI, MIT , Bonn, LL Chvátal Kalai Cook Frédéric Guyslain

I am past 60

Mathematics Genealogy Project

MathScinet

Google Citations