Giorgio Lucarelli

Teaching and Research Associate
ENSIMAG, Grenoble INP
LIG, INRIA (Datamove)

Welcome!

I am currently Teaching and Research Associate (Attaché Temporaire d'Enseignement et de Recherche - ATER) at ENSIMAG of Grenoble INP and member of the Data Aware Large Scale Computing (DataMove) team of INRIA and LIG. I obtained my PhD in Theoretical Computer Science in October 2009 from Athens University of Economics and Business, under the supervision of Professor Ioannis Milis. I completed a M.Sc. in Computer Science (July 2005) and my undergraduate studies in Informatics (September 2003) at the same University.

My research interests include: algorithms and complexity, approximation and online algorithms, power-aware scheduling, scheduling in large-scale systems, graph algorithms, exact and parameterized algorithms.

Publications

• M. Demange, B. Escoffier, G. Lucarelli, I. Milis, J. Monnot, V. Th. Paschos and D. De Werra, Weighted edge coloring in Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives, chapter 11, pages 291-318, V. Th. Paschos (editor), Wiley-ISTE, 2008.

• M. Amarís, G. Lucarelli, C. Mommessin and D. Trystram, Generic algorithms for scheduling applications on heterogeneous platforms. Concurrency and Computation: Practice and Experience, accepted. (A preliminary version appeared in Euro-Par 2017)
• S. Albers, E. Bampis, D. Letsios, G. Lucarelli and R. Stotz, Scheduling on power-heterogeneous processors. Information and Computation, 257: 22-33, 2017. (A preliminary version appeared in LATIN 2016)
• N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis and V. Th. Paschos, Exact and superpolynomial approximation algorithms for the densest k-subgraph problem. European Journal of Operational Research, 262: 894-903, 2017. (A preliminary version appeared in WALCOM 2013)
• E. Bampis, A. Kononov, D. Letsios, G. Lucarelli and M. Sviridenko, Energy efficient scheduling and routing via randomized rounding. Journal of Scheduling, 21: 35-51, 2018. (A preliminary version appeared in FSTTCS 2013)
• E. Bampis, D. Letsios and G. Lucarelli, Green scheduling, flows and matchings. Theoretical Computer Science, 579: 126-136, 2015. (A preliminary version appeared in ISAAC 2012)
• S. Talebi, E. Bampis, G. Lucarelli, I. Katib and G. N. Rouskas, On routing and spectrum assignment in rings. IEEE/OSA Journal of Lightwave Technology, 33(1): 151-160, 2015.
• E. Bampis, A. Kononov, D. Letsios, G. Lucarelli and I. Nemparis, From preemptive to non-preemptive speed-scaling scheduling. Discrete Applied Mathematics, 181: 11-20, 2015. (A preliminary version appeared in COCOON 2013)
• S. Talebi, E. Bampis, G. Lucarelli, I. Katib and G. N. Rouskas, Spectrum assigment in optical networks: A multiprocesor scheduling perspective. IEEE/OSA Journal of Optical Communications and Networking, 6: 754-763, 2014. (A preliminary version appeared in ONDM 2014)
• E. Bampis, A. Kononov, G. Lucarelli and I. Milis, Bounded max-colorings of graphs. Journal of Discrete Algorithms, 26: 56-68, 2014. (A preliminary version appeared in ISAAC 2010)
• E. Bampis, D. Letsios, G. Lucarelli, E. Markakis and I. Milis, On multiprocessor temperature-aware scheduling problems. Journal of Scheduling, 16: 529-538, 2013. (A preliminary version appeared in FAW-AAIM 2012)
• G. Ausiello, N. Boria, A. Giannakos, G. Lucarelli and V. Th. Paschos, Online maximum k-coverage. Discrete Applied Mathematics, 160: 1901-1913, 2012. (A preliminary version appeared in FCT 2011)
• G. Lucarelli and I. Milis, Improved approximation algorithms for the Max-Edge Coloring problem. Information Processing Letters, 111: 819-823, 2011. (A preliminary version appeared in TAPAS 2011)
• N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis, V. Th. Paschos and O. Pottié, The max quasi-independent set problem. Journal of Combinatorial Optimization, 23: 94-117, 2012. (A preliminary version appeared in CSR 2010)
• N. Bourgeois, G. Lucarelli, I. Milis and V. Th. Paschos, Approximating the max-edge-coloring problem. Theoretical Computer Science, 411: 3055-3067, 2010. (Parts of this article appeared in WAOA 2008 and IWOCA 2009)
• G. Lucarelli, I. Milis and V. Th. Paschos, On the max-weight edge coloring problem. Journal of Combinatorial Optimization, 20: 429-442, 2010. (A preliminary version appeared in MISTA 2007)
• G. Lucarelli, X. Vassilakos and I. Androutsopoulos, Named entity recognition in Greek texts with an ensemble of Support Vector Machines and active learning. International Journal on Artificial Intelligence Tools, 16(6): 1015-1045, World Scientific, 2007. (A preliminary version appeared in SETN 2006)

• G. Lucarelli, B. Moseley, N. K. Thang, A. Srivastav and D. Trystram, Online non-preemptive scheduling to minimize weighted flow-time on unrelated machines. In 26th Annual European Symposium on Algorithms (ESA 2018), accepted.
• R. Bleuse, K. Dogeas, G. Lucarelli, G. Mounié and D. Trystram, Interference-aware scheduling using geometric constraints. In 24th International European Conference on Parallel and Distributed Computing (Euro-Par 2018), accepted.
• G. Lucarelli, B. Moseley, N. K. Thang, A. Srivastav and D. Trystram, Online non-preemptive scheduling on unrelated machines with rejections. In 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), accepted.
• L. Arantes, E. Bampis, A. Kononov, M. Letsios, G. Lucarelli and P. Sens, Scheduling under uncertainty: A query-based approach. In 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), accepted.
• L. Yala, P. Frangoudis, G. Lucarelli and A. Ksentini, Balancing between cost and availability for CDNaaS resource placement. In IEEE Global Communications Conference (GLOBECOM 2017), IEEE, 2017.
• M. Amarís, G. Lucarelli, C. Mommessin and D. Trystram, Generic algorithms for scheduling applications on hybrid multi-core machines. In 23rd International European Conference on Parallel and Distributed Computing (Euro-Par 2017), volume 10417 of LNCS, pages 220-231. Springer, 2017.
• G. Lucarelli, F. Mendonca and D. Trystram, A new on-line method for scheduling independent tasks. In 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID 2017), pages 140-149, IEEE, 2017.
• G. Lucarelli, N. K. Thang, A. Srivastav and D. Trystram, Online non-preemptive scheduling in a resource augmentation model based on duality. In 24th European Symposium on Algorithms (ESA 2016), volume 57 of LIPIcs, pages 63:1-17, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
• G. Lucarelli, A. Srivastav and D. Trystram, From preemptive to non-preemptive scheduling using rejections. In 22nd International Computing and Combinatorics Conference (COCOON 2016), volume 9797 of LNCS, pages 510-519, Springer, 2016.
• S. Albers, E. Bampis, D. Letsios, G. Lucarelli and R. Stotz, Scheduling on power-heterogeneous processors. In 12th Latin American Theoretical Informatics Symposium (LATIN 2016), volume 9644 of LNCS, pages 41-54, Springer, 2016.
• S. Angelopoulos, G. Lucarelli and N. K. Thang, Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow time problems. In 23rd European Symposium on Algorithms (ESA 2015), volume 9294 of LNCS, pages 35-46, Springer, 2015.
• G. Lucarelli, F. Mendonca, D. Trystram and F. Wagner, Contiguity and locality in backfilling scheduling. In 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID 2015), pages 586-595, IEEE, 2015.
• E. Bampis, D. Letsios and G. Lucarelli, Speed-scaling with no preemptions. In 25th International Symposium on Algorithms and Computation (ISAAC 2014), volume 8889 of LNCS, pages 259-269, Springer, 2014.
• E. Bampis, V. Chau, D. Letsios, G. Lucarelli, I. Milis and G. Zois, Energy efficient scheduling of MapReduce jobs. In 20th International European Conference on Parallel Processing (Euro-Par 2014), volume 8632 of LNCS, pages 198-209, Springer, 2014.
• E. Bampis, D. Letsios and G. Lucarelli, A note on multiprocessor speed scaling with precedence constraints. In 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2014), pages 138-142, ACM, 2014.
• S. Talebi, E. Bampis, G. Lucarelli, I. Katib and G. N. Rouskas, The spectrum assigment (SA) problem in optical networks: A multiprocesor scheduling perspective. In 18th Conference on Optical Network Design and Modeling (ONDM 2014), pages 55-60, IEEE, 2014.
• E. Bampis, A. Kononov, D. Letsios, G. Lucarelli and M. Sviridenko, Energy efficient scheduling and routing via randomized rounding. In 33rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013), volume 24 of LIPIcs, pages 449-460, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013.
• E. Bampis, V. Chau, D. Letsios, G. Lucarelli and I. Milis, Energy minimization via a primal-dual algorithm for a convex program. In 12th International Symposium on Experimental Algorithms (SEA 2013), volume 7933 of LNCS, pages 366-377, Springer, 2013.
• E. Bampis, A. Kononov, D. Letsios, G. Lucarelli and I. Nemparis, From preemptive to non-preemptive speed-scaling scheduling. In 19th International Computing and Combinatorics Conference (COCOON 2013), volume 7936 of LNCS, pages 134-146, Springer, 2013.
• N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis and V. Th. Paschos, Exact and approximation algorithms for densest k-subgraph. In 7th Workshop on Algorithms and Computation (WALCOM 2013), volume 7748 of LNCS, pages 114-125, Springer, 2013.
• E. Bampis, D. Letsios and G. Lucarelli, Green scheduling, flows and matchings. In 23rd International Symposium on Algorithms and Computation (ISAAC 2012), volume 7676 of LNCS, pages 106-115, Springer, 2012.
• E. Bampis, D. Letsios, G. Lucarelli, E. Markakis and I. Milis, On multiprocessor temperature-aware scheduling problems. In Joint International Conference: 6th International Frontiers in Algorithmics Workshop and 8th International Conference on Algorithmic Aspects of Information and Management (FAW-AAIM 2012), volume 7285 of LNCS, pages 149-160, Springer, 2012.
• G. Ausiello, N. Boria, A. Giannakos, G. Lucarelli and V. Th. Paschos, Online maximum k-coverage. In 18th International Symposium on Fundamentals of Computation Theory (FCT 2011), volume 6914 of LNCS, pages 181-192, Springer, 2011.
• G. Lucarelli and I. Milis, Improved approximation algorithms for the Max-Edge Coloring problem. In 1st International ICST Conference on Theory and Practice of Algorithms in Computer Systems (TAPAS 2011), volume 6595 of LNCS, pages 206-216, Springer, 2011.
• E. Bampis, A. Kononov, G. Lucarelli and I. Milis, Bounded max-colorings of graphs. In 21st International Symposium on Algorithms and Computation (ISAAC 2010), volume 6506 of LNCS, pages 353-365, Springer, 2010.
• N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis, V. Th. Paschos and O. Pottié, The max quasi-independent set problem. In 5th International Computer Science Symposium in Russia (CSR 2010), volume 6072 of LNCS, pages 60-71, Springer, 2010.
• N. Bourgeois, G. Lucarelli, I. Milis and V. Th. Paschos, Approximating the max edge-coloring problem. In 20th International Workshop on Combinatorial Algorithms (IWOCA 2009), volume 5874 of LNCS, pages 83-94, Springer, 2009.
• G. Lucarelli, I. Milis and V. Th. Paschos, On the maximum edge coloring problem. In 6th Workshop on Approximation and Online Algorithms (WAOA 2008), volume 5426 of LNCS, pages 279-292, Springer, 2009.
• G. Lucarelli, I. Milis and V. Th. Paschos, On a generalized graph coloring/batch scheduling problem. In 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA 2007), pages 353-360, 2007.

