betaFeedback

WorksComputer Science

Approximation Algorithms for Product Query Optimization

Abstract

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).

Introduction

In database systems, query optimization consists in choosing the right actions to perform for computing the result of a query. For instance, should we compute the plan ((a⋈b)⋈c)((a \bowtie b) \bowtie c) or the plan ((b⋈c)⋈a)((b \bowtie c) \bowtie a), where ⋈\bowtie is the join operation for answering to the following SQL query?

SELECT a.*
FROM a,
     b,
     c
WHERE a.a_id = b.a_id
  AND b.b_id = c.b_id

In a seminal paper, [6] proved that computing an optimal plan is NP-complete; their plans are left-deep join trees and they model the cost by means of a selectivity factor between two relations RiR_i and RjR_j giving an estimation on the proportion of the size of Ri⋈RjR_i \bowtie R_j compared to Ri×RjR_i \times R_j. They ask to compute a plan that only uses the join operations explicitly given in the query. In [4], NP-hardness is proven for a more general notion of cost satisfying so-called ASI (adjacent sequence interchange) property and allowing for computing any Cartesian products in the plan. In [10], it was proven that the problem is also NP-complete when plans are arbitrary trees (bushy trees) and only Cartesian products are considered. They consider the output cost that is the sum of the sizes (i.e., number of tuples) of all intermediate products computed during the plan.

Example 1. Consider relations R1R_1, R2R_2, R3R_3, R4R_4 of respective sizes 2, 2, 5, 10. The plan (R1×R2)×(R3×R4)(R_1 \times R_2) \times(R_3 \times R_4) can be represented by the following tree on which we have written the intermediate product sizes:

Multiplication plan with relation sizes

Figure 1.

The output cost of this plan is 5+2+10+2+10+20+200=2495+2+10+2+10+20+200 = 249. As the final product size is always the same, we may also exclude it in the cost. The output cost without the root is 5+2+10+2+10+20=495+2+10+2+10+20 = 49.

The cost of a plan τ\tau including the root is denoted by cost⁡^(τ)\widehat{\operatorname{cost}}(\tau) while its cost without the root is denoted by cost⁡(τ)\operatorname{cost}(\tau). Although this query optimization problem is called cross product optimization in [10], we change its name to MultOrd to emphasize the fact that the input instance only contains the sizes of the relations. In particular the optimization process is agnostic about the very content of the relations. Thus, MultOrd corresponds to the natural problem of computing Cartesian products (i.e., joins without any conditions; no WHERE clauses in SQL) and where only the sizes of the relations are used to determine an optimal plan.

Observe that the NP-hardness proven in [10] relies on a reduction from Exact Covering With 3-Sets, in which elements of sets are encoded by relations where sizes are prime numbers. This setting is rather rare and one may wonder whether the problem is really so difficult in general. Note that the reduction in [10] involves the first prime numbers making the resulting instance of MultOrd in poly-size even if numbers are given in unary. Said differently, MultOrd is NP-hard when numbers are given in unary. As the numbers represent sizes of relations written explicitly, it is practically relevant to consider the numbers written unary. In the current paper, we consider the numbers to be written binary making our approximation results stronger.

Our Contribution

