Publications

 

Books

Afrati, F., "Introduction to Information Theory" (in greek), Symmetria,  Athens, 1985.

Afrati, F., Papageorgiou, G., "Algorithms: Design and Analysis of Computational Complexity" (in greek),  Symmetria,  Athens, 1993, second edition with 25% new material, 2005.

 

Chapters in books

On Approximation Algorithms for Data Mining Applications,  Foto Afrati. In the volume "Efficient Approximation and Online Algorithms" of the series Lecture Notes in Computer Science (Springer Verlag) no 3484, Eds: E. Bampis, K. Jansen, C. Kenyon, 2006.

Papers in Refereed Journals

21. Foto N. Afrati, Ioannis Milis, Designing PTASs for MIN-SUM scheduling problems, to appear in Discrete Applied Mathematics.

20. Foto N. Afrati, Timos Aslanidis, Evripidis Bampis, Ioannis Milis: Scheduling in Switching Networks with Set-Up Delays. J. Comb. Optim. 9(1): 49-57 (2005)

19. Foto N. Afrati, Stavros S. Cosmadakis, Eugénie Foustoucos: Datalog programs and their persistency numbers. ACM Trans. Comput. Log. 6(3): 481-518 (2005)

18. Foto N. Afrati, Evripidis Bampis, Lucian Finta, Ioannis Milis: Scheduling trees with large communication delays on two identical processors. J. Scheduling 8(2): 179-190 (2005)

17. Foto N. Afrati, Hans Leiß, Michel de Rougemont: Definability and Compression. Fundam. Inform. 56(1-2): 155-180 (2003)

16. Irène Guessarian, Eugénie Foustoucos, Theodore Andronikos, Foto N. Afrati: On temporal logic versus datalog. Theor. Comput. Sci. 1(303): 103-133 (2003)

15. Foto N. Afrati, Manolis Gergatsoulis, Francesca Toni: Linearisability on datalog programs. Theor. Comput. Sci. 308(1-3): 199-226 (2003)

14. Foto N. Afrati, Irène Guessarian, Michel de Rougemont: The expressiveness of DAC. Theor. Comput. Sci. 286(1): 3-32 (2002)

13. F. Afrati, E. Bampis, C. Kenyon and I. Milis, A PTAS for the average weighted completion time problem on unrelated   machines, Journal of Scheduling  3 (2000)  323-332.

12. Afrati,F., "Bounded Arity Datalog (<>) Queries on Graphs"  special issue of Journal of Computer and Systems Sciences, vol 55 1997 on ACM Conference 'Principles of Database Systems'.

11. Afrati, F., Cosmadakis, S.,Yannakakis, M., "Datalog vs. Polynomial Time", Journal of Computer and Systems Sciences (special issue on ACM Conference 'Principles of Database Systems'), October 1995.

10. Afrati,F., "A Polynomial Algorithm for Hamiltonian Grids". RAIRO Theoretical Informatics and Applications, Vol 28, no 6, 1994, pp 567-582.

9. Afrati, F., Stafylopatis, A., "Performance Considerations on a Random Graph Model for Parallel processing", RAIRO Theoretical Informatics and Applications, vol. 27, no. 4, 1993, pp 367-388.

8. Paschos, P., Anagnostou, M., Afrati, F., "Deterministic Access Protocols for Packet radio Networks", International Journal of Digital and Analog Communication Systems, Vol. 6 1993, pp. 151-160.

7. Paschos, P., Anagnostou, M., Afrati, F., "Deterministic Access Protocols for Packet radio Networks", International Journal of Digital and Analog Communication Systems, Vol. 6 1993, pp. 151-160.

6. Afrati, F., "The Parallel Complexity of Single Rule Logic Programs" . Discrtete Applied Mathematics (special issue) 40 (1992) pp 107-126.

5. Afrati, F., Papadimitriou, C.H., "The Parallel Complexity of Simple Logic Programs", J.ACM, Vol. 90 No 4 September 1993, pp. 891-916.

4. Afrati, F., Papadimitriou, C.H., Papageorgiou, G., Roussou, A., Sagiv, Y., Ullman, J.D., "On the Convergence of Query Evaluation", Journal of Computer and Systems Sciences, Vol. 38 No 2, April 1989 (special issue), pp. 341-359.

3. Afrati, F., Papadimitriou, C.H., Papageorgiou, G. "The Synthesis of Communication Protocols", Algorithmica Vol 3, 1988 (special issue on distributed computing), pp. 451-472.

2. Afrati, F., Cosmadakis, S., Papadimitriou, C.H., Papageorgiou, G., Papakonsta ntinou "The Complexity of the Travelling Repairman Problem", RAIROTheoretical Informatics and Applications, Vol.20, No.1, 1986, pp.79-87.

1. Afrati, F., Papadimitriou, C.H., Papageorgiou, G., "The Complexity of Cubical Graphs" Information and Control Vol.66, No.1-2, July-August 1985 pp. 53-60.
 

Papers in Conference Proceedings

51. Foto N. Afrati, Paraskevas V. Lekeas, Chen Li: Answering aggregation queries on hierarchical web sites using adaptive sampling. CIKM 2005: 237-238

