Computing Optimal Beams in Two and Three Dimensions

The problem of computing an optimal beam among weighted regions (called the optimal beam problem) arises in several applied areas such as radiation therapy, stereotactic brain surgery, medical surgery, geological exploration, manufacturing, and environmental engineering. In this paper, we present computational geometry techniques that enable us to develop efficient algorithms for solving various optimal beam problems among weighted regions in two and three dimensional spaces. In particular, we consider two types of problems: the covering problems (seeking an optimal beam to contain a specified target region), and the piercing problems (seeking an optimal beam of a fixed shape to pierce the target region). We investigate several versions of these problems, with a variety of beam shapes and target region shapes in 2-D and 3-D. Our algorithms are based on interesting combinations of computational geometry techniques and optimization methods, and transform the optimal beam problems to solving a collection of instances of certain special non-linear optimization problems. Our approach makes use of interesting geometric observations, such as utilizing some new features of Minkowski sums.     

Efficient Algorithms and Implementations for Optimizing the Sum of Linear Fractional Functions,with Applications

This paper presents an improved algorithm for solving the sum of linear fractional functions (SOLF) problem in 1-D and 2-D. A key subproblem to our solution is the off-line ratio query (OLRQ) problem, which asks to find the optimal values of a sequence of m linear fractional functions (called ratios), each ratio subject to a feasible domain defined by O(n) linear constraints. Based on some geometric properties and the parametric linear programming technique, we develop an algorithm that solves the OLRQ problem in O((m+n)log (m+n)) time. The OLRQ algorithm can be used to speed up every iteration of a known iterative SOLF algorithm, from O(m(m+n)) time to O((m+n)log (m+n)), in 1-D and 2-D. Implementation results of our improved 1-D and 2-D SOLF algorithm have shown that in most cases it outperforms the commonly-used approaches for the SOLF problem. We also apply our techniques to some problems in computational geometry and other areas, improving the previous results.This research was supported in part by the National Science Foundation under Grant CCR-9623585.The research of this author was supported in part by National Science Foundation under grant CCF-0430366.Grant-in-Aid of Ministry of Science, Culture and Education of Japan, No. 10780274.The research of this author was supported in part by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Researchon Priority Areas     

Constructing the Maximum Consensus Tree from Rooted Triples

We investigated the problem of constructing the maximum consensus tree from rooted triples. We showed the NP-hardness of the problem and developed exact and heuristic algorithms. The exact algorithm is based on the dynamic programming strategy and runs in O((m + n ²)3 ⁿ ) time and O(2 ⁿ ) space. The heuristic algorithms run in polynomial time and their performances are tested and shown by comparing with the optimal solutions. In the tests, the worst and average relative error ratios are 1.200 and 1.072 respectively. We also implemented the two heuristic algorithms proposed by Gasieniec et al. The experimental result shows that our heuristic algorithm is better than theirs in most of the tests.     

Estimating Long Memory in Volatility

We consider semiparametric estimation of the memory parameter in a model that includes as special cases both long‐memory stochastic volatility and fractionally integrated exponential GARCH (FIEGARCH) models. Under our general model the logarithms of the squared returns can be decomposed into the sum of a long‐memory signal and a white noise. We consider periodogram‐based estimators using a local Whittle criterion function. We allow the optional inclusion of an additional term to account for possible correlation between the signal and noise processes, as would occur in the FIEGARCH model. We also allow for potential nonstationarity in volatility by allowing the signal process to have a memory parameter d^*1/2. We show that the local Whittle estimator is consistent for d^*∈(0,1). We also show that the local Whittle estimator is asymptotically normal for d^*∈(0,3/4) and essentially recovers the optimal semiparametric rate of convergence for this problem. In particular, if the spectral density of the short‐memory component of the signal is sufficiently smooth, a convergence rate of n^2/5−δ for d^*∈(0,3/4) can be attained, where n is the sample size and δ>0 is arbitrarily small. This represents a strong improvement over the performance of existing semiparametric estimators of persistence in volatility. We also prove that the standard Gaussian semiparametric estimator is asymptotically normal if d^*=0. This yields a test for long memory in volatility.     

Flattening topologically spherical surface

The problem of optimal surface flattening in 3-D finds many applications in engineering and manufacturing. However, previous algorithms for this problem are all heuristics without any quality guarantee and the computational complexity of the problem was not well understood. In this paper, we prove that the optimal surface flattening problem is NP-hard. Further, we show that the problem of flattening a topologically spherical surface admits a PTAS and can be solved by a (1+ε)-approximation algorithm in O(nlog n) time for any constant ε>0, where n is the input size of the problem.     

Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem

In this paper we consider the constant rank unconstrained quadratic 0-1 optimization problem, CR-QP01 for short. This problem consists in minimizing the quadratic function 〈x, Ax〉 + 〈c, x〉 over the set {0,1} ⁿ where c is a vector in ℝ ⁿ and A is a symmetric real n × n matrix of constant rank r. We first present a pseudo-polynomial algorithm for solving the problem CR-QP01, which is known to be NP-hard already for r = 1. We then derive two new classes of special cases of the CR-QP01 which can be solved in polynomial time. These classes result from further restrictions on the matrix A. Finally we compare our algorithm with the algorithm of Allemand et al. (2001) for the CR-QP01 with negative semidefinite A and extend the range of applicability of the latter algorithm. It turns out that neither of the two algorithms dominates the other with respect to the class of instances which can be solved in polynomial time.     

On the complexity and approximation of non-unique probe selection using d-disjunct matrix

In this paper, we studied the MINimum-d-Disjunct Submatrix (MIN-d-DS), which can be used to select the minimum number of non-unique probes for viruses identification. We prove that MIN-d-DS is NP-hard for any fixed d. Using d-disjunct matrix, we present an O(log k)-approximation algorithm where k is an upper bound on the maximum number of targets hybridized to a probe. We also present a (1+(d+1)log n)-approximation algorithm to identify at most d targets in the presence of experimental errors. Our approximation algorithms also yield a linear time complexity for the decoding algorithms. The research of T. Znati was supported in part by National Science Foundation under grant CCF-0548895.     

Line facility location in weighted regions

In this paper, we present approximation algorithms for solving the line facility location problem in weighted regions. The weighted region setup is a more realistic model for many facility location problems that arise in practical applications. Our algorithms exploit an interesting property of the problem, that could possibly be used for solving other problems in weighted regions.     

Parameterized lower bound and inapproximability of polylogarithmic string barcoding

String barcoding is a method that can identify microorganisms by analyzing their genome sequences. In this paper, we study the polylogarithmic string barcoding problem, where the lengths of the substrings in the testing set are polylogarithmically bounded. In particular, we show that the polylogarithmic string barcoding problem remains NP-hard and moreover, for a problem instance with n sequences, it is NP-hard to achieve an approximate ratio within dln n in polynomial time, where d is some constant. We then consider the parameterized polylogarithmic string barcoding problem, where the number of substrings in the test set is considered to be a fixed parameter k. We show that, unless W[2]=FPT, there does not exist a 2 ^O(k) n ^c algorithm that can decide whether a test set of size k exists or not, where c is a constant independent of n and k.     

The max quasi-independent set problem

In this paper, we deal with the problem of finding quasi-independent sets in graphs. This problem is formally defined in three versions, which are shown to be polynomially equivalent. The one that looks most general, namely, f-max quasi-independent set, consists of, given a graph and a non-decreasing function f, finding a maximum size subset Q of the vertices of the graph, such that the number of edges in the induced subgraph is less than or equal to f(|Q|). For this problem, we show an exact solution method that runs within time O^*(2^{\fracd-27/23d+1n})O^{*}(2^{\frac{d-27/23}{d+1}n}) on graphs of average degree bounded by d. For the most specifically defined γ-max quasi-independent set and k-max quasi-independent set problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested.     

Fast On-Line/Off-Line Algorithms for Optimal Reinforcement of a Network and its Connections with Principal Partition

The problem of computing the strength and performing optimal reinforcement for an edge-weighted graph G(V, E, w) is well-studied. In this paper, we present fast (sequential linear time and parallel logarithmic time) on-line algorithms for optimally reinforcing the graph when the reinforcement material is available continuously on-line. These are the first on-line algorithms for this problem. We invest O(|V|³|E|log|V|) time (equivalent to (|V|) invocations of the fastest known algorithms for optimal reinforcement) in preprocessing the graph before the start of our algorithms. It is shown that the output of our on-line algorithms is as good as that of the off-line algorithms. Thus our algorithms are better than the fastest off-line algorithms in situations when a sequence of more than (|V|) reinforcement problems need to be solved. The key idea is to make use of ideas underlying the theory of Principal Partition of a Graph. Our ideas are easily generalized to the general setting of polymatroid functions. We also present a new efficient algorithm for computation of the Principal Sequence of a graph.     

Single facility scheduling with dual criteria: minimizing maximum tardiness subject to minimum number of tardy jobs

This paper considers the static single machine scheduling problem with the objective of minimizing the maximum tardiness of any job subject to the constraint that the total number of lardy jobs is minimum. Based on simple dominance conditions an o(n²) heuristic algorithm is proposed to find an approximate solution to this problem. The effectiveness of the proposed heuristic algorithm is empirically evaluated by solving a large number of problems and comparing them to the optimal solutions obtained through the branch and bound algorithm.     

Median problems with positive and negative weights on cycles and cacti

This paper deals with facility location problems on graphs with positive and negative vertex weights. We consider two different objective functions: In the first one (MWD) vertices with positive weight are assigned to the closest facility, whereas vertices with negative weight are assigned to the farthest facility. In the second one (WMD) all the vertices are assigned to the nearest facility. For the MWD model it is shown that there exists a finite set of points in the graph which contains the locations of facilities in an optimal solution. Furthermore, algorithms for both models for the 2-median problem on a cycle are developed. The algorithm for the MWD model runs in linear time, whereas the algorithm for the WMD model has a time complexity of  O(n²)\mathcal{O}(n^{2}) .     