We show that MultOrd, although NP-hard, is easy to approximate. This contrasts with the inaproximability of query optimization in general [3].

  • We show, see Theorem 2, that MultOrd has an FPTAS (fully polynomial-time approximation scheme), meaning that we can find a (1+ϵ)(1+\epsilon)-approximate plan, in polytime in the size of the input and in 1/ϵ1/\epsilon. We assume that the size of the relation sizes are given in binary.

  • In the output cost, we always count the product of the sizes of all relations in the root. As this final product is present in all plans, we also consider the notion of cost in which we ignore the root (i.e., we do not count the global product of all the inputs). In the previous example, the cost is then 5+2+10+2+10+20=495+2+10+2+10+20 = 49. Theorem 3 shows that MultOrd with the cost ignoring the global product at the root also has an FPTAS.

  • We also compare multiplication ordering to product partition. First we show that an approximate solution for ProdPart helps to find an approximate solution for MultOrd (Lemma 10). However, applying product partition is not always part of the optimal plan, and we exhibit an example where applying a product partition at the root does not lead to an optimal plan for multiplication ordering (see Proposition 8).

  • Interestingly, we also focus on MultOrd when the sizes have a form of regularity (in contrast to being prime numbers as in the NP-hardness proof [6]). We prove that when the sizes are all powers of the same base (e.g., 454^5, 4124^{12}, 4124^{12}, 44594^{459}, then MultOrd is in PTIME (see Theorem 4). However the problem becomes NP-complete when the exponents are written in binary (see Theorem 5).

Paper outline. In Section 2, we briefly discuss the related work both in database theory and in algorithms. In Section 3 we formally define MultOrd. Then, in Section 4, we explain how to exactly solve MultOrd with a naïve algorithm; this is important because it gives subroutines for the approximation algorithms. In Section 5, we give two preprocessing rules allowing us to only consider input numbers greater or equal to 2. In Section 6, we introduce two strategies: Pacman-plan and Half-plan and prove upper and lower bounds on the cost of any plan. In § 7, we show that MultOrd has a FPTAS both for cost and cost. In § 8, we highlight strong links between the famous ProductPartition problem and MultOrd. In § 9, we then tackle the restriction on the input to powers. In § 10, we discuss future work.

Related work

The MultOrd problem has direct connections to problems in database query optimization as well as to ordering problems studied in other areas.

Database theory

Ordering of joins in database is a vast topic, see Table p. 45 in [8]. The problem is NP-complete in general, see the seminal paper [6] in which they prove that it is NP-hardness to get an optimal left-deep join tree where we also give a selectivity factor for each pair of relations that can be joined. Later, in [4], they proved that this problem is also NP-complete if we allow for Cartesian products, meaning that all pair of relations are joinable. In [3], it is shown that query optimization in general cannot be approximated.

The case when all selectivity factors are equal to 1 corresponds to computing Cartesian products. In particular, searching for an optimal (with the output cost) bushy 1 tree for computing a Cartesian product is NP-hard [10]. This problem is exactly MultOrd. Observe that if we know the left-right order of the leaves of the tree, we can find OPT by dynamic programming. However nothing was known concerning approximation.

Ordering in the context of other multiplication problems

In algorithms, many problems involve ordering operations on a certain number of objects from some class. Sometimes the outcome is always the same (e.g., multiplying integers or matrices), but intermediate objects of vastly different sizes can be created, depending on the ordering of operations. Thus, an important goal in this context is to try to order these operations (e.g., multiplications) so as to reduce the sizes of the intermediate objects.

The most famous problem of this kind is finding the optimal ordering for the computation of a products of matrices, M1⋅M2⋯MnM_1 \cdot M_2 \cdots M_n. This task can be done in O(n3)O(n^3) and is a standard textbook exercise in dynamic programming [5]. Dynamic programming can be applied here because the left-right order of the matrices is fixed; only the optimal bushy tree has to be computed.

Many multiplication ordering problems are NP-hard. One problem which seems close is the Vertex-EliminationProblem [2] consisting of iteratively eliminating internal nodes in a directed graphs, namely adding edges from all in-neighbors to all out-neighbors and deleting the node. The cost to minimize is the sum of all in-degree times out-degree at the moment of the elimination of the node. Another related work can be found in [AKC†21].

Definition of the MultOrd problem

An instance of MultOrd is a multiset of positive integers S={si}i=1nS = \{s_i\}_{i=1}^{n}. A plan τ\tau for computing s1×⋯×sns_1 \times\cdots\times s_n is a binary tree whose leaves are s1,…,sns_1,\ldots,s_n. A plan τ\tau can be seen as a syntactic tree of an expression for computing s1×⋯×sns_1 \times\cdots\times s_n with parenthesis. For the rest of the paper, unless stated otherwise, nn denotes the number of integers in the instance. We sometimes refer to these input integers {s1,…,sn}\{s_1,\ldots,s_n\} as elements.

Example 2. A plan for 2×2×5×102 \times2 \times5 \times10 could be (5×2)×(10×2)(5 \times2) \times(10 \times2) that corresponds to the syntactic

tree

        ×
      /   \
     ×     ×
    / \   / \
   5   2 10  2

For a plan τ\tau, we denote by S(τ)S(\tau) the multiset composed of the labels of the leaves of τ\tau. The evaluation of a plan τ\tau is ∣τ∣=∏s∈S(τ)s|\tau| = \prod_{s\in S(\tau)} s, that is the product of all leaves of τ\tau. The cost of a plan τ\tau (denoted cost⁡(τ)\operatorname{cost}(\tau)) is the sum of all the intermediate products at internal nodes of τ\tau (we exclude the root and include the leaves). The cost that also includes the root is denoted by cost⁡^(τ)\widehat{\operatorname{cost}}(\tau). The formal definitions are as follows.

Definition 1 (cost including the root). For a leaf ss, cost⁡^(s)=s\widehat{\operatorname{cost}}(s)=s. For a plan τ1×τ2\tau_1\times\tau_2, cost⁡^(τ1×τ2):=∣τ1∣⋅∣τ2∣+cost⁡^(τ1)+cost⁡^(τ2)\widehat{\operatorname{cost}}(\tau_1\times\tau_2):=|\tau_1|\cdot|\tau_2|+\widehat{\operatorname{cost}}(\tau_1)+\widehat{\operatorname{cost}}(\tau_2).

Definition 2 (cost excluding the root). For al plan τ\tau, cost⁡(τ):=cost⁡^(τ)−∣τ∣\operatorname{cost}(\tau):=\widehat{\operatorname{cost}}(\tau)-|\tau|.

Alternatively, the cost excluding the root can also be defined by induction as follows. The base case is cost⁡(s)=0\operatorname{cost}(s)=0 for a leaf ss which is also a root in that case. The cost of the leaves will be accounted for during their evaluation. For a plan τ=τ1×τ2\tau=\tau_1\times\tau_2, we have cost⁡(τ)=cost⁡(τ1)+cost⁡(τ2)+∣τ1∣+∣τ2∣\operatorname{cost}(\tau)=\operatorname{cost}(\tau_1)+\operatorname{cost}(\tau_2)+|\tau_1|+|\tau_2|.

Example 3. If τ\tau is (5×2)×(10×2)(5\times2)\times(10\times2) then cost⁡(τ)=5+2+10+2+10+20=49\operatorname{cost}(\tau)=5+2+10+2+10+20=49 and cost⁡^(τ)=5+2+10+2+10+20+200=249\widehat{\operatorname{cost}}(\tau)=5+2+10+2+10+20+200=249.

Definition 3. MultOrd\mathsf{MultOrd} is the following optimization problem: given a multiset S={si}i=1nS=\{s_i\}_{i=1}^n of positive integers written in binary, compute a plan τ\tau to compute s1×⋯×sns_1\times\cdots\times s_n minimizing cost⁡(τ)\operatorname{cost}(\tau).

We will also consider the variant MultOrd\mathsf{MultOrd} where we minimize cost⁡^(τ)\widehat{\operatorname{cost}}(\tau). To avoid ambiguity, we talk about ‘MultOrd\mathsf{MultOrd} for cost’ and ‘MultOrd\mathsf{MultOrd} for cost⁡^\widehat{\operatorname{cost}}’. Note that the distinction is not important for exact solving, since in this case, the two problems are equivalent. However the distinction is important when considering approximation ratios.

Let SS be an instance of MultOrd\mathsf{MultOrd} and X⊂SX\subset S a non-empty subset of SS. We say that a plan τ\tau is following XX if it is of the form τ=τ1×τ2\tau=\tau_1\times\tau_2 such that S(τ1)=XS(\tau_1)=X and S(τ2)=S∖XS(\tau_2)=S\setminus X. Moreover, for any subset X⊆SX\subseteq S, we denote the weight of XX in SS to be wS(X)=∏s∈Xs+∏s∈S∖Xsw_S(X)=\prod_{s\in X}s+\prod_{s\in S\setminus X}s. Therefore the cost of a plan τ=τ1×τ2\tau=\tau_1\times\tau_2 following X⊆SX\subseteq S is cost⁡(τ)=cost⁡(τ1)+cost⁡(τ2)+wS(X)\operatorname{cost}(\tau)=\operatorname{cost}(\tau_1)+\operatorname{cost}(\tau_2)+w_S(X).

Exact solving

For an instance SS, we denote by OPT⁡(S)\operatorname{OPT}(S) (resp. OPT⁡^(S)\widehat{\operatorname{OPT}}(S)) the optimal cost of the MultOrd\mathsf{MultOrd} problem for this instance using the cost (resp. cost⁡^\widehat{\operatorname{cost}}) objective function.

Solving MultOrd\mathsf{MultOrd} could be decomposed into phases: find the right permutation on the leaves and then choose the inner structure of the tree. The following proposition states that if the right permutation has been found, the problem can be solved in polynomial time. This is especially useful since some algorithms in databases rely on a particular choice of permutation. Given an instance S={si}i=1nS=\{s_i\}_{i=1}^n of MultOrd\mathsf{MultOrd}, a plan computing s1×⋯×sns_1\times\cdots\times s_n respecting the order is a plan which in its associated bracketing, element sis_i appears before sjs_j if and only if i<ji<j. Equivalently, it is a plan in which the binary tree’s leaves are s1,…,sns_1,\ldots,s_n in that order and such that no edges of the tree are crossing.

Example 4. For the instance {2,5,7,8}\{2,5,7,8\}, the plan (2×5)×(7×8)(2\times5)\times(7\times8) computes the product 2×5×7×82\times5\times7\times8 and respects the order, but the plan (2×8)×(5×7)(2\times8)\times(5\times7) does not respect the order.

Proposition 1. Let {si}i=1n\{s_i\}_{i=1}^n be an instance of MultOrd\mathsf{MultOrd}. One can find an optimal plan respecting the order in time polynomial in the size of the instance.

Proof. We propose an algorithm based on dynamic programming. The subproblems are M[i,j]M[i,j], which denote the optimal value of cost⁡\operatorname{cost} of a plan to compute si×⋯×sjs_i\times\cdots\times s_j that follows the order si,…,sjs_i,\ldots,s_j. We now prove that:

∀i≤j, M[i,j]={siif i=j,min⁡i≤a≤j−1{M[i,a]+M[a+1,j]+∏b=ijsb}otherwise.\forall i\le j,\ M[i,j]= \begin{cases} s_i & \text{if } i=j,\\ \min_{i\le a\le j-1}\left\{M[i,a]+M[a+1,j]+\prod_{b=i}^{j}s_b\right\} & \text{otherwise.} \end{cases}

The base case is true. The inductive case is proven as follows. In the sequel, we say that τ\tau is a plan for si,…,sjs_i,\ldots,s_j when it is a plan for computing si×⋯×sjs_i \times\cdots\times s_j in that order. Thus,

M[i,j]=min⁡τ plan for si,…,sjcost⁡^(τ)=min⁡i≤a≤j−1min⁡τ1 plan for si,…,saτ2 plan for sa+1,…,sj(cost⁡^(τ1)+cost⁡^(τ2)+∣τ1∣×∣τ2∣)=min⁡i≤a≤j−1{M[i,a]+M[a+1,j]+∏b=ijsb}.M[i,j] = \min_{\tau\text{ plan for }s_i,\ldots,s_j} \widehat{\operatorname{cost}}(\tau) = \min_{i\leq a\leq j-1}\min_{\substack{\tau_1\text{ plan for }s_i,\ldots,s_a\\\tau_2\text{ plan for }s_{a+1},\ldots,s_j}} \left(\widehat{\operatorname{cost}}(\tau_1)+\widehat{\operatorname{cost}}(\tau_2)+|\tau_1|\times|\tau_2|\right) = \min_{i\leq a\leq j-1}\left\{M[i,a]+M[a+1,j]+\prod_{b=i}^{j}s_b\right\}.

We can design a dynamic programming algorithm that fills a table MM of size O(n2)O(n^2). Each step costs at most O(n2)O(n^2) arithmetic operations, resulting in a complexity of O(n4)O(n^4).

Since we can enumerate all permutations of SS and solve the problem for each permutation using Proposition 1, the final complexity is n!O(n4)=O(n!)n!O(n^4)=O(n!) since n!×n4≤(n+4)!n!\times n^4\leq(n+4)!.

Corollary 1. MultOrd is solvable in O(n!)O(n!).

We can actually obtain a faster bound.

Theorem 1. MultOrd can be solved in O(3n)O(3^n) time.

Proof. Let SS be an instance of MultOrd. At each step, every plan splits the instance into two child subplans. Thus,

OPT⁡^(S)=∏s∈Ss+min⁡∅≠X⊊S(OPT⁡^(X)+OPT⁡^(S∖X)).\widehat{\operatorname{OPT}}(S)=\prod_{s\in S}s+\min_{\varnothing\ne X\subsetneq S}\left(\widehat{\operatorname{OPT}}(X)+\widehat{\operatorname{OPT}}(S\setminus X)\right).

Then, consider a dynamic programming algorithm for this formula. It has to feed an array of size ∣{∅≠X⊊S}∣=2n−2|\{\varnothing\ne X\subsetneq S\}|=2^n-2. At each step, it goes though all non-trivial subsets. We denote by smax⁡s_{\max} the biggest sis_i. Notice that the cost of computing the product of some sis_i’s is equal to the sum of their representations’ sizes. Therefore the computation cost for the instance SS is:

∑∅≠X⊊S(∣{Y∣∅≠Y⊊X}∣+∣X∣)≤∑∅≠X⊊S2∣X∣−2+∣X∣≤∑i=0n(ni)(2i+i)≤3n+n2n=O(3n+n2n).\sum_{\varnothing\ne X\subsetneq S}\left(|\{Y\mid\varnothing\ne Y\subsetneq X\}|+|X|\right) \leq\sum_{\varnothing\ne X\subsetneq S}2^{|X|}-2+|X| \leq\sum_{i=0}^{n}\binom{n}{i}(2^i+i) \leq3^n+n2^n =O(3^n+n2^n).

Using the binomial theorem stating that ∀x,y,a∈N,(x+y)a=∑i=0a(ai)xiyn−i\forall x,y,a\in\mathbb{N},(x+y)^a=\sum_{i=0}^{a}\binom{a}{i}x^iy^{n-i}. Thus the computation times is O(3n)O(3^n). Moreover, note that minimizing cost⁡^\widehat{\operatorname{cost}} is the same as minimizing cost.

Preprocessing

In this section, we highlight some safe preprocessing rules that can be applied at the beginning of any algorithm so that we can restrict our attention to more specific instances.

Proposition 2. Let SS be an instance of MultOrd and let ∅≠S′⊊S\varnothing\ne S'\subsetneq S, then OPT⁡(S)≤OPT⁡^(S′)+OPT⁡^(S∖S′)\operatorname{OPT}(S)\leq\widehat{\operatorname{OPT}}(S')+\widehat{\operatorname{OPT}}(S\setminus S').

Proof. Let τ1\tau_1 (resp. τ2\tau_2) be an optimal plan for S′S' (resp. S∖S′S\setminus S') for the cost objective function. Let τ=τ1×τ2\tau=\tau_1\times\tau_2. Note that τ\tau is a valid plan for the instance SS since S=S′⊔(S∖S′)S=S'\sqcup(S\setminus S') where ⊔\sqcup is the disjoint union operator. Then OPT⁡(S)≤cost⁡(τ)=cost⁡(τ1)+cost⁡(τ2)=OPT⁡(S′)+OPT⁡(S∖S′)\operatorname{OPT}(S)\leq\operatorname{cost}(\tau)=\operatorname{cost}(\tau_1)+\operatorname{cost}(\tau_2)=\operatorname{OPT}(S')+\operatorname{OPT}(S\setminus S').

