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, and I hope France will soon  be on the list of these lucky places.

Selected Publications

Approximation Algorithms for the TSP and 2-edge-connected

  • 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), November 2014 Combinatorica’s on line version pdf  NEW 
  • Eight-Fifth Approximation for the Path TSP,  ArXIv (September 2012) detailed ArXiv pdf NEW, Version IPCO (Integer Programming and Combinatorial Optimization) 16, LNCS 7801 (Goemans and Correa eds), March 2013, pp 362-374. extended abstract 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    NEW
  • Complements of nearly perfect graphs, Journal of Combinatorics, 4(3): 2013, pp 299-310.  pdf    NEW


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