1 
Linear Time Approximation of 3D Convex PolytopesMario A. Lopez, Shlomo Reisner, reisner@math.haifa.ac.il 05 March 2001 (has links)
No description available.

2 
On Discrete Hyperbox PackingLi, Xiafeng 14 January 2010 (has links)
Bin packing is a very important and popular research area in the computer
science field. Past work showed many good and realworld packing algorithms. How
ever, due to the complexity of the problem in multipledimensional bin packing, also
called hyperbox packing, we need more practical packing algorithms for its realworld
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 hyperboxpacking algorithms, generates many frameworkbased algorithms, and simultaneously calls for the
analysis for those algorithms.
We also analyze the performance of a couple of frameworkbased algorithms from
two perspectives of worstcase performance and averagecase performance. In worst
case analysis, we use the worstcase performance ratio as our metric and analyze the
relationship of the ratio of frameworkbased algorithms and that of the corresponding
1D algorithms. We also compare their worstcase performance against two baselines:
strip optimal algorithms and optimal algorithms. In averagecase 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 frameworkbased algorithms.

3 
Approximation techniques for unsplittable flow and traveling salesmen problemsFriggstad, Zachary Unknown Date
No description available.

4 
The complexity of expansion problemsLouis, Anand 27 August 2014 (has links)
Graphpartitioning 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.

5 
Survey of approximation algorithms for set cover problemDutta, Himanshu Shekhar. Shahrokhi, Farhad M., January 2009 (has links)
Thesis (M.S.)University of North Texas, Dec., 2009. / Title from title page display. Includes bibliographical references.

6 
Two Approaches to Approximation Algorithms for Vertex Deletion ProblemsDrescher, Matthew 15 November 2021 (has links) (PDF)
We give a 2approximation algorithm for Cluster Vertex Deletion. This tight result matches the hardness lower bound. We obtain a new deterministic 7/3approximation algorithm for Feedback Vertex Set in Tournaments. This result is based on the LP given by just one round of SheraliAdams. We find a new, simpler deterministic (2 + epsilon)approximation algorithm for Split Vertex Deletion. We give a 2approximation algorithm for ClawFree Vertex Deletion in trianglefree graphs. In the case of general graphs we prove that it is UGChard to obtain an approximation ratio lower than 3. / Doctorat en Sciences / info:eurepo/semantics/nonPublished

7 
A ConstantFactor Approximation Algorithm for Embedding Unweighted Graphs into TreesBadoiu, Mihai, Indyk, Piotr, Sidiropoulos, Anastasios 05 July 2004 (has links)
We present a constantfactor approximation algorithm for computing an embedding of the shortest path metric of an unweighted graph into a tree, that minimizes the multiplicative distortion.

8 
A ConstantFactor Approximation Algorithm for Embedding Unweighted Graphs into TreesBadoiu, Mihai, Indyk, Piotr, Sidiropoulos, Anastasios 05 July 2004 (has links)
We present a constantfactor approximation algorithm for computing anembedding of the shortest path metric of an unweighted graph into atree, that minimizes the multiplicative distortion.

9 
Minimum Crossing Problems on GraphsRoh, Patrick January 2007 (has links)
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 NPhard, even when the graph is bipartite and the sets of S are pairwise disjoint.

10 
Improved Approximation Algorithms for Box Contact RepresentationsBekos, Michael A., van Dijk, Thomas C., Fink, Martin, Kindermann, Philipp, Kobourov, Stephen, Pupyrev, Sergey, Spoerhase, Joachim, Wolff, Alexander 27 January 2016 (has links)
We study the following geometric representation problem: Given a graph whose vertices correspond to axisaligned 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 NPhard, and there are approximation algorithms for certain graph classes for the optimization version, MaxCrown, 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 APXcomplete on bipartite graphs of bounded maximum degree.

Page generated in 0.1468 seconds