Scheduling a Pipelined Operator Graph of Bounded Treewidth


Article Preview

Pipelined operator graph (POG) scheduling is an important problem in the area of parallel query optimization. A POG is a graph with vertices representing query operators that can run in parallel and edges representing communication between adjacent operators. The problem is to assign operators to processors so as to minimize the maximum processor load. We present a 2-approximation algorithm for the case where the operator graph has bounded treewidth.



Key Engineering Materials (Volumes 467-469)

Edited by:

Dehuai Zeng




S. G. Li and X. Xin, "Scheduling a Pipelined Operator Graph of Bounded Treewidth", Key Engineering Materials, Vols. 467-469, pp. 1102-1107, 2011

Online since:

February 2011




[1] W. Hasan and R. Motwani: Optimization algorithms for exploiting the parallelism, communication tradeoff in pipelined parallelism. In Proceedings of the 20th International Conference on Very Large Data Bases, Santiago, Chile, September 1994, p.36.

[2] W. Hasan: Optimization of SQL queries for parallel machines. Ph.D. Thesis, Department of Computer Science, Stanford University, December (1996).

[3] Petra Schuurman and Gerhard J. Woeginger: Scheduling a pipelined operator graph. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, San Francisco, California, United States, January 2000, p.207–212.

[4] M. R. Garey and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, first edition, W. H. Freeman and Company, New York, (1979).

[5] C. H. Papadimitriou and K. Steiglitz: Combinatorial optimization: algorithms and complexity. New Jersey: Prentice-Hall, (1982).

[6] C. Chekuri, W. Hasan, and R. Motwani: Scheduling problems in parallel query optimization. In Proceedings of the 14th ACM SIGACT-SIGMOD-SIGART Symposium on Principle of Database Systems, San Jose, CA, May 1995, p.255–265.


[7] C. Chekuri: Approximation algorithms for scheduling problems. Ph.D. Thesis, Department of Computer Science, Stanford University, (1998).

[8] Hans L. Bodlaender and Arie M. C. A. Koster: Combinatorial Optimization on Graphs of Bounded Treewidth. The Computer Journal, vol. 51, no. 3, p.255–269, (2008).

[9] J. Kleinberg and E. Tardos: Algorithm Design. Boston: Addison-Wesley, (2005).

[10] Zoya Svitkina and Eva Tardos: Min-max multiway cut. In Lecture Notes in Computer Science 3122: Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Heidelberg: Springer-Verlag, August 2004, p.207.


[11] R. L. Graham: Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, vol. 17, no. 2, p.416–429, (1969).