• R. Bleuse, G. Lucarelli, G. Mounié and D. Trystram, Interference-aware scheduling with 2D-torus as a case study. In 30th Conference of the European Chapter on Combinatorial Optimization (ECCO 2017), 2017.
• G. Lucarelli, N. K. Thang, A. Srivastav and D. Trystram, Online min-sum flow scheduling with rejections. In 13th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2017), 2017.
• G. Lucarelli, D. Trystram and F. Wagner, A generic approach for heterogeneous scheduling. In 28th Conference of the European Chapter on Combinatorial Optimization (ECCO 2015), 2015.
• S. Angelopoulos, G. Lucarelli and N. K. Thang, Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems. In 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2015), 2015.
• E. Bampis, A. Kononov, D. Letsios, G. Lucarelli and M. Sviridenko, Energy efficient multiprocessor scheduling via configuration LP. In 11th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2013), 2013.
• E. Bampis, G. Lucarelli and I. Milis, On a batch scheduling problem with compatibility and cardinality constraints. In 8th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2007), 2007.

• G. Lucarelli and I. Androutsopoulos, A Greek named-entity recognizer that uses Support Vector Machines and active learning. In 4th Hellenic Conference on Artificial Intelligence (SETN 2006), volume 3955 of LNAI, pages 203-213, Springer, 2006.

