2025275
Optimizing the sum of linear fractional functions and applications
1 I n t r o d u c t i o n . The problem of optimizing the sum of linear fractional functions (SOLF) is defined as follows: max f(Zl,...,Xd)= ~ [ : 7 : ~ d ) (Xl ..... z~t)ES i=1 ~ a r t m e n t of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA, {chen,odaescu,xwu,jxu}@cse.nd.edu. This research was supported in part by the National Science Foundation under Grant CCR-9623585. tThe work of this author was supported in part by a fellowship of the Center for Applied Mathematics, University of Notre Dame, Notre Dame, Indiana, USA. t Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 O-okayama, Meguro-ku, Tokyo 152, Japan, daiOis.titech.ac.jp. Grant-in-Aid of Ministry of Science, Culture and Education of Japan, No. 10780274. §Department of Architecture and Architectural Systems, Graduate School of Engineering, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto, 606-8501 Japan, naoki~archi.kyoto-u.ac.jp. Partially supported by Grant-inAid for Scientific Research on Priority Areas (B) by the Ministry of Education, Science, Sports and Culture of Japan. IThe work of this author was supported in part by a fellowship of the Center for Applied Mathematics, and by a summer graduate research fellowship of the Graduate School, University of Notre Dame, Notre Dame, Indiana, USA. such that for each i = 1 , 2 , . . . , m , ni(Xl,...,Xd) and di(Xl,...,Xd) are linear functions in a fixed d-D space ]~d, di (x t , . . . ,Xd) ~ 0 for any (Xl , . . . ,Xd) E S, the feasible domain S is defined by n linear constraints (i.e., half-spaces in Rd), and S ~ ¢. Each linear fractional term ~(~1 ..... ~ ) ddxl,...,z~) is called a ratio. The SOLF problem appears in the algorithmic solutions for several geometric optimization problems. In layered manufacturing, Majhi et al. [17], [18] showed that the length-optimal supports for a simple nonconvex polygon can be obtained by solving the 1-D SOLF problem on an interval. Arkin et al. [1] formulated the problem of finding a minimum-area starshaped or monotone polygon that contains a simple polygon, which appears in material layout [1], [8], [21] (e.g., cloth manufacturing) and manufacturing [18], as one of optimizing the sum of 2-D fractional polynomials of degrees 3 and 2 under linear constraints. We will show that the objective function of this problem can actually be simplified to the 2-D SOLF form. For the problem of finding optimal penetrations among weighted regions [5], we shall show tha t the L1 and Leo versions of this problem have the 2-D SOLF problem as a key subproblem. The SOLF problem also arises in other areas. For example, in combinatorial optimization, a class of problems on finding a structure with the maximum (or minimum) mean-weight cost can be solved by optimizing some linear fractional functions [23]. In operations research, it was shown in [11], [24] that many economic applications (e.g., maximization of productivity, return on investment, and return/risk) can be reduced to solving the SOLF problem. Quite a few solutions have been given for the SOLF problem [1], [11], [15], [17], [18], [25]. It is interesting to note that the SOLF related problems were originally studied in economic applications, where the number of variables is usually much bigger than the number of fractional terms. As a result, many previous SOLF algorithms were designed to target problems with only a few fractional terms (less than 10) for a reasonable
9160894
Geometric algorithms for static leaf sequencing problems in radiation therapy
The static leaf sequencing (SLS) problem arises in radiation therapy for cancer treatments, aiming to accomplish the delivery of a radiation prescription to a target tumor in the minimum amount of delivery time. Geometrically, the SLS problem can be formulated as a 3-D partition problem for which the 2-D problem of partitioning a polygonal domain (possibly with holes) into a minimum set of monotone polygons is a special case. In this paper, we present new geometric algorithms for a basic case of the 3-D SLS problem (which is also of clinical value) and for the general 3-D SLS problem. Our basic 3-D SLS algorithm, based on new geometric observations, produces guaranteed optimal quality solutions using Steiner points in polynomial time; the previously best known basic 3-D SLS algorithm gives optimal outputs only for the case without any Steiner points, and its time bound involves a multiplicative factor of a factorial function of the input. Our general 3-D SLS algorithm is based on our basic 3-D SLS algorithm and a polynomial time algorithm for partitioning a polygonal domain (possibly with holes) into a minimum set of x-monotone polygons, and has a fast running time. Experiments and comparisons using real medical data and on a real radiotherapy machine have shown that our 3-D SLS algorithms and software produce treatment plans that use significantly shorter delivery time and give better treatment quality than the current most popular commercial treatment planning system and the most well-known SLS algorithm. Some of our techniques and geometric procedures (e.g., for the problem of partitioning a polygonal domain into a minimum set of x-monotone polygons) are interesting in their own right.
17909513
Determining an optimal penetration among weighted regions in two and three dimensions
We present efficient algorithms for solving the problem of computing an optimal penetration (a ray or a semi-ray) among weighted regions in 2-D and 3-D spaces. This problem finds applications in several areas, such as radiation therapy, geological exploration, and environmental engineering. Our algorithms are based on a combination of geometric techniques and optimization methods. Our geometric analysis shows that the d-D (d = 2, 3) optimal penetration problem can be reduced to solving O(n2(d−1)) instances of certain special types of non-linear optimization problems, where n is the total number of vertices of the regions. We also give implementation results of our 2-D algorithms.
8713870
Optimal Terrain Construction Problems and Applications
in Intensity-Modulated Radiation Therapy
AbstractIn this paper we study several rectilinear terrain construction
problems, which model the leaf sequencing problems in
intensity-modulated radiation therapy (IMRT).
We present a novel unified approach
based on geometric techniques for solving these terrain
construction problems. Our ideas include formulating the terrain
construction problems as computing shortest paths in a weighted directed
graph and building the graph by computing optimal bipartite matchings on various geometric objects
subject to specific constraints of each of the problems. Further,
since we need to compute optimal bipartite matchings on many sets
of geometric objects, we use techniques for computing such
matchings in a batch fashion to speed up these matching
computations. Our approach leads to the first algorithms for several leaf
sequencing problems in IMRT that are practically fast and guarantee
 an output which is optimal for a large sub-class of solutions. The previously known leaf
