**Deepak Rajan**

Email: drajan "at" us.ibm.com

Web:
research.ibm.com/people/d/dpkrjn

823 Huntingon Drive,
IBM T.J. Watson Research Center,
Fishkill, NY - 12524
19 Skyline Drive, Hawthorne NY - 10532
(510) 501-5852
(914) 784-6046

Professional
Awards
Research
Teaching
Skills

Go to top. |

Ph.D **University of
California at Berkeley,** Dec 2004.

*
Industrial Engineering and Operations
Research
*
**Minors:** Statistics, Computer Science.

**Designing capacitated survivable networks: Polyhedral analysis
and algorithms.**
A network is said to be survivable if all
demands on the network can be met under the failure of any one of
its edges. We present new models,
study relevant pricing problems and
develop cutting planes that are incorporated in a computationally
efficient algorithm. We also study various
mixed-integer sets and their polyhedra in to develop strong
valid inequalities for the mixed-integer knapsack set.
[PDF]

**Dissertation Committee :** *
Alper
Atamtürk,
Ilan Adler,
Dorit
Hochbaum,
Thomas Henzinger.*

M.S **University of
California at Berkeley,** 2001.

*Industrial Engineering and
Operations Research*

B.Tech **
Indian Institute of Technology - Madras,** 1999.

*Mechanical Engineering*

Software Tools and Techniques group (Manager: Dr. Philip S. Yu)

Oct 6, 2004 - present, full time.

Responsible for carrying out fundamental research in Computer Science and Operations Research, as well as towards the System S project, a large-scale distributed stream processing system. Specifically, I am responsible for the design and development of the scheduler of the system, as well as dynamic optimization of query graphs, resource adaptive stream operators, and the development of power-aware load scheduling techniques.

*Student Researcher*

**University of California at
Berkeley**,
Mar 2000 - Sep 2004, part time.

With Alper
Atamtürk,
Mar
2000 - Sep 2004.
**General mixed-integer knapsack set.**
Developed strong valid inequalities using sequence
independent lifting (in polynomial time) of facets of the restriction with one
continuous and two integer variables.
**Capacitated survivable network design.**
Proposed a method which introduces slack on directed cycles used as
failure-flow patterns to restore disrupted flow.
Studied pricing problems and developed metric-type
inequalities.
**Network design arc-set polyhedra.**
Analyzed the optimization problems over arc sets,
developed a linear-time separation algorithm for the
splittable arc-set, and introduced two classes of inequalities for the
unsplittable arc-set.

With
George Shanthikumar, Aug - Dec 2002.
**Matroids and transposition increasingness.**
Attempted to link deterministic optimization over structured sets
(*e.g.* matroids) to optimization over these sets for partial stochastic
orders.

* Summer Intern*

**IBM T.J. Watson Research
Center**, Jun - Aug 2003, full time.

With Gyana Parija,

*Student Researcher*

**
Indian Institute of Technology - Madras**, Aug 1998 - May 1999,
part time.

With
G.
Srinivasan.
**Cutting stock problem.**
Developed and implemented an LP-based heuristic that efficiently solves the
1-D problem by crash-starting the LP
using a near-optimal LP relaxation basis, and
then applies a single-pass rounding heuristic.

*
Institute for Operations Research and the Management Sciences
(INFORMS).*

Go to top. |

**
IBM Invention Achievement Award**

First Plateau Award

**
Dissertation Award,
Informs Technical Section on Telecommunications,
INFORMS**, 2006

Honorable Mention.

**Judith Liebman
Award,
INFORMS**, 2004

* Recognizes outstanding student volunteers who have been "moving
spirits" in their universities, their student chapters, and the
Institute.*

**Best Student Research Presentation,
PRISMS**, 2002.

*Over 100 participants from seven universities, including
Stanford
University and University of
California at Berkeley.*

**Regents Block Grant Fellowship,
University of
California at Berkeley,** 1999-2000

**
National Talent Search
Scholarship, India, ** 1993 - 1998.

*One of 750 awarded among applicants from high schools all over India.
*

Method and apparatus for scheduling work in a stream-oriented computer system.

Method and apparatus for assigning fractional processing nodes to work in a stream-oriented computer system.

Method and apparatus for assigning candidate processing nodes in a stream-oriented computer system.