On some geometric problems of color-spanning sets

In this paper we study several geometric problems of color-spanning sets: given n points with m colors in the plane, selecting m points with m distinct colors such that some geometric properties of the m selected points are minimized or maximized. The geometric properties studied in this paper are the maximum diameter, the largest closest pair, the planar smallest minimum spanning tree, the planar largest minimum spanning tree and the planar smallest perimeter convex hull. We propose an O(n ^1+ε ) time algorithm for the maximum diameter color-spanning set problem where ε could be an arbitrarily small positive constant. Then, we present hardness proofs for the other problems and propose two efficient constant factor approximation algorithms for the planar smallest perimeter color-spanning convex hull problem.     

Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling

We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem discussed here were already treated by Bar-Noy et al. (Proc. 31st ACM STOC, 1999, pp. 622–631; http://www.eng.tau.ac.il/amotz/). Our main contribution is to provide algorithms that do not use linear programming, are simple and much faster than the corresponding ones proposed in Bar-Noy et al. (ibid., 1999), while either having the same quality of approximation or improving it. More precisely, compared to the results of in Bar-Noy et al. (ibid., 1999), our pseudo-polynomial algorithm for multiple unrelated machines and all of our strongly-polynomial algorithms have better performance ratios, all of our algorithms run much faster, are combinatorial in nature and avoid linear programming. Finally, we show that algorithms with better performance ratios than 2 are possible if the stretch factors of the jobs are bounded; a straightforward consequence of this result is an improvement of the ratio of an optimal solution of the integer programming formulation of the JISP2 problem (see Spieksma, Journal of Scheduling, vol. 2, pp. 215–227, 1999) to its linear programming relaxation.     

Efficient Job Scheduling Algorithms with Multi-Type Contentions

In this paper, we consider an interesting generalization of the classic job scheduling problem in which each job needs to compete not only for machines but also for other types of resources. The contentions among jobs for machines and for resources could interfere with each other, which complicates the problem dramatically. We present a family of approximation algorithms for solving several variants of the problem by using a generic algorithmic framework. Our algorithms achieve a constant approximation ratio (i.e., 3) when there is only one type of resources or certain dependency relation exists among multiple types of resources. When the r resources are unrelated, the approximation ratio of our algorithm becomes k+2, where k≤ r is a constant depending on the problem instance. As an application, we also show that our techniques can be easily applied to optical burst switching (OBS) networks to design more efficient wavelength scheduling algorithms.This research was supported in part by an IBM faculty partnership award, and an IRCAF award from SUNY Buffalo.     

Construction of the nearest neighbor embracing graph of a point set

This paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNE-graph) of a given point set V of size n in the k-dimensional space (k-D) for k = 2,3. The NNE-graph provides another way of connecting points in a communication network, which has lower expected degree at each point and shorter total length of connections with respect to those using Delaunay triangulation. In fact, the NNE-graph can also be used as a tool to test whether a point set is randomly generated or has some particular properties. We show that in 2-D the NNE-graph can be constructed in optimal time in the worst case. We also present an time algorithm, where d is the -th largest degree in the utput NNE-graph. The algorithm is optimal when . The algorithm is also sensitive to the structure of the NNE-graph, for instance when , the number of edges in NNE-graph is bounded by for any value g with . We finally propose an time algorithm for the problem in 3-D, where d and are the -th largest vertex degree and the largest vertex degree in the NNE-graph, respectively. The algorithm is optimal when the largest vertex degree of the NNE-graph is .     

Random restricted matching and lower bounds for?combinatorial optimization

We prove results on optimal random extensions of trees over points in [0,1] ^d . As an application, we give a general framework for translating results from combinatorial optimization about the behaviour of random points into results for point sets with sufficiently high regularity. We furthermore introduce a new irregularity problem concerning Voronoi cells, which has applications in logistics.     

Improved algorithms for largest cardinality 2-interval pattern problem

The 2-INTERVAL PATTERN problem is to find the largest constrained pattern in a set of 2-intervals. The constrained pattern is a subset of the given 2-intervals such that any pair of them are R-comparable, where model . The problem stems from the study of general representation of RNA secondary structures. In this paper, we give three improved algorithms for different models. Firstly, an O(n{log} n +L) algorithm is proposed for the case , where is the total length of all 2-intervals (density d is the maximum number of 2-intervals over any point). This improves previous O(n ²log n) algorithm. Secondly, we use dynamic programming techniques to obtain an O(nlog n + dn) algorithm for the case R = { <, ⊏ }, which improves previous O(n ²) result. Finally, we present another algorithm for the case with disjoint support(interval ground set), which improves previous O(n ²□n) upper bound. A preliminary version of this article appears in Proceedings of the 16th Annual International Symposium on Algorithms and Computation, Springer LNCS, Vol. 3827, pp. 412–421, Hainan, China, December 19–21, 2005.