50. Foto N. Afrati, Rada Chirkova, Shalu Gupta, Charles Loftis: Designing and Using Views to Improve Performance of Aggregate Queries (Extended Abstract). DASFAA 2005: 548-554

49. Foto N. Afrati, Gautam Das, Aristides Gionis, Heikki Mannila, Taneli Mielikäinen, Panayiotis Tsaparas: Mining Chains of Relations. ICDM 2005: 553-556

48. Foto N. Afrati, Rada Chirkova: Selecting and Using Views to Compute Aggregate Queries (Extended Abstract). ICDT 2005: 383-397

47. Foto N. Afrati, Rada Chirkova, Manolis Gergatsoulis, Vassia Pavlaki: Designing Views to Efficiently Answer Real SQL Queries. SARA 2005: 332-346

46. Foto N. Afrati, Chen Li, Prasenjit Mitra: On Containment of Conjunctive Queries with Arithmetic Comparisons. EDBT 2004: 459-476, 2004

45.  Foto N. Afrati, Aristides Gionis, Heikki Mannila: Approximating a collection of frequent sets. KDD 2004: 12-19

44 .  Foto N. Afrati, Theodore Andronikos, Vassia Pavlaki, E. Foustoukos, Irène Guessarian: From CTL to Datalog. PCK50 2003: 72-85

43. Foto N. Afrati, Chen Li, Prasenjit Mitra: Answering Queries Using Views with Arithmetic Comparisons. PODS 2002: 209-220