• C. Mommessin and G. Lucarelli, Low complexity on-line scheduling algorithm for hybrid multi-core machines. In 19ème Conférence de la Société Française de Recherche Opérationnelle et Aide à la Décision (ROADEF 2018), 2018.
• A. Srivastav, G. Lucarelli, N. K. Thang and D. Trystram, Online non-preemptive scheduling in a resource augmentation model based on duality. In 18ème Conférence de la Société Française de Recherche Opérationnelle et Aide à la Décision (ROADEF 2017), 2017.
• S. Albers, E. Bampis, D. Letsios, G. Lucarelli and R. Stotz, Scheduling on power-heterogeneous processors. In 17ème Conférence de la Société Française de Recherche Opérationnelle et Aide à la Décision (ROADEF 2016), 2016.
• E. Bampis, D. Letsios and G. Lucarelli, Multiprocessor speed scaling with precedence constraints. In 16ème Conférence de la Société Française de Recherche Opérationnelle et Aide à la Décision (ROADEF 2015), 2015.
• E. Bampis, A. Kononov, D. Letsios, G. Lucarelli and M. Sviridenko, Energy efficient scheduling and routing via randomized rounding. In 15ème Conférence de la Société Française de Recherche Opérationnelle et Aide à la Décision (ROADEF 2014), 2014.
• E. Bampis, D. Letsios and G. Lucarelli, Ordonnancements, flots et couplages verts. In 14ème Conférence de la Société Française de Recherche Opérationnelle et Aide à la Décision (ROADEF 2013), 2013.

• G. Lucarelli, Scheduling in computer and communication systems and generalized graph coloring problems. Ph.D. thesis, M.Sc. in Computer Science, Athens University of Economics and Business, Greece, 2009.
• G. Lucarelli, Named entity recognition and categorization in greek texts. Master thesis, M.Sc. in Computer Science, Athens University of Economics and Business, Greece, 2005. (in greek)