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. In Fall 2015, Gruia was on sabbatical at University of Bonn as part of Hausdorff Trimester Program in Combinatorial Optimization. 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 2022, Gruia is teaching CS 530 - Theory of Computation.

Selected publications, starting with the most recent. Please send email for other papers or other versions of the posted papers.

G.C and Xiaolang Wang, Combination algorithms for Steiner Tree variants, version accepted by Algorithmica, 2022.

G. C. and Kai Wang, A new LP rounding algorithm for the active time problem, version accepted at Journal of Scheduling, 2021.

I. Albuquerque Raymundo Da Silva, G. C,, and N. De Graaf, Faster Compression of Patterns to Rectangle Rule Lists, as submitted to Theoretical Computer Science (final version published in 2020).

G.C, G. Kortsarz, and Z. Nutov, Improved approximation algorithms for Minimum Power Covering problems", as submitted to Workshop on Approximation and Online Algorithms (WAOA 2018).

G.C and Xiaolang Wang, Client Assignment Problems for Latency Minimization , version accepted by Journal of Combinatorial Optimization, 2018.

T-joins in Strongly Connected Hypergraphs , version accepted by Discrete Mathematics, Algorithms and Applications, 2017. Partially based on the same paper from APPROX 2010. as two publications mentioned below.

G.C., Chenchen Fu, Minming Li, Kai Wang, and Chun Jason Xue Energy-Aware Real-Time Task Scheduling on Local and Shared Memory Systems , journal submission. Preliminary version accepted in IEEE RTSS 2016.

G.C., Benjamin Grimmer, Satyajayant Misra, Sutep Tongngam, Guoliang Xue, and Weiyi Zhang. Improved Approximation Algorithms for Single-Tiered Relay Placement , version accepted by Journal of Combinatorial Optimization, 2014. Partially based on paper with Sutep Tongngam paper in WASA 2008.

G.C. and Kan Qiao, Minimum Power Broadcast: fast variants of greedy approximations, as submitted to IEEE MASS 2014.

Relay placement for two-connectivity, version accepted by Discrete Optimization, 2014. Preliminary version in IFIP Networking 2012.

G.C. and Minming Li, Register Loading via Linear Programming , version that corrects some minor errors that made it into Algorithmica. 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 submission (and further revised, final version in SIAM J. Discrete Math). The running time for the general case was improved (and experimental results added) in a INFOCOM 2012 paper. A separate journal submission has the 1.61. approximation for the two-power-levels case.

G.C., Cristina G. Fernandes, Hemanshu Kaul, and A. Zelikovsky, Maximum Series-Parallel Subgraph , journal full version; (see Algorithmica for the final version). Preliminary version in WG 2009

G.C. and Sutep Tongngam, Interference-Aware Broadcast Scheduling in Wireless Networks, , journal full version; (see Ad Hoc Networks, 2011 for the published 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), 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). The combined result is in SIAM J. Computing.

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 (minor corrections done in 2013 and 2015) , 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 is 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.