Proposition 3. Let SS be an instance of MultOrd such that one input element is equal to 11. Then there is an optimal strategy that starts by multiplying this element with the next smallest element.

Proof. Assume S={s1,…,sn}S=\{s_1,\ldots,s_n\}, that s1=1s_1=1 and that s2=min⁡{si, 1<i≤n}s_2=\min\{s_i,\,1<i\le n\} be the next smallest input element. Let τ∗\tau^* be an optimal strategy on SS and τ2\tau_2 be an optimal strategy on the instance {s2,…,sn}\{s_2,\ldots,s_n\}. Let τ\tau be the strategy where we first multiply s1s_1 and s2s_2, then we apply the strategy of τ2\tau_2. We claim that τ\tau is an optimal plan. To prove it, first notice that cost⁡(τ)=cost⁡(τ2)+s1+s2=s1+s2+OPT⁡(S∖{s1})\operatorname{cost}(\tau)=\operatorname{cost}(\tau_2)+s_1+s_2=s_1+s_2+\operatorname{OPT}(S\setminus\{s_1\}) since the multiplication of s1s_1 and s2s_2 is accounted as a leaf in τ2\tau_2. Now, observe that in τ∗\tau^*, s1s_1 is multiplied with some subtree τ2∗\tau_2^*. Let τ1∗=s1×τ2∗\tau_1^*=s_1\times\tau_2^* be the subplan appearing in τ∗\tau^* and S′S' be the set of numbers involved in τ2∗\tau_2^*. First note that cost⁡(τ1∗)=cost⁡(τ2∗)+∣s1∣+∣τ2∗∣=cost⁡(τ2∗)+s1+∣τ2∗∣\operatorname{cost}(\tau_1^*)=\operatorname{cost}(\tau_2^*)+|s_1|+|\tau_2^*|=\operatorname{cost}(\tau_2^*)+s_1+|\tau_2^*| and that ∣τ2∗∣≥s2|\tau_2^*|\ge s_2 by definition of s2s_2. Then,

cost⁡(τ∗)≥cost⁡^(τ1∗)+OPT⁡^(S∖(S′∪{s1}))≥cost⁡^(τ2∗)+s1+s2+OPT⁡^(S∖(S′∪{s1}))≥OPT⁡^(S′)+OPT⁡^(S∖(S′∪{s1}))+s1+s2≥s1+s2+OPT⁡(S∖{s1})(By Proposition 2.)\begin{aligned} \operatorname{cost}(\tau^*) &\ge\widehat{\operatorname{cost}}(\tau_1^*)+\widehat{\operatorname{OPT}}(S\setminus(S'\cup\{s_1\}))\\ &\ge\widehat{\operatorname{cost}}(\tau_2^*)+s_1+s_2+\widehat{\operatorname{OPT}}(S\setminus(S'\cup\{s_1\}))\\ &\ge\widehat{\operatorname{OPT}}(S')+\widehat{\operatorname{OPT}}(S\setminus(S'\cup\{s_1\}))+s_1+s_2\\ &\ge s_1+s_2+\operatorname{OPT}(S\setminus\{s_1\})\quad\text{(By Proposition 2.)} \end{aligned}

Thus, τ\tau is an optimal plan because τ∗\tau^* is optimal.

Therefore, from now on, we assume that all numbers in any input instance of MultOrd are greater than or equal to 2.

Bounds on cost

In this section, we introduce new lower and upper bounds on the cost of plans on a fixed instance which, in the following, will allow us to prove approximation ratios for approximation algorithms. First, we introduce the Pacman-plan (denoted τPAC\tau_{\mathrm{PAC}}) which has the highest cost for any instance. Specifically, given an instance S={s1,…,sn}S=\{s_1,\ldots,s_n\} on nn elements such that s1≥⋯≥sns_1\ge\cdots\ge s_n, the first multiplication is the product of s1s_1 and s2s_2 and for i≥2i\ge2, the iith multiplication is the product of si+1s_{i+1} with the product of the first ii elements. At each step, the Pacman plan introduces a new largest number; its shape is a caterpiller. Said differently, the Pacman-plan for SS is ((((s1×s2)×s3)×s4)×⋯ )×sn)((((s_1\times s_2)\times s_3)\times s_4)\times\cdots)\times s_n). Visually:

Pacman-plan tree

Figure 2 (PDF p. 6).

Example 5. The Pacman-plan for {8,5,3,3}\{8,5,3,3\} is (((8×5)×3)×3)(((8\times5)\times3)\times3).

The cost of a Pacman-plan is as follows.

Proposition 4. Let S={si}i=1nS=\{s_i\}_{i=1}^n be an instance of MultOrd such that s1≥⋯≥sns_1\ge\cdots\ge s_n and let τPAC\tau_{\mathrm{PAC}} be the Pacman-plan on SS. Then, by definition,

cost⁡^(τPAC)=∑i=2n(∏j=1isj)+∑i=1nsi=∑i=1n(si+∏j=1isj)−s1.\widehat{\operatorname{cost}}(\tau_{\mathrm{PAC}})=\sum_{i=2}^{n}\left(\prod_{j=1}^{i}s_j\right)+\sum_{i=1}^{n}s_i=\sum_{i=1}^{n}\left(s_i+\prod_{j=1}^{i}s_j\right)-s_1.

Proposition 5. The Pacman-plan has the highest achievable cost.

Proof. For an instance SS on nn elements, we compare the Pacman-plan on SS, denoted τPAC\tau_{\mathrm{PAC}}, to another (arbitrary) plan τ\tau. Both plans count the leaves and the root (using cost⁡^\widehat{\operatorname{cost}}), so we will only compare the cost of the multiplications at the n−2n-2 internal nodes (i.e., non-root and non-leaf nodes).

We will argue that there is a bijection between the internal nodes of τPAC\tau_{\mathrm{PAC}} and the internal nodes of τ\tau such that for all internal nodes of τPAC\tau_{\mathrm{PAC}}, the evaluation of this node is at least as large as the evaluation of the associated node of τ\tau. To do this, for each plan, we order the multiplications in that plan so that a multiplication at a parent node comes after the multiplications corresponding to any of its children (and hence descendants). We call such an order a hierarchy-respecting order. We use the following claim.

Claim 1. In any hierarchy-respecting order, the ithi^{\mathrm{th}} multiplication corresponds to the product of at most i+1i+1 elements.

Proof. Suppose each time we multiply two numbers together we use a piece of glue to connect them. For example, a product of two elements contains one piece of glue and a product of four elements contains three pieces of glue. Since we use exactly one new piece of glue for each multiplication, at the ithi^{\mathrm{th}} step we can produce a product corresponding to a number using at most ii pieces of glue. Hence, it can be the product of at most i+1i+1 elements, which proves the claim. ◊

Observe that the ithi^{\mathrm{th}} multiplication in the (unique) hierarchy-respecting order of τPAC\tau_{\mathrm{PAC}} is the product of the i+1i+1 largest elements. For a hierarchy-respecting order for τ\tau, by Claim 1, the ithi^{\mathrm{th}} multiplication can be the product of at most i+1i+1 elements, which is clearly at most the product of the largest i+1i+1 elements corresponding to the ithi^{\mathrm{th}} multiplication in τPAC\tau_{\mathrm{PAC}}. □

Lemma 1. Let SS be an instance of MultOrd such that all numbers are at least 2 and let τPAC\tau_{\mathrm{PAC}} be a Pacman-plan on SS. Then cost⁡(τPAC)≤1min⁡(S)−1∏s∈Ss+∑s∈Ss−max⁡(S)\operatorname{cost}(\tau_{\mathrm{PAC}}) \leq\frac{1}{\min(S)-1}\prod_{s\in S}s+\sum_{s\in S}s-\max(S).

Proof. Wlog, assume S={si}i=1nS=\{s_i\}_{i=1}^{n} and s1≥⋯≥sns_1\geq\cdots\geq s_n and let P=∏s∈SsP=\prod_{s\in S}s. By Proposition 4 we have

cost⁡^(τPAC)=∑i=1nsi+∑i=1n∏j=1isj−s1.\widehat{\operatorname{cost}}(\tau_{\mathrm{PAC}})=\sum_{i=1}^{n}s_i+\sum_{i=1}^{n}\prod_{j=1}^{i}s_j-s_1.

Note that since all s∈Ss\in S respect s≥sns\geq s_n, then ∀i∈[n], ∏j=i+1nsj≥snn−i\forall i\in[n],\ \prod_{j=i+1}^{n}s_j\geq s_n^{n-i}. Therefore,

∑i=1n∏j=1isj=∑i=1n∏j=1nsj∏j=i+1nsj≤P∑i=1n1snn−i=P∑i=0n−11sni≤P∑i=0+∞1sni=snsn−1P.\sum_{i=1}^{n}\prod_{j=1}^{i}s_j=\sum_{i=1}^{n}\frac{\prod_{j=1}^{n}s_j}{\prod_{j=i+1}^{n}s_j}\leq P\sum_{i=1}^{n}\frac{1}{s_n^{n-i}}=P\sum_{i=0}^{n-1}\frac{1}{s_n^i}\leq P\sum_{i=0}^{+\infty}\frac{1}{s_n^i}=\frac{s_n}{s_n-1}P.

