Computing predecessor and successor in rounding to nearest

We give simple and efficient methods to compute and/or estimate the predecessor and successor of a floating-point number using only floating-point operations in rounding to nearest. This may be used to simulate interval operations, in which case the quality in terms of the diameter of the result is significantly improved compared to existing approaches.      

Practical segment intersection with finite precision output

The fundamental problem of finding all intersections among a set of line segments in the plane has numerous important applications. Reliable implementations need to cope with degenerate input and limited precision. Representing intersection points with fixed precision can introduce extraneous intersections. This paper presents simple solutions to these problems and shows that they impose only a very modest performance penalty. Test data came from a data compression problem involving a map database.     

A note on the prize collecting traveling salesman problem

We study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. We present an approximation algorithm with constant bound. The algorithm is based on Christofides' algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.Research supported in part by ONR contract N00014-90-J-1649 and NSF contract DDM-8922712.     

A constructive aisle design model for unit-load warehouses with multiple pickup and deposit points

We develop a network-based warehouse model of individual pallet locations and their interactions with appropriate cross aisles in order to evaluate the expected travel distance of a given design. The model is constructive in that it uses Particle Swarm Optimization to determine the best angles of cross aisles and picking aisles for multiple, pre-determined pickup and deposit (P&D) points in a unit-load warehouse. Our results suggest that alternative designs offer reduced expected travel distance, but at the expense of increased storage space. The opportunity for benefit also seems to decline as P&D points increase in number and dispersion.     

Reporting curve segment intersections using restricted predicates

We investigate how to report all k intersecting pairs among a collection of n x-monotone curve segments in the plane, using only predicates of the following forms: is an endpoint to the left of another? is an endpoint above a segment? do two segments intersect? By studying the intersection problem in an abstract setting that assumes the availability of certain “detection oracles”, we obtain a near-optimal randomized algorithm that runs in expected time. In the bichromatic case (where segments are colored red or blue with no red/red or blue/blue intersections), we find a better algorithm that runs in O((n+k)log_2+k/nn) worst-case time, by modifying a known segment-tree method. Two questions of Boissonnat and Snoeyink are thus answered to within logarithmic factors.     

A dexterous randomized response model for estimating a rare sensitive attribute using Poisson distribution

Taking the clue from the pioneer work of Land et al. (2011), we have suggested an unbiased estimator of the mean number of persons possessing the rare sensitive attribute in presence of the known proportion of persons possessing a rare unrelated attribute. The variance expression is derived. The empirical studies performed and graphical representation show that the new model is more efficient than the one recently considered by Land et al. (2011).     

估计敏感特征比例和敏感指标均值的问卷调查技术

提出了一种敏感性问题问卷调在技术.在相同的样本量下,提出的问卷调查技术可以获得调查者所关心的两项敏感指标(敏感比例π_x和敏感指标均值μ_x).此外,还定义了关于敏感指标的极大似然估计形式,给出一种问卷调查装置对个体隐私保护的度量方法.利用Monte Carlo方法模拟计算了在简单随机有放回抽样设计方案下估计量的精度和装置的保护度.     

A Markov-modulated jump-diffusion risk model with randomized observation periods and threshold dividend strategy

This paper considers a Markov-modulated jump-diffusion risk model with randomized observation periods and threshold dividend. A second order integro-differential system of equations that characterizes the expected discounted dividend payments is obtained. As a closed-form solution does not exist, a numerical procedure based on the sinc function approximation through a collocation method is proposed. Finally, an example illustrating the procedure is presented.     

On Approximate Range Counting and Depth

We improve the previous results by Aronov and Har-Peled (SODA’05) and Kaplan and Sharir (SODA’06) and present a randomized data structure of O(n) expected size which can answer 3D approximate halfspace range counting queries in expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo. In addition, we describe new results for several related problems, including approximate Tukey depth queries in 3D, approximate regression depth queries in 2D, and approximate linear programming with violations in low dimensions. A preliminary version of this paper appeared in Proc. 23rd Sympos. Comput. Geom., pp. 337–343, 2007. Work of the second author was supported by NSERC.     

Iterated egalitarian compromise solution to bargaining problems and midpoint domination

We introduce a new solution for two-person bargaining problems: the iterated egalitarian compromise solution. It is defined by using two prominent bargaining solutions, the egalitarian solution (Kalai, 1977) and the equal-loss solution (Chun, 1988), in an iterative fashion. While neither of these two solutions satisfy midpoint domination – an appealing normative property – we show that the iterated egalitarian compromise solution does so.