Approximation Algorithms

In this paper we present a polynomial time algorithm for computing a Hausdorff core of a polygon with a single reflex vertex.  A Hausdorff core of a polygon $P$ is a convex polygon $Q$ contained inside $P$ which minimizes the Hausdorff distance between $P$ and $Q$.  Our algorithm essentially consists of rotating a line about the reflex vertex; this line defines a convex polygon by cutting $P$.  To determine the angle at which the line should be rotated, our algorithm searches for a global minimum on the upper envelope of $n$ continuous piecewise functions, where $n$ is the number of vertices of $P$.

Explicitly model sources as AR processes, transform the MMV model into a block-sparsity model, and then derive the AR-SBL algorithms in the sparse Bayesian learning framework. Super recovery performance than existing MMV algorithms is observed when sources have high temporal correlation.

We study the off and on-line versions of the well known problem of scheduling a set of n independent multiprocessor tasks with prespecified processor allocations on a set of identical processors in order to minimize the makespan. Recently, in [12], it has been proven that in the case when all tasks have unit processing time the problem cannot be approximated within a factor of m 1– ∈, neither for some ∈ > 0, unless P= NP; nor for any ∈ > 0, unless NP=ZPP. For this special case we give a simple algorithm based on the classical first-fit technique. We analyze the algorithm for both tasks arrive over time and tasks arrive over list on-line scheduling versions, and show that its competitive ratio is bounded by 2√m and 2√m + 1, respectively. Here we also use some preliminary results on (vertex) coloring of k-tuple graphs. For the case of arbitrary processing times, we show that any algorithm which uses the first-fit technique cannot be better than m competitive. Then, by using our split-round technique, we give a 3√m-approximation algorithm for the off-line version of the problem. Finally, by using some ideas from [20], we adapt the algorithm to the on-line case, in the paradigm of tasks arriving over time in which the existence of a task is unknown until its release date, and show that its competitive ratio is bounded by 6√m. Due to the conducted experimental results, we conclude that our algorithms can perform well in practice.

A typical polling system consists of a number of queues, attended by a single server in a fixed order. The present study derives closed-form approximations for the mean waiting times and mean marginal queue lengths of polling systems with renewal arrival processes, which can be computed by simple calculations. The results of the present research may be very suitable for the design and optimisation phase in many application areas, such as telecommunication, maintenance, manufacturing and transportation.

_____________________________________________
Boon, M.A.A., Winands, E.M.M., Adan, I.J.B.F., Wijk, A.C.C. van (2009). Closed-form waiting time approximations for polling systems,
Performance Evaluation, Volume 68, Issue 3, March 2011, Pages 290-306.

In this paper we consider a single-server, cyclic polling system with switch-over times. A distinguishing feature of the model is that the rates of the Poisson arrival processes at the various queues depend on the server location. For this model we study the joint queue length distribution at polling epochs and departure epochs. We also study the marginal queue length distribution at arrival epochs, as well as at arbitrary epochs (which is not the same in general, since we cannot use the PASTA property). A generalised version of the distributional form of Little’s law is applied to the joint queue length distribution at departure epochs in order to find the waiting time distribution for each customer type. We also provide an alternative, more efficient way to determine the mean queue lengths and mean waiting times, using Mean Value Analysis. Furthermore, we show that under certain conditions a Pseudo-Conservation Law for the total amount of work in the system holds. Finally, typical features of the model under consideration are demonstrated in several numerical examples.

_____________________________________________
Boon, M.A.A., Wijk, A.C.C. van, Adan, I.J.B.F., Boxma, O.J. (2009). A polling model with smart customers,
Queueing Systems, 2010, Volume 66, Number 3, Pages 239-274.

Given a set  D of m unit disks and a set P of n points in the plane,
the discrete unit disk cover problem is to select a minimum cardinality subset D'\subseteq D to cover P.
This problem is NP-hard and the best previous practical solution is a 38-approximation algorithm by Carmi et al. We first consider the line-separable discrete unit disk cover problem (the set of disk centers can be separated from the set of points by a line) for which we present an O(n(log n+m))-time algorithm that finds an exact solution. Combining our line-separable algorithm with
techniques from the algorithm of Carmi et al. results in an O(m^2n^4) time 22-approximate solution to the discrete unit disk cover problem.