Method and systems for assigning non-continual jobs to candidate processing nodes in a stream-oriented computer system.

Method and apparatus for predicting resource usage of reusable stream processing elements

Go to top. |

Atamtürk, A. and Rajan, D.
*"Partition inequalities for capacitated survivable network design
based on directed p-cycles."* To appear in **
Discrete Optimization**.
[PS]
[PDF]

Rajan, D., and Yu, P. S.
*"On temperature-aware scheduling for single-processor systems."*
**
HiPC 2007**,
LNCS 4873, 342-355.
[PS]
[PDF]

Rajan, D., and Yu, P. S.
*"Temperature-aware scheduling: When is system-throttling good
enough?"
*
IBM Research Report RC24331, 2007.
[PS]
[PDF]

Lucchese, C., Vlachos, M., Rajan, D., and Yu, P. S.
*
"Rights Protection of Multidimensional Time-Series Datasets with
Neighborhood Preservation."
*
To appear in **
Proceedings of the 24th International Conference on Data Engineering**.
[PDF]

Vlachos, M., Rajan, D., Lucchese, C., and Yu, P. S.
*"Ownership Protection of Shape Datasets
with Geodesic Distance Preservation."*
To appear in **
Proceedings of the 11th International Conference on Extending Database
Technology**.
[PDF]

Rajan, D., and Yu, P. S.
*"Discovering partial orders in binary data."*
**
Proceedings of the 2006 IEEE International Conference on Data Mining
(ICDM)**, 2006, 510-521.
[PS]
[PDF]

Rajan, D. and Takriti, S.
*"Minimum up/down polytopes of the unit commitment problem with start-up
costs."*
**
IBM Research Report** RC23628, 2005.
[PS]
[PDF]

Rajan, D. and Atamtürk, A.
*"A directed cycle based column-and-cut generation method for
capacitated survivable network design."*
**
Networks**, 43, 201-211, 2004.
[PS]
[PDF]

Atamtürk, A. and Rajan, D.
*"On
splittable and unsplittable flow capacitated network-design arc-set
polyhedra."*
**
Mathematical Programming**, 92, 315-333, 2002.
[PS]
[PDF]

Rajan, D. and Atamtürk, A.
*"Survivable network design : Routing of flows and slacks."*
Chapter in **
Telecommunications Network Design and Management**, 65-81,
Kluwer Academic Publishers, 2002.
[PS]
[PDF]

Atamtürk, A. and Rajan, D.
*"A new model for designing survivable networks."*
**
Proceedings of the 10th International Conference on
Telecommunication Systems Modeling and Analysis (ICTSM10)**, 2002.
[PS]
[PDF]

Rajan, D., and Yu, P. S.
*"Temperature-aware scheduling: When is system-throttling good
enough?"*
Submitted to **
22nd IEEE International Parallel and Distributed Processing Symposium**.
[PS]
[PDF]

Dash, S., Lodi, A., and Rajan, D.
*"The {-1,0,1} unconstrained QP."*
In preparation.

Atamtürk, A. and Rajan, D.
*"On the polyhedron of the general mixed-integer knapsack set."*
In preparation.

Rajan, D. and Shanthikumar, G.
*"On a class of easily solvable combinatorial optimization problems with
stochastic objective."* In preparation.

Rajan, D., and Yu, P. S.
*"Discovering partial orders in binary data,"*
**
The 2006 IEEE International Conference on Data Mining
(ICDM)**,
Dec 2006, Hong Kong, China.

Atamtürk, A. and Rajan, D.
*"Partition inequalities for survivable network design using p-cycles,"*
**
The Eighth INFORMS Telecommunications Conference**,
Mar 2006, Dallas, Texas.
**
IBM T.J. Watson Research Center**, Mar 2006, Yorktown Heights, New York.

Rajan, D., Dash, S. and Lodi, A.
*"3-State Unconstrained Quadratic Programming,"*
**
INFORMS Annual Meeting**, Nov 2005, San Francisco, California.
**
IBM T.J. Watson Research Center**, Nov 2005, Yorktown Heights, New York.
**
INFORMS International Meeting**, Jul 2007, Puerto Rico.

