Research
Home | Research | Teaching | CV (pdf) | Coursework

Research

My research interests lie in Theoretical Computer Science (mainly the design and analysis of algorithms) and Combinatorics (mainly structural graph theory). I am currently working on approximation algorithms for combinatorial optimization problems. The main areas of approximation that I have worked in are Mathematical Programming, Network Design, Submodular Optimization, Geometric Approximation, and Routing. I am also very interested in designing MapReduce algorithms.

Publications

  1. Approximation Algorithms and Hardness of Integral Concurrent Flow
    2. Parinya Chalermsook, Julia Chuzhoy, Alina Ene, Shi Li. STOC 2012, to appear.

  2. Lovász versus Local Distribution: the Approximability of Multiway Partitioning Problems
    3. Alina Ene, Jan Vondrák, Yi Wu. Manuscript, November 2011.

  3. Geometric Packing under Non-uniform Constraints
    4. Alina Ene, Sariel Har-Peled, Benjamin Raichel. arXiv, July 2011.

  4. Approximation Algorithms for Submodular Multiway Partition
    5. Chandra Chekuri, Alina Ene. FOCS 2011. Preliminary version on the arXiv.

  5. Fast Clustering using MapReduce
    6. Alina Ene, Sungjin Im, Benjamin Moseley. arXiv, September 2011. Extended abstract in KDD 2011 (oral presentation).

  6. Submodular Cost Allocation Problem and Applications
    7. Chandra Chekuri, Alina Ene. arXiv, May 2011. Extended abstract in ICALP 2011.

  7. Prize-Collecting Steiner Tree and Forest in Planar Graphs
    8. Chandra Chekuri, Alina Ene, Nitish Korula. arXiv, June 2010.
    Note: We merged with an independent paper by Bateni, Hajiaghayi and Marx, and the combined paper appeared in SODA 2011.

  8. Unsplittable Flow in Paths and Trees, and Column-Restricted Packing Integer Programs
    9. Chandra Chekuri, Alina Ene, Nitish Korula. APPROX, 2009.

Undergraduate Work
  1. Fast Exact and Heuristic Methods for Role Minimization Problems
    2. Alina Ene, William Horne, Nikola Milosavljevic, Prasad Rao, Robert Schreiber, Robert E. Tarjan. SACMAT, 2008.

Talks

  1. Approximation Algorithms for Submodular Multiway Partition
    2. Conference version presented at FOCS 2011.
    Longer version presented at the UIUC Theory Seminar, Oct 2011.

  2. Fast Clustering using MapReduce
    3. Conference version presented at KDD 2011.
    Longer version presented at IBM Almaden, Jun 2011.

  3. Submodular Cost Allocation Problem and Applications
    4. Conference version presented at ICALP 2011.
    Longer version presented at the UIUC Theory Seminar, Feb 2011.

  4. Prize Collecting Steiner Tree and Forest in Planar Graphs
    5. Conference version presented at SODA 2011 (co-presented with Hossein Bateni).
    Shorter version presented at the Midwest Theory Day, Dec 2010.
    Longer version presented at the UIUC Theory Seminar, Nov 2010.

  5. Column-Sparse and Column-Restricted Packing Integer Programs
    6. UIUC Theory Seminar, Aug 2009.

  6. Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
    7. Conference version presented at APPROX 2009.
    Shorter version presented at the Midwest Theory Day, Apr 2009.
    Longer version presented at the UIUC Theory Seminar, Apr 2009.

Undergraduate Work
  1. Minimum Biclique Covers
    2. Hewlett-Packard Labs, Palo Alto CA, 2007.

Last update: November 3, 2011