Broadband wireless channel is a time dispersive channel and become strongly frequency-selective. However, in most cases, the channel is composed of a few dominant taps and a large part of approximate zero taps or zero. To exploit the sparsity of multi-path channel (MPC), two methods have been proposed. They are, namely, greedy algorithm and convex program. Greedy algorithm is easy to be implemented but not stable; on the other hand, the convex program method is stable but difficult to be implemented as practical channel estimation problems. In this paper, we introduce a novel channel estimation strategy using compressive sampling matching pursuit (CoSaMP) algorithm which was proposed in [1]. This algorithm will combine the greedy algorithm with the convex program method. The effectiveness of the proposed algorithm will be confirmed through comparisons with the existing methods.

Cognitive radio is an enabling technology for efficient utilization
of radio spectrum. In this paper, an orthogonal frequency division multiple access (OFDMA) based cognitive (opportunistic) network is considered, which co-exists with a macrocell network through utilizing its unused subcarriers.
We particularly consider the uplink opportunity detection problem by the opportunistic network, where accurate synchronization to the macrocell network is crucial for minimizing the interference received from the macrocell users. After demonstrating the impact of synchronization on the inter-carrier-interference (ICI) observed at the opportunistic network, an improved blind first-user synchronization technique is proposed, and its statistics are analyzed. Through computer simulations it is shown that the proposed technique yields
less interference and better opportunities for the opportunistic network.

When using images to locate objects, there is the problem of correcting for distortion and misalignment in the images. An elegant way of solving this problem is to generate an error correcting function that maps points in an image to their corrected locations. We generate such a function by fitting a polynomial to a set of sample points. The objective is to identify a polynomial that passes "sufficiently close" to these points with "good" approximation of intermediate points. In the past, it has been difficult to achieve good global polynomial approximation using only sample points. We report on the development of a global polynomial approximation algorithm for solving this problem. Key Words: Polynomial approximation, interpolation, image rectification.

Given a simple polygon P, we consider the problem of finding a convex polygon Q contained in P that minimizes H(P;Q), where H denotes the Hausdorff distance. We call such a polygon Q a Hausdorff core of P. We describe polynomial-time approximations for both the minimization and decision versions of the Hausdorff core problem, and we provide an argument supporting the hardness of the problem.

We are interested in the problem of satisfying a maximum-profit subset of undirected communication requests in an optical ring that uses the Wavelength Division Multiplexing technology. We present four deterministic and purely combinatorial algorithms for this problem, and give theoretical guarantees for their worst-case approximation ratios. Two of these algorithms are novel, whereas the rest are adaptation of earlier approaches. An experimental evaluation of the algorithms in terms of attained profit and execution time reveals that the theoretically best algorithm performs only marginally better than one of the new algorithms, while at the same time being several orders of magnitude slower. Furthermore, an extremely fast greedy heuristic with nonconstant approximation ratio performs reasonably well and may be favored over the other algorithms whenever it is crucial to minimize execution time.

We show that for $k \geq 3$ even the Omega(n) level of the Lasserre hierarchy cannot disprove a random k-CSP instance over any predicate type implied by k-XOR constraints, for example k-SAT or k-XOR. (One constant is said to imply another if the latter is true whenever the former is. For example k-XOR constraints imply k-CNF constraints.) As a result the Omega(n) level Lasserre relaxation fails to approximate such CSPs better than the trivial, random algorithm. As corollaries, we obtain Omega(n) level integrality gaps for the Lasserre hierarchy of $7/6 - epislon$ for VertexCover, 2-epsilon for k-UniformHypergraphVertexCover, and any constant for k-UniformHypergraphIndependentSet. This is the first construction of a Lasserre integrality gap.

Our construction is notable for its simplicity. It simplifes, strengthens, and helps to explain several previous results.

A fundamental challenge in Internet computing (IC) is to efficiently schedule computations having complex interjob dependencies, given the unpredictability of remote machines, in availability and time of access. The recent IC Scheduling theory focuses on these sources of unpredictability by crafting schedules that maximize the number of executable jobs at every point in time. In this paper, we experimentally investigate the key question: does IC Scheduling yield significant positive benefits for real IC? To this end, we develop a realistic computation model to match jobs to client machines and conduct extensive simulations to compare IC-optimal schedules against popular, intuitively compelling heuristics. Our results suggest that for a large range of computation-dags, client availability patterns, and two quite different performance metrics, IC-optimal schedules significantly outperform schedules produced by popular heuristics, by as much as 10-20%.

