Approximation Algorithms for Product Query Optimization
Macéo Ottavy, Avijeet Ghosh, Pascal Koiran, Alantha Newman, François Schwarzentruber, Blair D. Sullivan, Stéphan Thomassé
原文摘要
We study database query optimization for Cartesian products. This problem is equivalent to finding an optimal plan for multiplying non-negative integers. We call this problem multiplication ordering. We show that the problem has an FPTAS when the cost of a plan is the sum of all intermediate products; both in the case when the overall final product is counted and when it is not. We show that using the optimal solution to the well-known product partition problem does not always lead to an optimal plan, but we establish connections between the product partition and multiplication ordering problems. Finally, we prove that multiplication ordering is in PTIME (resp. \NP-complete) when integers are powers of a same base where the exponents are written in unary (resp. in binary).
cs.DS