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: September 24, 2014.  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

  • The Salesman’s Improved Paths: A 3/2+1/34 Approximation, Foundations of Computer Science, October 2016 (FOCS 2016) pdf  NEW 
  • 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, (with J. Cheriyan, and Z. Szigeti) 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  NEW 
  • 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   
  • Problems about Uniform Covers, with Tours and Detours, Oberwolfach Report 51 (2015)    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 (in common with Zeev Vaxman), Discrete Applied Mathematics, 91 (1998) 305--311.  pdf
  • The metric dimension of Graphs, (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 29 (2007) 73-77 pdf,
  • “Generalizing all sets with bounded unions”, Combinatorics, Probability and Computing, (2008) 17, 641-660 (with Yannick Frein and Benjamin Lévęque). pdf
  • The Chromatic Gap and its Extremes, Journal of Combinatorial Theory, Series B, 102 (2012) 1155-1178   pdf 
  • Complements of nearly perfect graphs, Journal of Combinatorics, 4(3): 2013, pp 299-310.  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