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


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


Matchings in Graphs and Generalizations, Multiflows



Polyhedral Combinatorics, Packing, Covering







Scheduling  and Applications to Physics


Popularization, Theses




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

I am past 60

Mathematics Genealogy Project


Google Citations