42.  F. Afrati, Τ. Aslanidis, E. Bampis and  I. Milis,  Scheduling  in switching  networks with set-up delays, In Proc. 4èmes Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (ALGOTEL'2002). 

41. Agis Papantoniou, Ezz Hattab, Foto N. Afrati, Eleftherios Kayafas, Vassilis Loumos: Change Management, a Critical Success Factor for e-Government. DEXA Workshop 2001: 402-406

40. F. Afrati and  I.  Milis,  Designing PTASs for MIN-SUM scheduling problems, In Proc. 13th International Symposium Fundamentals of Computation Theory (FCT'01), Invited paper in the Workshop on Efficient Algorithms (WEA'01), Lecture Notes in Computer Science (Springer Verlag)  LNCS-2138 (2001)  432-444.

39. Foto N. Afrati, Chen Li, Jeffrey D. Ullman: Generating Efficient Plans for Queries Using Views. SIGMOD Conference 2001

38. F. Afrati, E. Bampis, L. Finta and  I. Milis,  Scheduling trees with large communication delays on two identical processors, In Proc.  6th International Euro-Par Conference (EURO-PAR'00),   Lecture Notes in Computer Science (Springer Verlag) LNCS-1900 (2000)   288-295.

37. Foto N. Afrati, Evripidis Bampis, Aleksei V. Fishkin, Klaus Jansen, Claire Kenyon: Scheduling to Minimize the Average Completion Time of Dedicated Tasks. FSTTCS 2000: 454-464

36. Foto N. Afrati, Hans Leiß, Michel de Rougemont: Definability and Compression. LICS 2000: 63-73

35 . F. Afrati, E. Bampis, C. Kenyon and I. Milis, Scheduling on a constant number of processors, In Proc. 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’99), Lecture Notes in Computer Science (Springer Verlag) LNCS-1671 (1999) 281-287.

34. F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne,  M. Skutella, C. Stein and M. Sviridenko, Approximation schemes for  minimizing  average weighted completion time with release dates,  Ιn Proc. 40th  IEEE Symposium on Foundations of Computer Science (FOCS’99) (1999) 32-43.

33. Foto N. Afrati, Manolis Gergatsoulis, Theodoros G. Kavalieros: Answering Queries Using Materialized Views with Disjunctions. ICDT 1999: 435-452

32 .  Foto N. Afrati, I. Karali, Theodoros Mitakos: On Inheritance in Object Oriented Datalog. IADT 1998: 280-289

31. Foto N. Afrati, Theodore Andronikos, Theodore G. Kavalieros: On the Expressiveness of Query Languages with Linear Constraints; Capturing Desirable Spatial Properties. CDB 1997: 105-115

30. Foto N. Afrati, Francesca Toni: On the Relationsship Between Chain Queries and Linear Datalog Programs. DDLP 1997:

29. Foto N. Afrati, Irène Guessarian, Michel de Rougemont: The Expressiveness of Datalog Circuits (DAC). MFCS 1997: 119-128

28 .  Foto N. Afrati, Manolis Gergatsoulis, Maria Katzouraki: On Transformations into Linear Database Logic Programs. Ershov Memorial Conference 1996: 433-444

27. Afrati, F., Kavalieros, Th., Theodoratos, D., "On the Complexity of Updating Knowledge Bases", Proceedings of Conference of Greek CS Society, Athens, Dec. 1995.

26. Afrati,F., Andronikos,Th., Kavalieros,Th., "Expressiveness of Constraint Query Languages" Proceedings of 1st workshop on Constraint Databases , Springer Verlag Lecture Notes in CS, 1995.

25. Afrati,F., Andronikos,Th., Kavalieros,Th., "On the Expressiveness of Query Languages with Linear Constraints: Considerations on Spatial Data" Proceedings of 2nd workshop on Constraint Databases, Springer Verlag Lecture Notes in CS, 1995.

24. Afrati,F., Cosmadakis,S., Grumbach,S., Kuper,G., "Linear vs. Polynomial Constraints in Database Query Languages", 2nd Workshop on Principles and Practice of Constraint Programming, 1994.

23. Afrati,F., "Bounded Arity Datalog (<>) Queries on Graphs", Proceeding s of the 13th ACM PODS, Symposium on the Principles of Database Systems, 1994.

22. Afrati,F., Cosmadakis,S.,Yannakakis,M., "Datalog vs. Polynomial Time", Proceedings of the 10th ACM PODS, Symposium on the Principles of Database Systems, 1991, pp.13-25; (the final version appears above as a refereed journal entry).

21. Afrati,F., "Finding Strongly Connected Components in Series Parallel Graphs". Proceedings TENCON'91, New Dehli, India,1991.

20. Afrati,F., Coutras,C., "A Hypertext Model Supporting Query Mechanisms&qu ot;, Proceedings of the European Conference on Hypertext 1990, published in volume Hypertext: Concepts, systems and applications by Cambridge University Press.

19. Afrati,F., Cosmadakis,S., "Expressiveness of Restricted Recursive Queries", Proceedings of the 21st ACM STOC, Symposium on Theory of Computing, May 1989, pp. 113-126.

18. Afrati,F., Stafylopatis,A., "Performance Considerations on a Random Graph Model for Parallel Processing". Proceedings of IMACS Conference, Paris 1988.

17. Afrati,F, Papadimitriou,C.H., Papageorgiou,G., "Scheduling Dags to Minimize Time and Communication", Proceedings of the Aegian Workshop on Computing (AWOC), June 1988.

16. Afrati,F., Papadimitriou,C.H., "The Parallel Complexity of Simple Chain Queries", Proceedings of the 6th ACM PODS, Symposium on the Principles of Database Systems, March 1987 pp. 210-213; (the final version appears above as a refereed journal entry).

15. Afrati,F., Papadimitriou,C.H., Papageorgiou,G., Roussou,A., Sagiv,Y.,Ullman,J .D., "Convergence of Sideways Query Evaluation", Proceedings of the 5th ACM PODS, Symposium on the Principles of Database Systems,March 1986 pp. 24-30; (the final version appears above as a refereed journal entry).

14. Afrati,F., Papadimitriou,C.H., Papageorgiou,G. "The Synthesis of Communication Protocols", Proceedings of the 5th ACM PODC. Symposium on the Principles of Distributed Computing, August 1986;(the final version (appears above as a refereed journal entry).

13. Afrati,F., Anagnostou,M., Protonotarios,E.N., "Performance Evaluation of Hybrid ARQ Protocols", Proceedings of IEEE Symposium on Information Theory, June 1985.

12. Afrati,F., Dendrinos,M., "Symmetry and Cyclicity Properties of some Low Complexity Codes", Proceedings of IEEE Symposium on Information Theory, June 1985.

11. Anagnostou,M., Afrati,F., "On the Complexity and Accuracy of Algorithms used for the Performance Evaluation of ARQ Protocols", Proceedings of the IEEE International Conference MELECON, 1985.

10. Afrati,F., Papaspirou,V., "Optimal Extension of a Linear Code", Proceedings of the IEEE International Conference MELECON, 1985.

9. Afrati,F., Papadimitriou,C.H., Papageorgiou,G., "The Complexity of Cubical Graphs", Proceedings of the 11th ICALP, International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science appears above as a refereed journal entry),1984.

8. Afrati,F., Dendrinos.M., "Considerations on Low Complexity Codes Concerning Symmetry and Cyclicity", Proceedings DIGITECH, 1984.

7. Afrati,F., Ballas,D., "Analysis of Error Correcting Codes for the Binary Symmetric Channel", Proceedings MECO 1983.

6. Afrati,F., Anagnostou,M., Mikroudis,N., "A Hybrid ARQ Scheme using Convolutional Codes", Proceedings MECO 1983.

5. Afrati,F., Anagnostou,M., Mikroudis,N.,"A Hybrid Scheme for the Improvement of the ARQ Protocols", Proceedings of the IEEE International Conference MELECON, 1983.

4. Afrati,F., "A Random Search Algorithm for the Construction of Ternary Linear Block Codes", Proceedings of the IEEE International Conference MELECON, 1983.

3. Afrati,F., "A Graph-Theoretic Approach to the Binary Linear Block Code Construction", Proceedings of the IEEE International Symposium on Information Theory, 1982.

2. Afrati,F., " A Branch-and-Bound Method for the Construction of Binary Linear Block Codes", Proceedings of the IEEE International Conference MELECON, 1981.

1. Afrati,F., Constantinides,A.G., " The Use of Graph Theory in Binary Block Code Construction", Proceedings of the IEEE International Conference on Digital Signal Processing, 1978.