Recently a classifier was proposed that was based on the assumption: the training samples for a particular class form a linear basis for any new test sample. This assumption is a generalization of the Nearest Neighbour classifier. In the previous work, the classifier was built upon this assumption
required solving a complex optimisation problem. The optimisation method was time consuming and restrictive in application. In this work our proposed algorithm takes care of the previous problems keeping the basic assumption
intact. We also offer generalisations of the basic assumption. Comparative experimental results on some UCI machine learning databases show that our proposed generalised classifier is performs as good as other well known
techniques like Nearest Neighbour and Support Vector Machine.

We study the survivable network design problem (SNDP) for vertex connectivity. Given a graph G(V, E) with costs on edges, the goal of SNDP is to find a minimum cost subset of edges that ensures a given set of pairwise vertex connectivity requirements. When all connectivity requirements are between a special vertex, called the source, and vertices in a subset T ⊆ V , called terminals, the problem is called the single-source SNDP. Our main result is a randomized k O(k 2 ) log 4 n-approximation algorithm for single-source SNDP where k denotes the largest connectivity requirement for any source-terminal pair. In particular, we get a polylogarithmic approximation for any constant k. Prior to our work, no non-trivial approximation guarantees were known for this problem for any k ≥ 3. We also show that SNDP is k Ω(1) -hard to approximate and provide an elementary construction that shows that the well-studied set-pair linear programming relaxation for this problem has anΩ(k 1/3 ) integrality gap.

In this paper we investigate the problem of searching for a hidden target in a bounded region of the plane, by an autonomous robot which is only able to use limited local sensory information. We formalize a discrete version of the problem as a "reward-collecting" path problem and provide efficient approximation algorithms for various cases.

Given an object with n points on its boundary where ngers can be placed, we give algorithms to select a \strong" grasp with the least number c of ngers (up to a logarithmic factor) using several measures of goodness. Along similar lines, given an integer c, we nd the \best" c logc nger grasp for a small constant . In addition, we generalize existing measures for the case of frictionless assemblies of many objects in contact. We also give an approximation scheme which guarantees a grasp quality close to the overall optimal value where ngers are not restricted to preselected points. These problems translate into a collection of convex set covering problems where we either minimize the cover size or maximize the scaling factor of an inscribed geometric object L. We present an algorithmic framework which handles these problems in a uniform way and give approximation algorithms for speci c instances of L including convex polytopes and balls. The framework generalizes an algorithm for polytope covering and approximation by Clarkson Cla93] in two di erent ways. Let = 1=bd=2c, where d is the dimension of the Euclidean space containing L. For both types of problems, when L is a polytope, we get the same expected time bounds (with a minor improvement), and for a ball, the expected running time is O(n 1+ + (nc) 1=(1+ =(1+ )) + c log(n=c)(c logc) bd=2c ) for xed d, and arbitrary positive . We improve this bound if we allow in addition a di erent kind of approximation for the optimal radius. We also give bounds when d is not a constant.

We consider the problem of optimal multicast routing with Quality of Service constraints motivated by the requirements of interactive continuous media communication, e.g., real-time teleconferencing. We concentrate on distributed algorithms for determining a tree over the network topology, rooted at the source and spanning the intended destinations. Quality of Service requirements for interactive continuous media typically impose constraints on some metric over the individual paths from the source to each destination, usually in the form of an upper bound on the delay. Thus, we focus on the problem of minimizing the cost of the tree while at the same time satisfying a common constraint over individual source-destination paths. We have shown that this problem is intractable, but have also devised centralized polynomial time heuristics that perform well. Here we present distributed algorithms to minimize tree cost while satisfying the constraints on the paths from the source to each destination.

In this paper, we show that in the best-known version of the blocks world (and several related versions), planning is di cult, in the sense that nding an optimal plan is NP-hard. However, the NP-hardness is not due to deleted-condition interactions, but instead due to a situation which we call a deadlock. For problems that do not contain deadlocks, there is a simple hill-climbing strategy that can easily nd an optimal plan, regardless of whether or not the problem contains any deleted-condition interactions.