Last inequality holds since sn≥2s_n\geq2 and those the sum is converging. Therefore, cost⁡(τPAC)=cost⁡^(τPAC)−∣τPAC∣≤∑i=1nsi−s1+snsn−1P−P≤1min⁡(S)−1∏s∈Ss+∑i=1nsi−max⁡(S)\operatorname{cost}(\tau_{\mathrm{PAC}})=\widehat{\operatorname{cost}}(\tau_{\mathrm{PAC}})-|\tau_{\mathrm{PAC}}|\leq\sum_{i=1}^{n}s_i-s_1+\frac{s_n}{s_n-1}P-P\leq\frac{1}{\min(S)-1}\prod_{s\in S}s+\sum_{i=1}^{n}s_i-\max(S). □

Corollary 2. Let SS be an instance of MultOrd such that all numbers are at least 2 and let τPAC\tau_{\mathrm{PAC}} be a Pacman-plan on SS. Then cost⁡(τPAC)≤∏s∈Ss+∑s∈Ss−max⁡(S)\operatorname{cost}(\tau_{\mathrm{PAC}})\leq\prod_{s\in S}s+\sum_{s\in S}s-\max(S).

Lemma 2. Let s1,…,sns_1,\ldots,s_n be some integers greater or equal to 2, then ∑i=1nsi≤∏i=1nsi\sum_{i=1}^{n}s_i\leq\prod_{i=1}^{n}s_i.

Proof. For n=2n=2,

s1s2=(s1−1)s2+s2=(s1−1)(s2−1)+s2+s1−1≥s2+s1s_1s_2=(s_1-1)s_2+s_2=(s_1-1)(s_2-1)+s_2+s_1-1\geq s_2+s_1

Thus, the property is true for n=2n=2. Assume the property is true for nn and let s1,…,sn+1s_1,\ldots,s_{n+1} be n+1n+1 integers greater than 2. Then

∑i=1n+1si=sn+1+∑i=1nsi≤sn+1+∏i=1nsi≤(sn+1)(∏i=1nsi)≤∏i=1n+1si.\sum_{i=1}^{n+1}s_i=s_{n+1}+\sum_{i=1}^{n}s_i\leq s_{n+1}+\prod_{i=1}^{n}s_i\leq(s_{n+1})\left(\prod_{i=1}^{n}s_i\right)\leq\prod_{i=1}^{n+1}s_i.

The first inequality holds by the induction hypothesis and the second one holds by the case for n=2n=2. Then the property holds. □

Proposition 6. Consider an instance SS of MultOrd such that all numbers are at least 2, then for all plans τ\tau on SS, cost⁡(τ)≤2∣τ∣\operatorname{cost}(\tau)\leq2|\tau|.

Proof. Let τPAC\tau_{\mathrm{PAC}} be a Pacman-plan on SS. By Proposition 5, cost⁡(τ)≤cost⁡(τPAC)\operatorname{cost}(\tau)\leq\operatorname{cost}(\tau_{\mathrm{PAC}}) and using Corollary 2 and Lemma 2 we have cost⁡(τPAC)≤∏s∈Ss+∏s∈Ss\operatorname{cost}(\tau_{\mathrm{PAC}})\leq\prod_{s\in S}s+\prod_{s\in S}s. So cost⁡(τ)≤2∣τ∣\operatorname{cost}(\tau)\leq2|\tau|. □

Lemma 3. Let SS be an instance of MultOrd on at least three elements and let τ=τ1×τ2\tau=\tau_1\times\tau_2 be a plan on SS. Then cost⁡(τ)≥∣τ1∣+∣τ2∣+∑s∈Ss−smax⁡\operatorname{cost}(\tau)\geq|\tau_1|+|\tau_2|+\sum_{s\in S}s-s_{\max}.

Proof. Assume that both τ1\tau_1 and τ2\tau_2 are plans on at least two elements. Then no leaves are accounted in ∣τ1∣|\tau_1| nor in ∣τ2∣|\tau_2|. Therefore cost⁡(τ)≥∑s∈Ss+∣τ1∣+∣τ2∣≥∑s∈Ss+∣τ1∣+∣τ2∣−smax⁡\operatorname{cost}(\tau)\geq\sum_{s\in S}s+|\tau_1|+|\tau_2|\geq\sum_{s\in S}s+|\tau_1|+|\tau_2|-s_{\max}.

Otherwise, wlog, assume τ1\tau_1 is a plan on only one element s0s_0 thus τ2\tau_2 is a plan on at least two elements. Then cost⁡(τ)=cost⁡(τ2)+∣τ1∣+∣τ2∣≥∑s∈S∖{s0}s+∣τ1∣+∣τ2∣≥∣τ1∣+∣τ2∣+∑s∈Ss−smax⁡\operatorname{cost}(\tau)=\operatorname{cost}(\tau_2)+|\tau_1|+|\tau_2|\geq\sum_{s\in S\setminus\{s_0\}}s+|\tau_1|+|\tau_2|\geq|\tau_1|+|\tau_2|+\sum_{s\in S}s-s_{\max}.

Half-plan

In this subsection, we introduce the naive notion of a Half-plan (denoted τHALF\tau_{\mathrm{HALF}}) and prove an upper bound on its cost. These results are used to prove approximation results such as an FPTAS for the cost with the root in Theorem 2. A Half-plan on an instance SS is a plan that puts half of the input numbers on one side and the rest of the numbers on the other side. Therefore if the Half-plan on instance SS on nn elements, τHALF=τ1×τ2\tau_{\mathrm{HALF}}=\tau_1\times\tau_2, follows XX, then both XX and S\XS\backslash X have at least ⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor elements. Notice that an instance can have several Half-plans.

Example 6. An example of a Half-plan for {2,2,3,3,5,8,9}\{2,2,3,3,5,8,9\} is ((2×8)×3)×(5×(3×(2×9)))((2\times8)\times3)\times(5\times(3\times(2\times9))).

Lemma 4. Let SS be an instance of MultOrd, then cost⁡(τHALF)≤6min⁡(S)n2−1∏s∈Ss\operatorname{cost}(\tau_{\mathrm{HALF}})\leq\frac{6}{\min(S)^{\frac{n}{2}-1}}\prod_{s\in S}s.

Proof. Let τHALF=τ1×τ2\tau_{\mathrm{HALF}}=\tau_1\times\tau_2 be an Half-plan on SS. Firstly, notice that since all numbers in τ1\tau_1 are greater than or equal to min⁡(S)\min(S) and since τ1\tau_1 contains at least n2−1\frac{n}{2}-1 numbers, we have, ∣τ1∣≥min⁡(S)n2−1|\tau_1|\geq\min(S)^{\frac{n}{2}-1}. Since ∏s∈Ss=∣τHALF∣=∣τ1∣⋅∣τ2∣\prod_{s\in S}s=|\tau_{\mathrm{HALF}}|=|\tau_1|\cdot|\tau_2|, we have,

∣τ2∣=∣τHALF∣∣τ1∣≤∏s∈Ssmin⁡(S)n2−1.|\tau_2|=\frac{|\tau_{\mathrm{HALF}}|}{|\tau_1|}\leq\frac{\prod_{s\in S}s}{\min(S)^{\frac{n}{2}-1}}.

Similarly, ∣τ1∣≤∏s∈Ssmin⁡(S)n2−1|\tau_1|\leq\frac{\prod_{s\in S}s}{\min(S)^{\frac{n}{2}-1}}. Therefore,

cost⁡(τ)=cost⁡(τ1)+cost⁡(τ2)+∣τ1∣+∣τ2∣≤3(∣τ1∣+∣τ2∣)≤6min⁡(S)n2−1∏s∈Ss.\operatorname{cost}(\tau)=\operatorname{cost}(\tau_1)+\operatorname{cost}(\tau_2)+|\tau_1|+|\tau_2|\leq3(|\tau_1|+|\tau_2|)\leq\frac{6}{\min(S)^{\frac{n}{2}-1}}\prod_{s\in S}s.

First inequality uses Proposition 6 on τ1\tau_1 and τ2\tau_2 and the second inequality uses the above inequalities.

Lemma 5. For any instance SS of MultOrd, cost⁡(τHALF)≤242n2cost⁡(τPAC)\operatorname{cost}(\tau_{\mathrm{HALF}})\leq\frac{24}{2^{\frac{n}{2}}}\operatorname{cost}(\tau_{\mathrm{PAC}}).

Proof. Let S={si}i=1nS=\{s_i\}_{i=1}^{n} be an instance of MultOrd such that s1≥⋯≥sn≥2s_1\geq\cdots\geq s_n\geq2 then, by Proposition 4, we have

cost⁡(τPAC)=∑i=1n(si+∏j=1isj)−s1−∏s∈Ss≥∑i=1n−1∏j=1isj≥∏j=1n−1sj≥1sn∏s∈Ss.\operatorname{cost}(\tau_{\mathrm{PAC}})=\sum_{i=1}^{n}\left(s_i+\prod_{j=1}^{i}s_j\right)-s_1-\prod_{s\in S}s\geq\sum_{i=1}^{n-1}\prod_{j=1}^{i}s_j\geq\prod_{j=1}^{n-1}s_j\geq\frac{1}{s_n}\prod_{s\in S}s.

Using Lemma 4 we have,

cost⁡(τHALF)≤6min⁡(S)n2−1∏s∈Ss≤6min⁡(S)n2−2cost⁡(τPAC)≤242n2cost⁡(τPAC).\operatorname{cost}(\tau_{\mathrm{HALF}})\leq\frac{6}{\min(S)^{\frac{n}{2}-1}}\prod_{s\in S}s\leq\frac{6}{\min(S)^{\frac{n}{2}-2}}\operatorname{cost}(\tau_{\mathrm{PAC}})\leq\frac{24}{2^{\frac{n}{2}}}\operatorname{cost}(\tau_{\mathrm{PAC}}).

Trivial approximation factors

Thanks to the bound on the cost of a plan obtained in Proposition 6, we are able to find approximation factors for any plan. Namely, we show that no matter the chosen plan, we can prove a guarantee on its cost.

Lemma 6. Let SS be an instance with all input elements ≥2\ge2. Then every plan τ\tau on SS is a 3-approximation of MultOrd\mathrm{MultOrd} for the cost objective function.

