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 2013, Gruia is teaching CS 535 - Analysis of Algorithm.

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

Relay placement for two-connectivity, submitted journal version. Preliminary version in IFIP Networking 2012.

G.C. and Minming Li, Register Loading via Linear Programming , submitted journal version. Preliminary version in WADS 2011.

Min-Power Strong Connectivity, in APPROX 2010. The approximation ratio of the same algorithm for the general case is improved to 1.85, and simplified in Approximate Min-Power Strong Connectivity , revised journal submssion. The running time was improved (and experimental results added) in a INFOCOM 2012 paper.

G.C., Cristina G. Fernandes, Hemanshu Kaul, and A. Zelikovsky, Maximum Series-Parallel Subgraph , submitted journal full version; in Algorithmica. Preliminary version in WG 2009

G.C. and Sutep Tongngam, Interference-Aware Broadcast Scheduling in Wireless Networks, , full version. Preliminary version in in 4th International Conference on Mobile Ad-hoc and Sensor Networks (MSN'08) .

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 journal 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, in Random Structures and Algorithms, 2009.

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., and A. Zelikovsky, The Polymatroid Steiner Problems, in Journal of Combinatorial Optimization, 2005. Preliminary results in ISAAC 2004. A generalization of Group Steiner Tree with potential applications besides sensor networks, which is why it selected to appear here, even though the algorithm is a straightforward adaptation of the one of Chekuri, Even, and Korsatz.

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. Please send email for a journal version.

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.