Browsing by Subject "approximation algorithms"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item On Discrete Hyperbox Packing(2010-01-14) Li, XiafengBin packing is a very important and popular research area in the computer science field. Past work showed many good and real-world packing algorithms. How- ever, due to the complexity of the problem in multiple-dimensional bin packing, also called hyperbox packing, we need more practical packing algorithms for its real-world applications. In this dissertation, we extend 1D packing algorithms to hyperbox packing prob- lems via a general framework that takes two inputs of a 1D packing algorithm and an instance of hyperbox packing problem and outputs a hyperbox packing algorithm. The extension framework significantly enriches the family of hyperbox-packing algorithms, generates many framework-based algorithms, and simultaneously calls for the analysis for those algorithms. We also analyze the performance of a couple of framework-based algorithms from two perspectives of worst-case performance and average-case performance. In worst- case analysis, we use the worst-case performance ratio as our metric and analyze the relationship of the ratio of framework-based algorithms and that of the corresponding 1D algorithms. We also compare their worst-case performance against two baselines: strip optimal algorithms and optimal algorithms. In average-case analysis, we use expected waste as a metric, analyze the waste of optimal hyperbox packing algorithms, and estimate the asymptotic forms of the waste for framework-based algorithms.Item Optimization in Geometric Graphs: Complexity and Approximation(2011-02-22) Kahruman-Anderoglu, SeraWe consider several related problems arising in geometric graphs. In particular, we investigate the computational complexity and approximability properties of several optimization problems in unit ball graphs and develop algorithms to find exact and approximate solutions. In addition, we establish complexity-based theoretical justifications for several greedy heuristics. Unit ball graphs, which are defined in the three dimensional Euclidian space, have several application areas such as computational geometry, facility location and, particularly, wireless communication networks. Efficient operation of wireless networks involves several decision problems that can be reduced to well known optimization problems in graph theory. For instance, the notion of a \virtual backbone" in a wire- less network is strongly related to a minimum connected dominating set in its graph theoretic representation. Motivated by the vastness of application areas, we study several problems including maximum independent set, minimum vertex coloring, minimum clique partition, max-cut and min-bisection. Although these problems have been widely studied in the context of unit disk graphs, which are the two dimensional version of unit ball graphs, there is no established result on the complexity and approximation status for some of them in unit ball graphs. Furthermore, unit ball graphs can provide a better representation of real networks since the nodes are deployed in the three dimensional space. We prove complexity results and propose solution procedures for several problems using geometrical properties of these graphs. We outline a matching-based branch and bound solution procedure for the maximum k-clique problem in unit disk graphs and demonstrate its effectiveness through computational tests. We propose using minimum bottleneck connected dominating set problem in order to determine the optimal transmission range of a wireless network that will ensure a certain size of "virtual backbone". We prove that this problem is NP-hard in general graphs but solvable in polynomial time in unit disk and unit ball graphs. We also demonstrate work on theoretical foundations for simple greedy heuristics. Particularly, similar to the notion of "best" approximation algorithms with respect to their approximation ratios, we prove that several simple greedy heuristics are "best" in the sense that it is NP-hard to recognize the gap between the greedy solution and the optimal solution. We show results for several well known problems such as maximum clique, maximum independent set, minimum vertex coloring and discuss extensions of these results to a more general class of problems. In addition, we propose a "worst-out" heuristic based on edge contractions for the max-cut problem and provide analytical and experimental comparisons with a well known "best-in" approach and its modified versions.