Gruia Calinescu Gruia Calinescu joined in February 2000 the Computer Science Department at Illinois Institute of Technology. During the summer of 2002, he visited the Max-Planck-Institut fur Informatik. During the summer of 2001, he visited as a research associate the Department of Combinatorics and Optimization at University of Waterloo. During the academic year 1998-1999 he was a postdoctoral fellow at DIMACS (Center for Discrete Mathematics and Theoretical Computer Science). DIMACS is an NSF funded Science and Technology Center with partners at AT&T Labs-Research, Bellcore, Bell Labs, Princeton. His position at DIMACS was part of the Special Year on Large Scale Discrete Optimization . He completed in Summer 1998 the Algorithms, Combinatorics and Optimization PhD program at the Georgia Institute of Technology, in the College of Computing. His dissertation is titled `Approximation Algorithms for Graph-Theoretic Problems: Planar Subgraphs and Multiway Cut' and was supervised by Professor Howard Karloff.

Background:

Gruia has a Diploma from the University of Bucharest (link in Romanian language), with a (now lost) thesis in Scheduling supervised by Professor Ioan Tomescu.

Classes:

In Fall 2007, Gruia is teaching CS 535 - Design and Analysis of Algorithms.

Selected publications, starting with the most recent. Please send email for other papers.

G. Calinescu, C. Chekuri, and J. Vondrak, Disjoint Bases in a Polymatroid, submitted to Random Structures and Algorithms.

G. Calinescu, C. Chekuri, M. Pal, and J. Vondrak, Maximizing a Submodular Set Function subject to a Matroid Constraint, to appear in IPCO 2007.

D. L. Applegate, G. Calinescu, D. S. Johnson, H. Karloff, K. Ligett, J. Wang, Compressing rectilinear pictures and minimizing access control lists, as submitted to SODA 2007.

G. Calinescu and M. Pelsmajer, Fast edge colorings with fixed number of colors to minimize imbalance, submitted journal version. Extended abstract in FSTTCS 2006.

G. Calinescu, A. Dumitrescu, and J. Pach, Reconfigurations in graphs and grids, submitted journal version. Extended abstract in LATIN '06.

G. Calinescu, Analytical Bounds on Broadcast with Hitch-hiking in Wireless Ad-Hoc Networks, in MASS '05.

G. Calinescu, A. Dumitrescu, H. Karloff, and P-J Wan, Separating points by axis-parallel lines, in International Journal of Computational Geometry and Applications. An improvement over a CCCG'04 paper, this version also fixes a typo in a formula of the journal version.

G. Calinescu, Bounding the payment of approximate truthful mechanisms, in ISAAC 2004.

G. Calinescu, I. Mandoiu, P-J Wan, and A. Zelikovsky, Selecting Forwarding Neighbors in Wireless Ad Hoc Networks, in Mobile Networks and Applications, 2004. Preliminary results in DIALM 2001.

P. Berman, G. Calinescu, C. Shah, and A. Zelikovsky, Power Efficient Monitoring Schedules in Sensor Networks, in WCNC 2004. This is a rather shallow result but in light of INFOCOM 2005 papers doing even less more popularization is in order. Unfortunately the conference version has an incorrect claim in the abstract (the order of words in the sentence matter!) which is corrected in this version.

G. Calinescu and P-J. Wan, Range Assignment for High Connectivitity in Wireless Ad Hoc Networks, to appear in MONET. Preliminary version in Adhoc-Now 2003.

G. Calinescu, Computing 2-Hop Neighborhoods in Ad Hoc Wireless Networks, in Adhoc-Now '03. This is a rather shallow result but can be used as a building block in many localized algorithms.

G. Calinescu, S. Kapoor, A. Olshevsky, and A. Zelikovsky, Network Lifetime and Power Assignment in Ad-Hoc Wireless Networks, in ESA 2003.

G. Calinescu, C. G. Fernandes, H. Karloff, and A. Zelikovski, "A New Approximation Algorithm for Finding Heavy Planar Subgraphs," in Algorithmica, 2003.

G. Calinescu, C. G. Fernandes, and B. Reed, "Multicuts in Unweighted Graphs and Digraphs with Bounded Degree and Bounded Tree-Width," in Journal of Algorithms 2003. Preliminary results in IPCO 1998 and in GRACO 2001.

E. Althaus, G. Calinescu, I. Mandoiu, S. Prasad, N. Tchervenski, and A. Zelikovsky, Power Efficient Range Assignment in Ad-hoc Wireless Networks, to appear in Wireless Networks. Preliminary results in TCS '02 and WCNC '03.

G. Calinescu and P-J. Wan Splitable Traffic Partition in WDM/SONET Rings to Minimize SONET ADMs, in Theoretical Computer Science, 2002. Preliminary results in I-SPAN 2000.

G. Calinescu and P-J. Wan Traffic Partition in WDM/SONET Rings to Minimize SONET ADMs, in Journal of Combinatorial Optimization, 2002. The link is to the preliminary version from IEEE-IWTS 2001.

G. Calinescu, H. Karloff, and Y. Rabani, " Approximation Algorithms for the 0-Extension Problem," in SIAM J. Computing. Preliminary results in SODA 2001.

G. Calinescu, H. Karloff, and Y. Rabani, " An Improved Approximation Algorithm for Multiway Cut," in Journal of Computer and System Sciences, 2000. Preliminary version in STOC '98.

A. Amir and G. Calinescu. "Alphabet Independent and Dictionary Scaled Matching," in Journal of Algorithms, 2000. Preliminary version in CPM' 96.

G. Calinescu, C. G. Fernandes, U. Finkler, and H. Karloff, "A Better Approximation Algorithm for Finding Planar Subgraphs," in Journal of Algorithms, 1998. Preliminary version in SODA '96 and Cocoon '96.

Web Links

Mathematics and Computer Science - references frequently used by Gruia.