Atamtürk, A. and Rajan, D.
*"Metric-type Inequalities for Survivable Network Design using
Directed Cycles,"*
**
INFORMS Annual Meeting**, Oct 2004, Denver, Colorado.
**
IBM T.J. Watson Research Center**, Dec 2004, Yorktown Heights, New York.

Atamtürk, A. and Rajan, D.
*"Polynomially-Computable Lifting Functions for Two-Variable
Integer Knapsack Inequalities,"*
**
INFORMS Annual Meeting**, Oct 2004, Denver, Colorado.

Rajan, D.
*"Designing capacitated survivable networks: Polyhedral analysis
and algorithms,"*
**University of Minnesota**,
Apr 2004, Minneapolis, Minnesota.
**
The Eighth INFORMS Telecommunications Conference**,
Mar 2006, Dallas, Texas.
**
IBM T.J. Watson Research Center**, Mar 2006, Yorktown Heights, New York.

Atamtürk, A. and Rajan, D.
*"On the knapsack set with one continuous and two integer
variables,"*
**
INFORMS Annual Meeting**, Oct 2003, Atlanta, Georgia.

Rajan, D., Lee, J. and Takriti, S.
*"The unit commitment problem : A polyhedral study,"*
**
IBM T.J. Watson Research Center**, Aug 2003, Yorktown Heights, New York.
**
INFORMS Annual Meeting**, Oct 2003, Atlanta, Georgia.

Rajan, D. and Atamtürk, A.
*"A new model for designing survivable networks,"*
**
The 10th International Conference on
Telecommunication Systems Modeling and Analysis (ICTSM10)**, Oct
2002, Monterey, California.
HP Labs,
Apr 2003, Palo Alto, California.
**
IBM T.J. Watson Research Center**, Jul 2003, Yorktown Heights, New York.

Rajan, D. and Atamtürk, A.
*"Designing survivable networks with directed cycles for routing
disrupted flow,"*
**
Pacific Region Intercollegiate Symposium for the Management
Sciences (PRISMS)**,
Mar 2002, Palo Alto, California.

Atamtürk, A. and Rajan, D.
*"Designing capacity-efficient survivable networks with failure
flow patterns,"*
**INFORMS Annual
Meeting**, Nov 2001, Miami Beach, Florida.

Atamtürk, A. and Rajan, D.
*"A branch and cut algorithm for multicommodity network design
problems,"*
**INFORMS
Annual Meeting**, Nov 2000, San Antonio, Texas.

Go to top. |

**Instructor.**
Completely responsible for class.

*
Operations Research I*. Aug - Dec 2003.

Introduction to deterministic optimization. Nonlinear programming,
integer programming, network flows.

**Teaching Assistant.**
Held discussion sections/labs, office hours and graded papers/exams.

*Operations Research I*. Aug - Dec 2000.

Introduction to deterministic optimization. Nonlinear programming,
integer programming, network flows.

**Teaching Assistant.**
Held discussion sections/labs, office hours and graded papers/exams.

*Fundamentals of Operations Research.*
Jul - Nov 1998.

Linear programs, simplex method, sensitivity analysis,
duality theory, complementary slackness.

Go to top. |

** Programming/Software Languages :**
CPLEX
Callable Libraries,
C/C++,
Java,
AMPL,
Matlab,
R/Splus,
SIGMA,
LaTeX, HTML,
Pascal,
Perl,
SQL.

** Operating Systems :** Unix/Linux/Solaris (system
administrator), Windows 98/NT/2000/XP.

** Languages :** Fluent in English, Hindi and Tamil.

** Referee**

International Conference on Distributed Computing Systems,
INFORMS Journal of Computing,
Mathematical Programming,
Networks,
Networks and Spatial Economics,
Operations Research.

** Session Chair**

INFORMS International Meeting 2007.

**Coordinator, **
Pacific Region
Intercollegiate Symposium for the Management Sciences, 2003.

*Student conference for OR/MS programs in the Bay Area - more than 50
participants.
*

**President, **
Berkeley Student INFORMS Chapter, 2001-2002.

*Instrumental (with fellow officers) in reviving the long-dormant
student organization.*

**Graduate Student Representative, ** Departmental Research
Seminar Committee, 2001-2002.

* Organize weekly research seminar, with invited faculty/industry
practitioners.*

References available upon request.

Citizen of India.

Go to top. |