András Sebő

Optimisation Combinatoire, Grenoble

 

portre1                                    

 

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: 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

 

Coloring

 

 

Scheduling  and Applications to Physics

 

Popularization, Theses

 

Courses

 

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