Optimization Methods
This chapter proposes to use the low-polynomial cost approximation method presented in (Bar-Yehuda, 2001) to solve the DBW minimization problem and proposes to use L 2 to approximate g(L 2) (as defined in Section 3.1 of Chapter 3) to solve the AT Data Sep optimization problem.
Abstract
As discussed in Section 4.3 of Chapter 4, our problem of minimizing the total query cost is related to the graph Minimum Linear Arrangement problem (MinLA). The graph MinLA problem is a well-studied problem and several efficient approximation methods have been proposed (Bar-Yehuda, 2001; Koren, 2002). By extending an edge of (u,v) to a hyperedge {n 1 ,n 2 ..n k } and defining the " edge length " of a hyperedge length as L 2 =) } (),... (), (min{)} (),... (), (max{ 2 1 2 1 k k n n n n n n π π π π π π − , the problem of minimizing DBW is essentially the same as the hypergraph MinLA problem. We want to use the existing efficient MinLA approximation methods to solve our geographical data broadcast sequencing problem. In this chapter we propose to use the low-polynomial cost approximation method presented in (Bar-Yehuda, 2001) to solve the DBW minimization problem. We then propose to use L 2 to approximate g(L 2) (as defined in Section 3.1 of Chapter 3) to solve the AT Data Sep optimization problem. An novel approach is developed to optimize AT Data Mul. For the rest of this chapter, we first briefly introduce the algorithm of (Bar-Yehuda, 2001) and we then prove the correctness of using this algorithm for hypergraphs. We show the importance of generating the Binary Decomposition Tree (BDT) (Bar-Yehuda, 2001) and propose to use R-Tree as the basis for generating a 91