Amitabh Basu

I'm a Ph.D. student in the Algorithms, Combinatorics and Optimization (ACO) program at Carnegie Mellon University.

My research interests lie in theoretical Integer Programming, Polyhedral Theory and Combinatorial Optimization.
My thesis work is in cutting plane theory for general mixed-integer linear programs. More specifically, I am working on developing the theory of cutting planes from multiple rows of the simplex tableau. My advisor is Gerard Cornuejols.
Contact information
Address: Amitabh Basu
         Room A19B, Tepper School of Business
         Tech & Frew Street
         Pittsburgh, PA-15232
Ph:      412-268-9871
Email:   abasu1[AT]andrew[DOT]cmu[DOT]edu

Resume pdf

Research Papers

Preprints/Papers Under Review

On Lifting Integer Variables in Minimal Inequalities
accepted to IPCO 2010
Joint work with Manoel Campelo, Michele Conforti, Gerard Cornuejols and Giacomo Zambelli

Minimal inequalities for an infinite relaxation of integer programs
to appear in SIAM Journal of Discrete Mathematics (2010)
Joint work with Michele Conforti, Gerard Cornuejols and Giacomo Zambelli

A Counterexample to a conjecture of Gomory and Johnson, submitted
Joint work with Michele Conforti, Gerard Cornuejols and Giacomo Zambelli.

Maximal Lattice-free convex sets in linear subspaces, submitted
Joint work with Michele Conforti, Gerard Cornuejols and Giacomo Zambelli.

Experiments with two row cuts from degenerate tableaux, submitted
Joint work with Pierre Bonami, Gerard Cornuejols and Francois Margot

Convex Sets and Minimal Sublinear Functions, submitted
Joint work with Gerard Cornuejols and Giacomo Zambelli

Journal Articles and Conference Proceedings

On the Relative Strength of Split, Triangle and Quadrilateral Cuts
To appear in Mathematical Programming A, 2009 , DOI: 10.1007/s10107-009-0281-x. (Preliminary version in Proc. Symposium on Discrete algorithms (SODA), New York, January 2009)
Joint work with Pierre Bonami, Gerard Cornuejols and Francois Margot.

Geometric Algorithms for Optimal Airspace Design and Air Trafiic Controller Workload Balancing
ACM Journal on Experimental Algorithmics 14, 2009, 2.3--2.28. (Preliminary version in Proc. ALENEX 2008)
Joint work with Joe Mitchell and Girishkumar Sabhnani.

Distributed Localization using Noisy Distance and Angle Information
(Preliminary version in Proc. of the Seventh ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'06), 262-273, Florence, Italy, May, 2006)
Joint work with Jie Gao, Joe Mitchell and Girishkumar Sabhnani

Security types preserving compilation
Computer Languages, Systems and Structures 33, 2, July 2007, 35-59 . (Extended Abstract in Proc. VMCAI 2004, 2-15)
Joint work with Gilles Barthe and Tamara Rezk

Work in Progress and other manuscripts

Maximal Lattice-free Convex Sets in 3 Dimensions
Manuscript
with Gerard Cornuejols and Francois Margot

Steiner Point Removal in Graph Metrics
Manuscript
with Anupam Gupta