Proof. Let τ\tau be a plan and let τ∗\tau^{*} be an optimal strategy on SS. Then by Proposition 6 we have

cost⁡^(τ)≤3∣τ∣=3∣τ∗∣≤3cost⁡^(τ∗)≤3OPT⁡^(S).\widehat{\operatorname{cost}}(\tau) \le3|\tau| = 3|\tau^{*}| \le3\widehat{\operatorname{cost}}(\tau^{*}) \le3\widehat{\operatorname{OPT}}(S).

Lemma 7. Let SS be an instance of MultOrd\mathrm{MultOrd} such that all numbers are at least 2 and let P=∏s∈SsP = \prod_{s\in S}s. Then every plan on SS is a (2P)(2\sqrt{P})-approximation for cost.

Proof. Let τ=τ1×τ2\tau= \tau_1 \times\tau_2 be a plan on SS. Since P=∣τ∣=∣τ1∣⋅∣τ2∣P = |\tau| = |\tau_1| \cdot|\tau_2| then either ∣τ1∣|\tau_1| or ∣τ2∣|\tau_2| is bigger than P\sqrt{P}. Thus cost⁡(τ)=cost⁡(τ1)+cost⁡(τ2)+∣τ1∣+∣τ2∣≥P\operatorname{cost}(\tau) = \operatorname{cost}(\tau_1) + \operatorname{cost}(\tau_2) + |\tau_1| + |\tau_2| \ge\sqrt{P}. Thus OPT⁡(S)≥P\operatorname{OPT}(S) \ge\sqrt{P}. Moreover, by property 6 since all sis_i’s are at least 2, we have cost⁡(τ)≤2∣τ∣≤2P\operatorname{cost}(\tau) \le2|\tau| \le2P. Thus cost⁡(τ)OPT⁡(S)≤2PP≤2P\frac{\operatorname{cost}(\tau)}{\operatorname{OPT}(S)} \le\frac{2P}{\sqrt{P}} \le2\sqrt{P}.

FPTAS

In this section, we present a fully polynomial-time approximation scheme (FPTAS) for both the cost⁡^\widehat{\operatorname{cost}} and cost objective functions. Given a parameter ε>0\varepsilon> 0, the algorithm produces a (1+ε)(1+\varepsilon)-approximate solution in time polynomial in both 1ε\frac{1}{\varepsilon} and in the size of the instance.

Cost that includes the root

First, we tackle the case of the cost that includes the final product at the root, which is easier and will be used in the FPTAS for the case in which the cost excludes the root.

Theorem 2. MultOrd\mathrm{MultOrd} for cost⁡^\widehat{\operatorname{cost}} has an FPTAS.

Proof. Let ε>0\varepsilon> 0 be the parameter in the desired approximation bound and let SS be an instance of MultOrd\mathrm{MultOrd} on nn elements. Thanks to Proposition 3, we can apply a polynomial times preprocessing on the instance and assume that all input elements in SS are at least 2. Then, we consider the following algorithm:

  1. If ε<1222\varepsilon< \frac{12}{2^2}, we solve it using the exact algorithm of Theorem 1.

  2. Otherwise construct a Half-plan τHALF\tau_{\mathrm{HALF}} on SS (defined at the end of § 6).

The algorithm outputs a (1+ε)(1+\varepsilon)-approximation. If ε<1222\varepsilon< \frac{12}{2^2}, we solve exactly the problem, the output strategy is optimal and thus is a (1+ε)(1+\varepsilon)-approximation. Otherwise, ε≥1222\varepsilon\ge\frac{12}{2^2}. Lemma 4 give us that cost⁡^(τHALF)≤1222n−1∣τHALF∣+∣τHALF∣\widehat{\operatorname{cost}}(\tau_{\mathrm{HALF}}) \le\frac{12}{2^{\frac{2}{n}}-1}|\tau_{\mathrm{HALF}}| + |\tau_{\mathrm{HALF}}| since the smaller number in SS is at least 2. Therefore,

cost⁡^(τHALF)≤(1222n−1+1)∣τHALF∣≤(1+ε)∣τHALF∣≤(1+ε)OPT⁡^(S).\widehat{\operatorname{cost}}(\tau_{\mathrm{HALF}}) \le\left(\frac{12}{2^{\frac{2}{n}}-1}+1\right)|\tau_{\mathrm{HALF}}| \le(1+\varepsilon)|\tau_{\mathrm{HALF}}| \le(1+\varepsilon)\widehat{\operatorname{OPT}}(S).

Since OPT⁡^(S)≥∏s∈Ss=∣τHALF∣\widehat{\operatorname{OPT}}(S) \ge\prod_{s\in S}s = |\tau_{\mathrm{HALF}}|. Hence τHALF\tau_{\mathrm{HALF}} is a (1+ε)(1+\varepsilon)-approximation of MultOrd\mathrm{MultOrd} using cost⁡^\widehat{\operatorname{cost}}.

Complexity analysis. If ε<1222n\varepsilon< \frac{12}{2^{\frac{2}{n}}} then we consider the dynamic programming of Theorem 1 running in time O(3n)O(3^n). We have n<2log⁡(12ε)log⁡(2)≤2log⁡3log⁡(2)log⁡3(12ε)n < \frac{2\log(\frac{12}{\varepsilon})}{\log(2)} \le\frac{2\log3}{\log(2)}\log_3(\frac{12}{\varepsilon}). Then 3n≤(3log⁡3(12ε))2log⁡3log⁡2=(12ε)2log⁡3log⁡23^n \le\left(3^{\log_3(\frac{12}{\varepsilon})}\right)^{\frac{2\log3}{\log2}} = (\frac{12}{\varepsilon})^{\frac{2\log3}{\log2}} which is polynomial in 1ε\frac{1}{\varepsilon} and does not depend on nn. Otherwise, notice that constructing τ1\tau_1 and τ2\tau_2 is polynomial in nn and in 1ε\frac{1}{\varepsilon} since we just split the sis_i’s in half and take arbitrarily ordering. Thus, this shows that the proposed algorithm is a FPTAS algorithm.

Cost that excludes the root

We now tackle the problem where we use the cost objective function, which does not count the root. For this purpose, we introduce the known ProdPart problem which is an NP-complete problem first introduced in [9]. ProdPart takes as input a multiset of positive integers S={si}i=1nS = \{s_i\}_{i=1}^n and outputs a non-empty subset X⊂SX \subset S minimizing the majority of XX in SS denoted mS(X)=max⁡(∏s∈Xs, ∏s∈S∖Xs)m_S(X) = \max\left(\prod_{s\in X}s,\ \prod_{s\in S\setminus X}s\right).

ProdPart has been proved having an FPTAS algorithm in section 4 of [9]. We will use this result to design an FPTAS algorithm for MultOrd for cost.

Proposition 7. [See Section 4 of [9]]. There is an algorithm running in time O(n3log⁡(smax⁡)1ε)O\left(n^3\log(s_{\max})^{\frac{1}{\varepsilon}}\right) that computes a (1+ε)(1+\varepsilon)-approximation of ProdPart.

In order to make the connection between ProdPart and MultOrd, we have to compare the majority and the weight. We will firstly show that the ProdPart is equivalent to finding a subset X⊆SX \subseteq S minimizing the weight of XX in SS, denoted wS(X):=∏s∈Xs+∏s∈S∖Xsw_S(X) := \prod_{s\in X}s+\prod_{s\in S\setminus X}s. Notice that for every plan τ=τ1×τ2\tau=\tau_1\times\tau_2 following a set XX, cost⁡(τ)=cost⁡(τ1)+cost⁡(τ2)+wS(X)\operatorname{cost}(\tau)=\operatorname{cost}(\tau_1)+\operatorname{cost}(\tau_2)+w_S(X).

Lemma 8. Let SS be an instance of ProdPart, if X⊆SX\subseteq S minimizes mS(X)m_S(X) then XX also minimizes wS(X)w_S(X).

Proof. Let P=∏s∈SsP=\prod_{s\in S}s. Notice first that 0<P≤mS(X)≤P0<\sqrt{P}\leq m_S(X)\leq P and that wS(X)=mS(X)+PmS(X)w_S(X)=m_S(X)+\frac{P}{m_S(X)}.

