No description available.

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

No description available.

Graph-partitioning problems are a central topic of research in the study of algorithms and complexity theory. They are of interest to theoreticians with connections to error correcting codes, sampling algorithms, metric embeddings, among others, and to practitioners, as algorithms for graph partitioning can be used as fundamental building blocks in many applications. One of the central problems studied in this field is the sparsest cut problem, where we want to compute the cut which has the least ratio of number of edges cut to size of smaller side of the cut. This ratio is known as the expansion of the cut. In spite of over 3 decades of intensive research, the approximability of this parameter remains an open question. The study of this optimization problem has lead to powerful techniques for both upper bounds and lower bounds for various other problems, and interesting conjectures such as the SSE conjecture. Cheeger's Inequality, a central inequality in Spectral Graph Theory, establishes a bound on expansion via the spectrum of the graph. This inequality and its many (minor) variants have played a major role in the design of algorithms as well as in understanding the limits of computation. In this thesis we study three notions of expansion, namely edge expansion in graphs, vertex expansion in graphs and hypergraph expansion. We define suitable notions of spectra w.r.t. these notions of expansion. We show how the notion Cheeger's Inequality goes across these three problems. We study higher order variants of these notions of expansion (i.e. notions of expansion corresponding to partitioning the graph/hypergraph into more than two pieces, etc.) and relate them to higher eigenvalues of graphs/hypergraphs. We also study approximation algorithms for these problems. Unlike the case of graph eigenvalues, the eigenvalues corresponding to vertex expansion and hypergraph expansion are intractable. We give optimal approximation algorithms and computational lower bounds for computing them.

Thesis (M.S.)--University of North Texas, Dec., 2009. / Title from title page display. Includes bibliographical references.

We give a 2-approximation algorithm for Cluster Vertex Deletion. This tight result matches the hardness lower bound. We obtain a new deterministic 7/3-approximation algorithm for Feedback Vertex Set in Tournaments. This result is based on the LP given by just one round of Sherali-Adams. We find a new, simpler deterministic (2 + epsilon)-approximation algorithm for Split Vertex Deletion. We give a 2-approximation algorithm for Claw-Free Vertex Deletion in triangle-free graphs. In the case of general graphs we prove that it is UGC-hard to obtain an approximation ratio lower than 3. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

We present a constant-factor approximation algorithm for computing an embedding of the shortest path metric of an unweighted graph into a tree, that minimizes the multiplicative distortion.

We present a constant-factor approximation algorithm for computing anembedding of the shortest path metric of an unweighted graph into atree, that minimizes the multiplicative distortion.

This thesis will address several problems in discrete optimization. These problems are considered hard to solve. However, good approximation algorithms for these problems may be helpful in approximating problems in computational biology and computer science. Given an undirected graph G=(V,E) and a family of subsets of vertices S, the minimum crossing spanning tree is a spanning tree where the maximum number of edges crossing any single set in S is minimized, where an edge crosses a set if it has exactly one endpoint in the set. This thesis will present two algorithms for special cases of minimum crossing spanning trees. The first algorithm is for the case where the sets of S are pairwise disjoint. It gives a spanning tree with the maximum crossing of a set being 2OPT+2, where OPT is the maximum crossing for a minimum crossing spanning tree. The second algorithm is for the case where the sets of S form a laminar family. Let b_i be a bound for each S_i in S. If there exists a spanning tree where each set S_i is crossed at most b_i times, the algorithm finds a spanning tree where each set S_i is crossed O(b_i log n) times. From this algorithm, one can get a spanning tree with maximum crossing O(OPT log n). Given an undirected graph G=(V,E), and a family of subsets of vertices S, the minimum crossing perfect matching is a perfect matching where the maximum number of edges crossing any set in S is minimized. A proof will be presented showing that finding a minimum crossing perfect matching is NP-hard, even when the graph is bipartite and the sets of S are pairwise disjoint.

We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is called Contact Representation of Word Networks (Crown) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Crown is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, Max-Crown, in which realizing each desired adjacency yields a certain profit. We present the first O(1)-approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. Since the subgraph of realized adjacencies is necessarily planar, we also consider several planar graph classes (namely stars, trees, outerplanar, and planar graphs), improving upon the known results. For some graph classes, we also describe improvements in the unweighted case, where each adjacency yields the same profit. Finally, we show that the problem is APX-complete on bipartite graphs of bounded maximum degree.