We consider the one-dimensional bin packing problem under the discrete uniform distributions U {j, k}, 1 ≤ j ≤ k − 1, in which the bin capacity is k and item sizes are chosen uniformly from the set {1, 2, . . . , j}. Note that for 0 < u = j/k ≤ 1 this is a discrete version of the previously studied continuous uniform distribution U (0, u], where the bin capacity is 1 and item sizes are chosen uniformly from the interval (0, u]. We show that the average-case performance of heuristics can differ substantially between the two types of distributions. In particular, there is an online algorithm that has constant expected wasted space under U {j, k} for any j, k with 1 ≤ j < k − 1, whereas no online algorithm can have o(n 1/2 ) expected waste under U (0, u] for any 0 < u ≤ 1. Our U {j, k} result is an application of a general theorem of Courcoubetis and Weber that covers all discrete distributions. Under each such distribution, the optimal expected waste for a random list of n items must be either Θ(n), Θ(n 1/2 ), or O(1), depending on whether certain "perfect" packings exist. The perfect packing theorem needed for the U {j, k} distributions is an intriguing result of independent combinatorial interest, and its proof is a cornerstone of the paper. We also survey other recent results comparing the behavior of heuristics under discrete and continuous uniform distributions.

Many combinatorial optimization problems aim to select a subset of elements of maximum value subject to certain constraints. We consider an incremental version of such problems, in which some of the constraints rise over time. A solution is a sequence of feasible solutions, one for each time step, such that later solutions build on earlier solutions incrementally. We introduce a general model for such problems, and define incremental versions of maximum flow, bipartite matching, and knapsack. We find that imposing an incremental structure on a problem can drastically change its complexity. With this in mind, we give general yet simple techniques to adapt algorithms for optimization problems to their respective incremental versions, and discuss tightness of these adaptations with respect to the three aforementioned problems.

Traditional optimization algorithms are concerned with static input, static constraints, and attempt to produce static output of optimal value. Recent literature has strayed from this conventional approach to deal with more realistic situations in which the input changes over time. Incremental optimization is a new framework for handling this type of dynamic behavior. We consider a general model for producing incremental versions of traditional covering problems along with several natural incremental metrics. Using this model, we demonstrate how to convert conventional algorithms into incremental algorithms with only a constant factor loss in approximation power. We introduce incremental versions of min cut, edge cover, and (k, r)-center and present some hardness results. Lastly, we discuss how the incremental model can help us more fully understand online problems and their corresponding algorithms.

Given a graph G = (V, E), a (d, k)-coloring is a function from the vertices V to colors {1, 2, . . . , k} such that any two vertices within distance d of each other are assigned different colors. We determine the complexity of the (d, k)-coloring problem for all d and k, and enumerate some interesting properties of (d, k)-colorable graphs. Our main result is the discovery of a dichotomy between polynomial and NP-hard instances: for fixed d ≥ 2, the distance coloring problem is polynomial time for k ≤ 3d 2 and NP-hard for k > 3d 2 .

An algorithm for a typical combinatorial optimization problem is given static input, and finds a single solution. Incremental optimization is one framework for handling problems that require solutions to be built up over time due to evolving constraints. An incremental algorithm is given a sequence of input, and finds a sequence of solutions that build incrementally while adapting to the changes in the input. Online algorithms also take in a sequence of input and produce incremental solutions; unlike their incremental counterparts, however, they are not given the input sequence in advance. Thus two factors can affect the competitive ratio of an online problem: that it does not know the input sequence in advance, and that it makes irreversible decisions. Both factors contribute to an algorithm's performance, but the competitive ratio fails to discern which is more significant. Incremental problems are only affected by the second factor, however, thus we can use incremental results to better understand online algorithms and improve their performance.

A typical algorithm for a combinatorial optimization problem is given a static set of input, and finds a single solution. This kind of algorithm cannot be used, however, in situations where the input and solutions change over time due to evolving constraints. This dissertation explores incremental problems, one class of optimization problems that deals with this type of situation. An incremental algorithm is given a sequence of input, and finds a sequence of solutions that build incrementally while adapting to the changes in the input.

: Frames from the Treasure Chest animation. The chest contains a TensorTexture mapped onto a planar surface, which appears to have considerable 3D relief when viewed from various directions (images 1-3) and under various illuminations (images 3-5).