Let h:{[P,P]→Rx↦x+Pxh:\begin{cases}[\sqrt{P},P]\to\mathbb{R}\\x\mapsto x+\frac{P}{x}\end{cases}. Notice that ∀x∈[P,P]\forall x\in[\sqrt{P},P], h′(x)=1−Px2≥0h'(x)=1-\frac{P}{x^2}\geq0 so hh is increasing. Thus, ∀X,Y⊆S\forall X,Y\subseteq S, mS(X)≤mS(Y)⇔wS(X)≤wS(Y)m_S(X)\leq m_S(Y)\Leftrightarrow w_S(X)\leq w_S(Y). Therefore, if XX minimizes mS(X)m_S(X), XX also minimizes wS(X)w_S(X).

Lemma 9. Let SS be an instance of ProdPart, ε>0\varepsilon>0, X⊆SX\subseteq S minimizing mSm_S, and let Y⊆SY\subseteq S be a (1+ε)(1+\varepsilon)-approximation of mSm_S. Then YY is a (1+ε)(1+\varepsilon)-approximation of wSw_S.

Proof. Firstly, since YY is a (1+ε)(1+\varepsilon)-approximation of mSm_S, mS(Y)≤(1+ε)mS(X)m_S(Y)\leq(1+\varepsilon)m_S(X). Secondly, notice that 0<mS(X)≤mS(Y)≤(1+ε)mS(X)0<m_S(X)\leq m_S(Y)\leq(1+\varepsilon)m_S(X). Thus t=mS(Y)mS(X)∈[1,1+ε]t=\frac{m_S(Y)}{m_S(X)}\in[1,1+\varepsilon]. Let P=∏s∈SsP=\prod_{s\in S}s and α=PmS(X)2\alpha=\frac{P}{m_S(X)^2}, thus

wS(Y)wS(X)=t⋅mS(X)+Pt⋅mS(X)mS(X)+PmS(X)=t+αt1+α≤1+ε+α1+α≤1+ε.\frac{w_S(Y)}{w_S(X)} = \frac{t\cdot m_S(X)+\frac{P}{t\cdot m_S(X)}}{m_S(X)+\frac{P}{m_S(X)}} = \frac{t+\frac{\alpha}{t}}{1+\alpha} \leq \frac{1+\varepsilon+\alpha}{1+\alpha} \leq1+\varepsilon.

Since XX is minimizing mSm_S, by Lemma 8, XX also minimizing wSw_S. This concludes the proof.

Corollary 3. There is an algorithm running in time O(n3log⁡(smax⁡)1ε)O\left(n^3\log(s_{\max})^{\frac{1}{\varepsilon}}\right) that computes a (1+ε)(1+\varepsilon)-approximation of the minimization of wSw_S on an instance SS of ProdPart.

Proof. By Proposition 7 and Lemma 9.

Theorem 3. MultOrd for cost has an FPTAS.

Proof. Let SS an instance of MultOrd and ε>0\varepsilon>0 a fixed constant and let ε′=1+ε−1\varepsilon'=\sqrt{1+\varepsilon}-1. As in the FPTAS presented previously, we first perform a preprocessing step so we can assume all numbers in SS are greater or equal to 2. We consider the following algorithm:

  1. Compute a set X⊆SX\subseteq S that is a (1+ε′)(1+\varepsilon')-approximation of wSw_S.

  2. Return τ=τ1×τ2\tau=\tau_1\times\tau_2 where τ1\tau_1 (resp. τ2\tau_2) is computed via the FPTAS for cost⁡^\widehat{\operatorname{cost}} with ε′\varepsilon' on instance XX (resp. S∖XS\setminus X).

This algorithm outputs a (1+ε)(1+\varepsilon)-approximation Firstly, using the bound found in the proof of Theorem 2, we have that cost⁡^(τ1)≤(1+ε′)∣τ1∣\widehat{\operatorname{cost}}(\tau_1) \le(1+\varepsilon')|\tau_1| and the same holds for τ2\tau_2. Thus

cost⁡(τ)=cost⁡^(τ1)+cost⁡^(τ2)≤(1+ε′)(∣τ1∣+∣τ2∣)=(1+ε′)wS(X).\operatorname{cost}(\tau)=\widehat{\operatorname{cost}}(\tau_1)+\widehat{\operatorname{cost}}(\tau_2)\leq(1+\varepsilon')\left(|\tau_1|+|\tau_2|\right)=(1+\varepsilon')w_S(X).

Let τopt=τ1opt×τ2opt\tau^{opt}=\tau_1^{opt}\times\tau_2^{opt} be an optimal plan on SS, XoptX^{opt} be the set followed by τopt\tau^{opt} and X∗⊆SX^*\subseteq S be the subset minimizing wSw_S. Thus wS(X)≤(1+ε′)wS(X∗)w_S(X)\leq(1+\varepsilon')w_S(X^*) using Lemma 9 and wS(X∗)≤wS(Xopt)w_S(X^*)\leq w_S(X^{opt}) since X∗X^* is optimal. Therefore,

cost⁡(τ)≤(1+ε′)wS(X)≤(1+ε′)2wS(Xopt)≤(1+ε)cost⁡(τopt)=(1+ε)OPT⁡(S).\operatorname{cost}(\tau)\leq(1+\varepsilon')w_S(X)\leq(1+\varepsilon')^2w_S(X^{opt})\leq(1+\varepsilon)\operatorname{cost}(\tau^{opt})=(1+\varepsilon)\operatorname{OPT}(S).

This concludes the proof that the algorithm is a (1+ε)(1+\varepsilon)-approximation of MultOrd for cost.

Complexity Step 1 can be implemented in polynomial time in nn, 1ε\frac{1}{\varepsilon} and the number of bits in the sis_i’s thanks to Proposition 7. This is polynomial in the size of the input and in 1ε\frac{1}{\varepsilon} since sis_i’s are given in binary, thus the log of the biggest sis_i is its size.

Link to ProdPart

The purpose of this section is to highlight links between MultOrd and ProdPart motivated by the FPTAS for the cost objective described in Theorem 3. More precisely, we prove that to reach optimality for MultOrd, the first partition from the top of the plan has to be a good approximation of ProdPart which gives rise to conditions to achieve optimality. However, MultOrd and ProdPart are not equivalent in the general case (but are when all input elements have the same value). Since instances of size two are obvious (no choices to make), we can assume that all considered instances in this section have at least three input elements.

Lemma 10. Let SS be an instance of MultOrd and let X⊂SX\subset S be an γ≥1\gamma\geq1 approximation of ProdPart on SS. Then every plan following XX is a (γmin⁡(S)min⁡(S)−1)\left(\gamma\frac{\min(S)}{\min(S)-1}\right)-approximation for cost.

In particular, since each elements are greater or equal to 2, the plan is always a (2γ)(2\gamma)-approximation.

Proof. We first introduce three plans. Let τ=τ1×τ2\tau=\tau_1\times\tau_2 be a plan following XX and τ∗=τ1∗×τ2∗\tau^*=\tau_1^*\times\tau_2^* be a plan following X∗X^* with X∗X^* being an optimal solution of ProdPart on SS and let τopt=τ1opt×τ2opt\tau^{opt}=\tau_1^{opt}\times\tau_2^{opt} be an optimal solution of MultOrd on SS. Then, let a=min⁡(X)a=\min(X) and b=min⁡(S\X)b=\min(S\backslash X). Wlog we can assume a=min⁡(S)a=\min(S). Thus, a≤ba\leq b and then 1a−1≥1b−1\frac{1}{a-1}\geq\frac{1}{b-1}. Therefore, using Lemma 1 on τ1\tau_1, we have

cost⁡(τ1)≤1a−1∣τ1∣+∑s∈Xs−max⁡(X)\operatorname{cost}(\tau_1)\leq\frac{1}{a-1}|\tau_1|+\sum_{s\in X}s-\max(X)

and using Lemma 1 on τ2\tau_2, we have

cost⁡(τ2)≤1b−1∣τ2∣+∑s∈S\Xs−max⁡(S\X)≤1a−1∣τ2∣+∑s∈S\Xs−max⁡(S\X).\operatorname{cost}(\tau_2)\leq\frac{1}{b-1}|\tau_2|+\sum_{s\in S\backslash X}s-\max(S\backslash X)\leq\frac{1}{a-1}|\tau_2|+\sum_{s\in S\backslash X}s-\max(S\backslash X).

Then,

cost⁡(τ)=∣τ1∣+∣τ2∣+cost⁡(τ1)+cost⁡(τ2)≤(1+1a−1)(∣τ1∣+∣τ2∣)+∑s∈Xs−max⁡(X)+∑s∈S∖Xs−max⁡(S∖X)≤γaa−1(∣τ1∗∣+∣τ2∗∣)+∑s∈Ss−max⁡(S)≤γ⋅aa−1(∣τ1∗∣+∣τ2∗∣+∑s∈Ss−max⁡(S))≤γ⋅aa−1(∣τ1opt∣+∣τ2opt∣+∑s∈Ss−max⁡(S))≤γ⋅aa−1⋅cost⁡(τopt)=γ⋅min⁡(S)min⁡(S)−1⋅OPT⁡(S).\begin{aligned} \operatorname{cost}(\tau) &= |\tau_1| + |\tau_2| + \operatorname{cost}(\tau_1) + \operatorname{cost}(\tau_2) \\ &\le\left(1+\frac{1}{a-1}\right)(|\tau_1|+|\tau_2|)+\sum_{s\in X}s-\max(X)+\sum_{s\in S\setminus X}s-\max(S\setminus X) \\ &\le\gamma\frac{a}{a-1}(|\tau_1^*|+|\tau_2^*|)+\sum_{s\in S}s-\max(S) \\ &\le\frac{\gamma\cdot a}{a-1}\left(|\tau_1^*|+|\tau_2^*|+\sum_{s\in S}s-\max(S)\right) \\ &\le\frac{\gamma\cdot a}{a-1}\left(|\tau_1^{opt}|+|\tau_2^{opt}|+\sum_{s\in S}s-\max(S)\right) \\ &\le\frac{\gamma\cdot a}{a-1}\cdot\operatorname{cost}(\tau^{opt}) \\ &= \frac{\gamma\cdot\min(S)}{\min(S)-1}\cdot\operatorname{OPT}(S). \end{aligned}

The first inequality uses above remarks. The second one is because max⁡(S)\max(S) is either equal to max⁡(X)\max(X) or to max⁡(S∖X)\max(S\setminus X) and by using the assumption that XX is a γ\gamma-approximation of ProdPart on SS. The third one is by observing that γ⋅aa−1≥1\frac{\gamma\cdot a}{a-1}\ge1 and ∑s∈Ss−max⁡(S)≥0\sum_{s\in S}s-\max(S)\ge0. The fourth one is because X∗X^* is an optimal solution of ProdPart and the fifth one is using Lemma 3.

Corollary 4. Let SS be an instance of MultOrd and let τ\tau be a plan following an optimal solution to ProdPart on SS. Then the cost of τ\tau tend to the optimal cost when min⁡(S)\min(S) tends to infinity.

Proof. Let a=min⁡(S)a=\min(S) and using Lemma 10 with γ=1\gamma=1, we have

cost⁡(τ)≤aa−1OPT⁡(S)→a→+∞OPT⁡(S).\operatorname{cost}(\tau)\le\frac{a}{a-1}\operatorname{OPT}(S)\xrightarrow{a\to+\infty}\operatorname{OPT}(S).

Lemma 11. Let SS be an instance of MultOrd and let XX be a subset of SS being worse than or equal to a min⁡(S)min⁡(S)−1\frac{\min(S)}{\min(S)-1}-approximation of ProdPart. Then no plan following XX is optimal.

Proof. Let X∗X^* be a subset of SS being optimal for ProdPart and let τ∗=τ1∗×τ2∗\tau^*=\tau_1^*\times\tau_2^* following X∗X^*. Let τ=τ1×τ2\tau=\tau_1\times\tau_2 following XX. Then,

cost⁡(τ)≥∣τ1∣+∣τ2∣+∑s∈Ss−max⁡(S)≥min⁡(S)min⁡(S)−1(∣τ1∗∣+∣τ2∗∣)+∑s∈Ss−max⁡(S)>min⁡(S)min⁡(S)−1(∣τ1∗∣+∣τ2∗∣)+∑s∈Ss−max⁡(X∗)+∑s∈X∗s−max⁡(X∗)≥∣τ1∗∣+∣τ2∗∣+cost⁡(τ1∗)+cost⁡(τ2∗)=cost⁡(τ∗)=OPT⁡(S).\begin{aligned} \operatorname{cost}(\tau)&\ge|\tau_1|+|\tau_2|+\sum_{s\in S}s-\max(S)\\ &\ge\frac{\min(S)}{\min(S)-1}(|\tau_1^*|+|\tau_2^*|)+\sum_{s\in S}s-\max(S)\\ &>\frac{\min(S)}{\min(S)-1}(|\tau_1^*|+|\tau_2^*|)+\sum_{s\in S}s-\max(X^*)+\sum_{s\in X^*}s-\max(X^*)\\ &\ge|\tau_1^*|+|\tau_2^*|+\operatorname{cost}(\tau_1^*)+\operatorname{cost}(\tau_2^*)\\ &=\operatorname{cost}(\tau^*)\\ &=\operatorname{OPT}(S). \end{aligned}

First inequality uses Lemma 3, second uses the fact that XX is worst or equal to a min⁡(S)min⁡(S)−1\frac{\min(S)}{\min(S)-1}-approximation of ProdPart. The third one uses the assumption that all elements are greater or equal to 2. The fourth inequality uses Lemma 1 on τ1∗\tau_1^* and on τ2∗\tau_2^*.

Lemma 10, Lemma 11, Proposition 9 and the FPTAS algorithm in Theorem 3 highlighted strong connections between MultOrd and ProdPart. Therefore, we introduce the notion of ProdPart-plan, which is a plan following the strategy consisting of splitting the instance using an optimal solution to ProdPart at each step. A direct consequence of Lemma 10 is that every ProdPart-plan are 2-approximation of MultOrd. However, the following proposition contradict optimality of ProdPart-plans.

Proposition 8. ProdPart-plans are not always optimal.

Proof. We highlight a counter example following this logic: Let t≥2t \ge2, c≥2c \ge2 and S={b,…,b,bt−1,bt−1,bt+2}S = \{b,\ldots,b,b^{t}-1,b^{t}-1,b^{t}+2\}, where there are 3t3t occurrences of bb in the instance. So, for t=3t = 3 and b=2b = 2, S={2,2,2,2,2,2,2,2,2,7,7,10}S = \{2,2,2,2,2,2,2,2,2,7,7,10\}. Let τ\tau be the plan following the described strategy. One can check that there is only one optimal solution of ProdPart on SS which is X={bt−1,bt−1,bt+2}X = \{b^{t}-1,b^{t}-1,b^{t}+2\} and S∖XS \setminus X is the set containing all the bb’s. Let X∗={b,…,b,bT−1,bt+2}X^{*} = \{b,\ldots,b,b^{T}-1,b^{t}+2\} containing tt occurrences of bb. Let τ∗\tau^{*} be the plan following X∗X^{*} at first step and then following the most balanced splitting for the subplan. Let τ\tau be the plan following the ProdPart strategy, then τ\tau follows XX. The best valid counter example found is for t=2t = 2 and b=4b = 4. Thus τ∗\tau^{*} is not following the ProdPart plan since its first split is not optimal for ProdPart. In fact, one can check that mS(X)=4096<4320=mS(X∗)m_S(X) = 4096 < 4320 = m_S(X^{*}). One can also check that cost⁡(τ)=8603>8504=cost⁡(τ∗)\operatorname{cost}(\tau) = 8603 > 8504 = \operatorname{cost}(\tau^{*}), which gives a ration of 86038504≃1.0116\frac{8603}{8504} \simeq1.0116. Thus τ\tau is not optimal. The values found here were verified with computers.

Proposition 9. Let S={si}i=1nS = \{s_i\}_{i=1}^{n} be an instance of MultOrd with s1=s2=⋯=sn=ss_1 = s_2 = \cdots= s_n = s. Then we can solve MultOrd in O(nlog⁡n)O(n \log n) time using ProdPart.

Proof. Firstly, we can assume that s≥2s \ge2 since if s=0s = 0 every plan will have a cost of 0 and if s=1s = 1 the optimal plan will be to successively multiply 1 to the smallest other number Proposition 3, namely any other number. Consider the following inductive algorithm:

  1. If n=1n = 1 return the unique plan on a single leaf.

  2. Otherwise, create XX, a subset containing half of the numbers (for instance X={s1,…,s⌈n/2⌉}X = \{s_1,\ldots,s_{\lceil n/2\rceil}\}) and construct a plan τ=τ1×τ2\tau= \tau_1 \times\tau_2 following XX such that τ1\tau_1 (resp. τ2\tau_2) are constructed via this algorithm on the instance XX (resp. S∖XS \setminus X).

We will show that if a plan τ\tau does not split the instance in half then it cannot be optimal. Let X∗X^{*} splitting the instance in half and XX not doing that. Wlog, assume ∣X∗∣≥∣S∖X∗∣|X^{*}| \ge|S \setminus X^{*}| and ∣X∣≥∣S∖X∣|X| \ge|S \setminus X|. Thus ∣X∣>∣X∗∣|X| > |X^{*}|. Therefore, s∣X∣≥s⋅s∣X∗∣s^{|X|} \ge s \cdot s^{|X^{*}|} and thus mS(X)≥s⋅mS(X∗)m_S(X) \ge s \cdot m_S(X^{*}) since ∏s∈Xs=∏s∈X∗s=s∣X∣\prod_{s \in X} s = \prod_{s \in X^{*}} s = s^{|X|}.

Now, note that since all sis_i are equal then X∗X^{*} is the best product partition thus XX is worst or equal to a kk-approximation of ProdPart. Since s≥2s \ge2 and by Lemma 11, every plan not splitting in half the instance is not optimal. Thus, every optimal plan split the instance in half at each step.

The complexity analysis is simple, for an instance of size nn, let T(n)T(n) be the complexity to compute the solution. By induction, T(n)=2T(n2)+nT(n) = 2T(\frac{n}{2}) + n since the cost of creating XX is linear in nn. By the classic master theorem, T(n)=O(nlog⁡n)T(n) = O(n \log n).

Restriction when numbers are powers of a single basis

The NP-hardness proof in [10] uses a reduction where they construct an instance of MultOrd with distinct prime numbers in order to make distinctions between the solutions. In contrast, in this section, we consider the special case of instances with regularity. In particular, we consider instances where all the numbers sis_i are powers of the same base b≥2b \ge2. For instance, for b=4b = 4, an instance could be 45,412,412,44594^5,4^{12},4^{12},4^{459}. Naturally, when numbers sis_i are written in binary, it corresponds to the exponents to be written in unary, which is the case we consider now.

Exponents in unary

Proposition 10. Let b≥4b \ge4 and let S={si}i=1nS = \{s_i\}_{i=1}^{n} be an instance of positive powers of bb, namely, si=bais_i = b^{a_i} with ai>0a_i > 0. Let XX be a partition of the sis_i’s which is not optimal for ProdPart. Then every plan following XX is not optimal.

Proof. Let X∗X^* be an optimal partition of ProdPart and let τ∗=τ1∗×τ2∗\tau^*=\tau_1^*\times\tau_2^* (resp. τ=τ1×τ2\tau=\tau_1\times\tau_2) be a plan following X∗X^* (resp. XX). Wlog, assume ∏s∈X∗s≥∏s∈S∖X∗s\prod_{s\in X^*}s\ge\prod_{s\in S\setminus X^*}s and ∏s∈Xs≥∏s∈S∖Xs\prod_{s\in X}s\ge\prod_{s\in S\setminus X}s. Because b≥2b\ge2 and all ai≥1a_i\ge1, all si≥2s_i\ge2, therefore

OPT⁡(S)≤cost⁡(τ1∗)+cost⁡(τ2∗)+∣τ1∗∣+∣τ2∗∣\operatorname{OPT}(S)\le\operatorname{cost}(\tau_1^*)+\operatorname{cost}(\tau_2^*)+|\tau_1^*|+|\tau_2^*|
≤2(∣τ1∗∣+∣τ2∗∣)+∑s∈X∗s−max⁡(X∗)+∑s∈X∗s−max⁡(X∗)\le2(|\tau_1^*|+|\tau_2^*|)+\sum_{s\in X^*}s-\max(X^*)+\sum_{s\in X^*}s-\max(X^*)
≤4∏s∈X∗s+∑s∈Ss−max⁡(S).\le4\prod_{s\in X^*}s+\sum_{s\in S}s-\max(S).

Second inequality uses Corollary Corollary 2 on τ1∗\tau_1^* and τ2∗\tau_2^*. Since XX is not optimal for ProdPart but X∗X^* is, we have ∏s∈Xs>∏s∈X∗s\prod_{s\in X}s>\prod_{s\in X^*}s, which implies ∏s∈Xs≥b∏s∈X∗s\prod_{s\in X}s\ge b\prod_{s\in X^*}s. Thus

cost⁡(τ)≥∣τ1∣+∣τ2∣+∑s∈Ss−max⁡(S)>∏s∈Xs+∑s∈Ss−max⁡(S)≥b∏s∈X∗s+∑s∈Ss−max⁡(S).\operatorname{cost}(\tau)\ge|\tau_1|+|\tau_2|+\sum_{s\in S}s-\max(S)>\prod_{s\in X}s+\sum_{s\in S}s-\max(S)\ge b\prod_{s\in X^*}s+\sum_{s\in S}s-\max(S).

First inequality uses lemma 3. Then, cost⁡(τ)>OPT⁡(S)\operatorname{cost}(\tau)>\operatorname{OPT}(S). Thus, every plan not following an optimal product partition on the instance are not optimal.

Theorem 4. Let b≥4b\ge4 and let S={s1,…,sn}S=\{s_1,\ldots,s_n\} be an instance of positive power of bb, namely, si=bais_i=b^{a_i} with ai>0a_i>0. Then we can solve MultOrd on SS in polynomial time.

Proof. Consider the following strategy: at each level, find an optimal product partition of the instance and create a plan following it. This strategy is optimal by Proposition 10. Let I(X)I(X) be the set of index of the numbers in XX, namely, I(X)={i∈[n],si∈X}I(X)=\{i\in[n],s_i\in X\}. Then, minimizing wS(X)w_S(X) is the same as minimizing mSm_S by Lemma 8 which is the same as minimizing ∏i∈I(X)si+∏i∈[n]∖I(X)si\prod_{i\in I(X)}s_i+\prod_{i\in[n]\setminus I(X)}s_i which which is the same as minimizing

max⁡(∑i∈I(X)ai,∑i∈[n]∖I(X)ai)\max\left(\sum_{i\in I(X)}a_i,\sum_{i\in[n]\setminus I(X)}a_i\right)

by taking the log. Since the number are given in binary, the exponents aia_i’s are in unary. This is exactly an instance of 2-Partition with input written in unary which is solvable in polytime (see [7]).

Exponents in binary

Now we assume that the exponents are written in binary. For example, in the instance 454^5, 4124^{12}, 4124^{12}, 44594^{459}, the exponents 5, 12, 12, 459 are written in binary. In that case, the problem becomes NP-complete.

Theorem 5. MultOrd when all numbers are power of a base b≥2b\ge2 and exponents written in binary is NP-complete.

Proof. For the NP-membership, the certificate is just a plan τ\tau. For the NP-hardness proof, we reduce 2-Partition to MultOrd. 2-Partition is a problem that takes as input a mutliset of integers A={a1,…,an}A=\{a_1,\ldots,a_n\} and the goal is to determine whether there exists a subset X⊂AX\subset A such that ∑a∈Xa=∑a∈A∖Xa\sum_{a\in X}a=\sum_{a\in A\setminus X}a, it has been proved NP-complete in [7]. Let A={a1,…,an}A=\{a_1,\ldots,a_n\} be an instance of 2-Partition with no zeros and let S=∑a∈AaS=\sum_{a\in A}a. Let S={s1,…,sn}S=\{s_1,\ldots,s_n\} and β=6⋅b32S\beta=6\cdot b^{\frac{3}{2}S} be an instance of MultOrd such that ∀i∈{1,…,n}\forall i\in\{1,\ldots,n\}, si=c3ai≥2s_i=c^{3a_i}\ge2. For all A′⊆AA'\subseteq A, we denote by I(A′)={i∈[n],ai∈A′}I(A')=\{i\in[n],a_i\in A'\}. Let A1,A2⊆AA_1,A_2\subseteq A such that A_1\mathbin{\mathaccent\cdot\cup}A_2=A. Then let τ=τ1×τ2\tau=\tau_1\times\tau_2 a plan following A1A_1. Wlog assume that τ1\tau_1 is a plan on A1A_1 and τ2\tau_2 a plan on A2A_2. If ∑a∈A1a=∑a∈A2a=S2\sum_{a\in A_1}a=\sum_{a\in A_2}a=\frac{S}{2}, thus we have

∣τ1∣≤∏i∈I(A1)si≤b∑i∈I(A1)3ai≤b32S.|\tau_1|\le\prod_{i\in I(A_1)}s_i\le b^{\sum_{i\in I(A_1)}3a_i}\le b^{\frac{3}{2}S}.

Similarly, we have, ∣τ2∣≤c32S|\tau_2|\le c^{\frac{3}{2}S}. Using Proposition 6, we have

cost⁡(τ)≤cost⁡(τ1)+cost⁡(τ2)+∣τ1∣+∣τ2∣≤3(∣τ1∣+∣τ2∣)≤6⋅b32S≤β.\operatorname{cost}(\tau)\le\operatorname{cost}(\tau_1)+\operatorname{cost}(\tau_2)+|\tau_1|+|\tau_2|\le3(|\tau_1|+|\tau_2|)\le6\cdot b^{\frac{3}{2}S}\le\beta.

Otherwise, A1A_1 and A2A_2 are such that ∑a∈A1a≠∑a∈A2a\sum_{a\in A_1} a \ne\sum_{a\in A_2} a. Wlog, we can assume that ∑a∈A1a<∑a∈A2a\sum_{a\in A_1} a < \sum_{a\in A_2} a. So ∑a∈A2a≥S2+1\sum_{a\in A_2} a \ge\frac{S}{2}+1. Thus,

cost⁡(τ)≥∣τ1∣+∣τ2∣≥∣τ2∣≥∏i∈I(A2)si≥b3∑i∈I(A2)ai≥b3(S2+1)≥b3⋅b32S≥8⋅b32S>β.\operatorname{cost}(\tau) \ge|\tau_1| + |\tau_2| \ge|\tau_2| \ge\prod_{i\in I(A_2)} s_i \ge b^{3\sum_{i\in I(A_2)} a_i} \ge b^{3(\frac{S}{2}+1)} \ge b^3 \cdot b^{\frac{3}{2}S} \ge8 \cdot b^{\frac{3}{2}S} > \beta.

Therefore, if there are A1A_1 and A2A_2 satisfying 2-Partition problem, then we have a strategy τ\tau satisfying cost⁡(τ)≤β\operatorname{cost}(\tau) \le\beta. However, if the sets A1,A2A_1,A_2 do not sum to equal value, then any τ\tau will satisfies cost⁡(τ)>β\operatorname{cost}(\tau) > \beta. Thus, 2-Partition reduces to MultOrd with only powers of 2. This concludes the proof. □

Future work

We believe that the bound of Lemma 10 and of Lemma 11 can be improved. We would also like to show that the plan that follows a ProdPart optimal solution at each level achieves a better approximation ratio. Another direction is to address the remaining cases from Proposition 10, when the single basis is 2 or 3.

Moreover, the MultOrd problem is a specific case of the JoinOrdering problem. Therefore, a future direction is to tackle the case of non-Cartesian product. Namely, instead of having as input only the sizes of the relations S={s1,…,sn}S = \{s_1,\ldots,s_n\}, the input is also composed of a list of selectivities {fi,j}1≤i,j≤n\{f_{i,j}\}_{1\le i,j\le n} that determine the sizes of the joins between relation ii and jj divided by the size of the Cartesian product between relation ii and jj. Then the only thing that changes in the problem is the definition of the evaluation of a plan τ=τ1×τ2\tau= \tau_1 \times\tau_2 on SS following XX that become

∣τ∣=(∏i∈I(X)∏j∈[n]∖I(X)fi,j)∣τ1∣⋅∣τ2∣,|\tau| = \left(\prod_{i\in I(X)}\prod_{j\in[n]\setminus I(X)} f_{i,j}\right)|\tau_1|\cdot|\tau_2|,

where I(X)I(X) denotes the set of indices of the elements in XX. However, this simple change makes the problem much harder as the evaluation is not forced to grow with successive multiplications. This generalization was already partially studied in [3], but one could use a different analysis to tackle special cases or specific conditions.

Lastly, one can consider other cost functions known in the literature and/or other abstract operations (in place of multiplication). What are the conditions for our results to still hold?

References

  1. [2]Matthias Bentert, Alex Crane, Pål Grønas Drange, Yosuke Mizutani, and Blair D. Sull-ivan. Structural optimal Jacobian accumulation and minimum edge count are NP-complete under vertex elimination. CoRR, abs/2506.17521, 2025.arxiv.org/abs/2506.17521
  2. [3]Sourav Chatterji, Sai Surya Kiran Evani, Sumit Ganguly, and Mahesh Datt Yemm-anuru. On the complexity of approximate query optimization. In Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 282–292, 2002.
  3. [4]Sophie Cluet and Guido Moerkotte. On the complexity of generating optimal left-deep processing trees with cross products. In Georg Gottlob and Moshe Y. Vardi, editors, Proceedings of the 5th Annual International Conference on Database Theory (ICDT), volume 893, pages 54–67, 1995.DOI
  4. [5]Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani. Algorithms. McGraw-Hill, 2008.
  5. [6]Toshihide Ibaraki and Tiko Kameda. On the optimal nesting order for computing n-relational joins. ACM Trans. Database Syst., 9(3):482–502, 1984.DOI
  6. [7]Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–104. Plenum Press, New York, 1972.
  7. [8]Guido Moerkotte. Building query compilers (manuscript), 2006.
  8. [9]C. T. Ng, M. S. Barketau, T. C. Edwin Cheng, and Mikhail Y. Kovalyov. Product partition and related problems of scheduling and systems reliability: Computational complexity and approximation. Eur. J. Oper. Res., 207(2):601–604, 2010.DOI
  9. [10]Wolfgang Scheufele and Guido Moerkotte. On the complexity of generating optimal plans with cross products. In Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 238–248, 1997.

Paper details

vlnc:W_faqarcc6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents