Narrow Results

We investigate the shortest common superstring problem (SCSSP). As SCSSP is APX-complete it cannot be approximated within an arbitrarily small performance ratio. One heuristic that is widely used is the notorious greedy heuristic. It is known, that the performance ratio of this heuristic is at least 2 and not worse than 4. It is conjectured that the greedy heuristic's performance ratio is in fact 2 (the greedy conjecture). Even the best algorithms introduced for SCSSP can only guarantee an upper bound of 2.5. In [11] an even stronger version of the greedy conjecture is proven for a restricted class of orders in which strings are merged. We extend these results by broadening the class for which this stronger version can be established. We also show that the Triple inequality, introduced in [11] and crucial for their results, is inherently insufficient to carry the proof for the greedy conjecture in the general case. Finally we describe how linear programming can be used to support research along this line.

A connected dominating set (CDS, for short) for graph G is a dominating set which induces a connected subgraph of G. In this paper, we consider the problem of finding a minimum CDS for unit disk graphs, which have recently attracted considerable attention as a model of virtual backbone in multi-hop wireless networks. This optimization problem is known to be NP-hard and many approximation algorithms have been proposed in the literature. This paper proves a lower bound on the performance ratio of a greedy algorithm of Guha and Khuller which was originally proposed for general graphs and is known to be a representative in which the lookahead plays a crucial role in selecting a vertex to be contained in the CDS. More specifically, we show that for any fixed $\epsilon >0$ and integer $n_0\ge 1$, there is a unit disk graph with bounded degree consisting of at least $n_0$ vertices for which the output of the greedy algorithm is no better than $3-\epsilon$ times of an optimum solution to the same graph.

The problem of nonpreemptively scheduling a set of n independent jobs with identical release times so as to minimize the number of late jobs is considered. It is known that the problem can be solved in O(n log n) time, by an algorithm due to Moore, for a single processor, and that it becomes NP-hard for two or more identical processors, even if all jobs have identical due dates. In this paper we give a fast heuristic, based on Moore’s algorithm, for the multiprocessor case. Like Moore’s algorithm, our heuristic also admits an O(n log n) implementation. It is shown that the performance ratio of the heuristic is 4/3 for two identical processors, where the performance ratio is defined to be the least upper bound of the ratio of the number of on-time jobs in an optimal schedule versus that in the schedule generated by the heuristic.

We consider a non-preemptive single machine scheduling problem with forbidden intervals. Associated with each job is a given processing time and a delivery time to its customer, when the processing of the job is complete. The objective is to minimize the time taken for all the jobs to be delivered to the customers. The problem is strongly NP-hard in general. In this study, we show that the case with a fixed number of forbidden intervals can be solved by a pseudo-polynomial time algorithm, while no polynomial time approximation algorithm with a fixed performance ratio exists for the case with two forbidden intervals. We also develop a polynomial time approximation scheme (PTAS) for the case with a single forbidden interval.

We consider the portfolio selection problem of maximizing a performance measure in a continuous-time diffusion model. The performance measure is the ratio of the overperformance to the underperformance of a portfolio relative to a benchmark. Following a strategy from fractional programming, we analyze the problem by solving a family of related problems, where the objective functions are the numerator of the original problem minus the denominator multiplied by a penalty parameter. These auxiliary problems can be solved using the martingale method for stochastic control. The existence of solution is discussed in a general setting and explicit solutions are derived when both the reward and the penalty functions are power functions.

In this paper, we consider the single machine scheduling problem with inventory operations. The objective is to minimize makespan subject to the constraint that the total number of tardy jobs is minimum. We show the problem is strongly NP-hard. A polynomial -approximation scheme for the problem is presented, where m is defined as the total job's processing times ∑ p_j divided by the capacity c of the storage, and an optimal algorithm for a special case of the problem, in which each job is one unit in size.

In a (full) set multicover (SMC) problem, the goal is to select a subcollection of sets to fully cover all elements, where an element is fully covered if it belongs to at least a required number of sets of the selected subcollection. In a partial set multicover (PSMC) problem, it is sufficient to fully cover a required fraction of elements. In this paper, we present a greedy algorithm for PSMC, and analyze the ratio between the cost of the computed solution and the cost of an optimal solution to the corresponding (full) SMC problem. We shall call this ratio as a partial-versus-full ratio. The motivation for such an analysis is to show that PSMC is fairly economic even when it can only be calculated approximately. It turns out that the partial-versus-full ratio of our algorithm is at most $ln\frac{r}{1-\rho }$, where $r$ is the requirement of an element, and $\rho$ is the fraction of elements required to be fully covered. An example is given showing that this ratio is tight up to a constant.

In this paper, we provide the implications of using the performance ratio being defined by the expected shortfall-well known as RAROC-in static portfolio optimization, by giving the proof of the relevant results. We also use RAROC as a primary function in the AUGMECON algorithm, providing the main scheme of such an application on data from Athens Stock Exchange. The use of RAROC in AUGMECON as a primary function is also faced as an optimization problem under a general nonconvex optimization framework.