sequencing algorithms which are currently used in radiation therapy practice
are all heuristics that do not guarantee any good
quality of the output solutions and may run in a long time.
Our implementation
results show that our terrain construction algorithms run very
fast on real medical data (all under few seconds).
11091243
Efficient Algorithms for Intensity Map Splitting Problems in Radiation Therapy
In this paper, we study several interesting intensity map splitting (IMSp) problems that arise in Intensity-Modulated Radiation Therapy (IMRT), a state-of-the-art radiation therapy technique for cancer treatments. In current clinical practice, a multi-leaf collimator (MLC) with a maximum leaf spread is used to deliver the prescribed intensity maps (IMs). However, the maximum leaf spread of an MLC may require to split a large intensity map into several abutting sub-IMs each being delivered separately, which results in prolonged treatment time. Few IM splitting techniques reported in the literature has addressed the issue of treatment delivery efficiency for large IMs. We develop a unified approach for solving the IMSp problems while minimizing the total beam-on time in various settings. Our basic idea is to formulate the IMSp problem as computing a k-link shortest path in a directed acyclic graph. We carefully characterize the intrinsic structures of the graph, yielding efficient algorithms for the IMSp problems.
27904596
Segmenting Doughnut-Shaped Objects in Medical Images
Image segmentation with specific constraints has found applications in several areas such as biomedical image analysis and data mining. In this paper, we study the problem of segmenting doughnut-shaped and smooth objects in 2-D medical images. Image objects of these shapes are often studied in medical applications. We present an O(IJU(U − L)logJlog(U − L)) time algorithm, where the size of the input 2-D image is I× J, M is the smoothness parameter with 1 ≤ M ≤ J, and L and U are the thickness parameters specifying the thickness between two border contours of a doughnut-shaped object. Previous approaches for solving this segmentation problem are computationally expensive and/or need a lot of user interference. Our algorithm improves the straightforward dynamic programming algorithm by a factor of \(O(\frac{J(U-L)M^2}{U{\rm log}J{\rm log}(U-L)})\). We explore some interesting observations, which make possible to apply the divide-and-conquer strategy combined with dynamic programming. Our algorithm is also based on computing optimal paths in an implicitly represented graph.
11758071
Algorithms for optimal multi-resolution quantization
Multi-resolution quantization is a way of constructing a progressively refinable description of a discrete random variable. The underlying discrete optimization problem is to minimize an expected distortion over all refinement levels weighted by the probability or importance of the descriptions of different resolutions. This research is motivated by the application of multimedia communications via variable-rate channels. We propose an O(rN2) time and O(N2 log N) space algorithm to design a minimum-distortion quantizer of r levels for a random variable drawn from an alphabet of size N. It is shown that for a very large class of distortion measures the objective function of optimal multi-resolution quantization satisfies the convex Monge property. The efficiency of the proposed algorithm hinges on the convex Monge property. But our algorithm is simpler (even though of the same asymptotic complexity) than the well-known SMAWK fast matrix search technique, which is the best existing solution to the quantization problem. For exponential random variables our approach leads to a solution of even lower complexity: O(rN) time and O(N log N) space, which outperforms all the known algorithms for optimal quantization in both multi- and single-resolution cases. We also generalize the multi-resolution quantization problem to a graph problem, for which our algorithm offers an efficient solution.
18276516
Interference Detection for Subdivision Surfaces
Accurate and robust interference detection and ray-tracing of subdivis ion surfaces requires safe linear approximations. Approximation of the limit surface by the subdivided control polyhe dron can be both inaccurate and, due to the exponential growth of the number of facets, costly. This paper shows how a standard intersection hierarchy, such as an OB B tree, can be made safe and efficient for subdivision surface interference detection. The key is to construct, on th e fly, optimally placed facets, whose spherical offsets tightly enclose the limit surface. The spherically offset fac ets can be locally subdivided and they can be efficiently intersected based on standard triangle-triangle interfere nce detection.
7000665
Multiple Agents Moving Target Search
Traditional single-agent search algorithms usually make simplifying assumptions (single search agent, stationary target, complete knowledge of the state, and sufficient time). There are algorithms for relaxing one or two of these constraints; in this paper we want to relax all four. The application domain is to have multiple search agents cooperate to pursue and capture a moving target. Agents are allowed to communicate with each other. For solving Multiple Agents Moving Target (MAMT) applications, we present a framework for specifying a family of suitable search algorithms. This paper investigates several effective approaches for solving problem instances in this domain.
18130193
Preemptive maximum stretch optimization scheduling for wireless on-demand data broadcast
On-demand broadcast is an attractive data dissemination method for mobile and wireless computing. We need an on-demand broadcast scheduling algorithm which can balance individual and overall performance, at the same time avoid the starvation of data items, and scale in terms of client population, database size, and data size in heterogeneous settings. As stretch is regarded as a fair performance metric for variable-sized data requests, in this paper, we propose a new preemptive, heuristic online scheduling algorithm, called PRS for on-demand broadcast system to optimize the worst case stretch across all criteria. We have done a series of simulation experiments to evaluate the performance of our algorithm as compared with other recently proposed methods under a range of scenarios. The experimental results show that our algorithm can substantially reduce the maximum stretch without jeopardizing the overall system performance.
10914298
Wireless real-time on-demand data broadcast scheduling with dual deadlines
In this paper, issues involved in the design of real-time on-demand broadcast system which maintains data temporal constraints are discussed. We propose a new online scheduling algorithm, called RDDS that incorporates access frequency, data size, request-deadline and data-deadline of pending requests for real-time on-demand broadcast system with dual deadlines. Furthermore, the concepts of deferrable requests and non-deferrable requests are introduced, cases of non-deferrable requests are analyzed, and Non-deferrable Request First policy is proposed and integrated into RDDS to form another new algorithm, called RDDS-W. We have performed a series of simulation experiments to evaluate the performance of our algorithms as compared with other previously proposed methods. The experimental results show that our algorithms can substantially outperform other algorithms under a wide range of scenarios, especially when combining with Non-deferrable Request First policy, which improves the performance significantly.