Gruia Calinescu Gruia Calinescu joined in February 2000 the Computer Science Department at Illinois Institute of Technology. In Fall 2008, Gruia was on sabbatical at University of Wisconsin - Milwaukee. 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 Spring 2009, Gruia is teaching CS 330 - Discrete Structures.

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

G.C. and Robert Ellis, Monitoring schedules in randomly deployed sensor networks , full version. Preliminary version in in DialM-POMC 2008.

G.C. and C. G. Fernandes, On the k-Structure Ratio in Planar and Outerplanar Graphs (link to the web site of the free Discrete Mathematics and Theoretical Computer Science), 2008.

G.C. and M. Pelsmajer, Fast edge colorings with fixed number of colors to minimize imbalance (link to the web site of the free Journal of Graph Algorithms and Applications; this paper is at the bottom of the page), 2008. Preliminary version in FSTTCS 2006.

G.C., A. Dumitrescu, and J. Pach, Reconfigurations in graphs and grids, in SIAM J. Discrete Mathematics, 2008. Preliminary version in LATIN '06.

G.C., Chandra Chekuri, and Jan Vondrak, Disjoint Bases in a Polymatroid, to appear in Random Structures and Algorithms.

G. C., Chandra Chekuri, Martin Pal, and Jan Vondrak, Maximizing a Submodular Set Function subject to a Matroid Constraint, as submitted to IPCO 2007. This result was improved by Jan Vondrak (available from his web page).

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

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

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

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

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

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

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

G.C., 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.C., 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, 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.C., S. Kapoor, A. Olshevsky, and A. Zelikovsky, Network Lifetime and Power Assignment in Ad-Hoc Wireless Networks, in ESA 2003.

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

G.C., 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.

G.C. 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.C. 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.C., 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.C.. "Alphabet Independent and Dictionary Scaled Matching," in Journal of Algorithms, 2000. Preliminary version in CPM' 96.

G.C., 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.