We present a linear time algorithm for the weighted k -center problem on trees for fixed k . This partially settles the long-standing question about the lower bound on the time complexity of the problem. The current time complexity of the best-known algorithm for the problem with k as part of the input is O ( n log ⁡ n ) by Wang et al. (2018) [20] . Whether an O ( n ) time algorithm exists for arbitrary k is still open.

We present dynamic flow algorithms to solve the k-sink problem whose aim is to locate k sinks (evacuation centers) in such a way that the evacuation time of the last evacuee is minimized. In the confluent model, the evacuees originating from or passing through a vertex must evacuate to the same sink, and most known results on the k-sink problem adopt the confluent model. When the edge capacities are uniform (resp. general), our algorithms for non-confluent flow in the path networks run in O(n + k² log² n) (resp. O(n log(n) + k² log⁵ n)) time, where n is the number of vertices. Our algorithms for cycle networks run in O(k²n log² n) (resp. O(k²n log⁵ n)) time, when the edge capacities are uniform (resp. general).

The bilinear assignment problem (BAP) is a generalization of the well-known quadratic assignment problem. In this paper, we study the problem from the computational analysis point of view. Several classes of neighborhood structures are introduced for the problem along with some theoretical analysis. These neighborhoods are then explored within a local search and variable neighborhood search frameworks with multistart to generate robust heuristic algorithms. In addition, we present several very fast construction heuristics. Our systematic experimental analysis disclosed some interesting properties of the BAP, different from those of comparable models. We have also introduced benchmark test instances that can be used for future experiments on exact and heuristic algorithms for the problem.

Evacuation in emergency situations can be modeled by a dynamic flow network. Two criteria have been used before: one is the evacuation completion time and the other is the aggregate evacuation time of individual evacuees. The aim of this paper is to optimize the aggregate evacuation time in the simplest case, where the network is a path and only one evacuation center (called a sink) is to be introduced. The evacuees are initially located at the vertices, but their precise numbers are unknown, and are given by upper and lower bounds. Under this assumption, we compute the sink location that minimizes the maximum "regret." We present an $O(n^2\log n)$ time algorithm to solve this problem, improving upon the previously fastest $O(n^3)$ time algorithm, where $n$ is the number of vertices.

In this paper we study the k-delivery traveling salesman problem (TSP)on trees, a variant of the non-preemptive capacitated vehicle routing problem with pickups and deliveries. We are given n pickup locations and n delivery locations on trees, with exactly one item at each pickup location. The k-delivery TSP is to find a minimum length tour by a vehicle of finite capacity k to pick up and deliver exactly one item to each delivery location. We show that an optimal solution for the k-delivery TSP on paths can be found that allows succinct representations of the routes. By exploring the symmetry inherent in the k-delivery TSP, we design a 5/3-approximation algorithm for the k-delivery TSP on trees of arbitrary heights. The ratio can be improved to (3/2 - 1/2k) for the problem on trees of height 2. The developed algorithms are based on the following observation: under certain conditions, it makes sense for a non-empty vehicle to turn around and pick up additional loads.

We study the surveillance of a polygonal area by a robot, which is equipped with a flashlight and moves along the polygon boundary. Its aim is to illuminate any intruder who can move faster than the moving flashlight beam, trying to avoid detection. We propose an O(n)-time algorithm for testing if it is possible for such a robot to always detect any intruder in a given polygon, where n is the number of vertices of the given polygon. This improves upon the best previous time complexity of O(n log n).

We investigate the problem of converting sets of sensors into strongly connected networks of sensors using multiple directional antennae. Consider a set S of n points in the plane modeling sensors of an ad hoc network. Each sensor uses a fixed number, say 1 ≤ k ≤ 5, of directional antennae modeled as a circular sector with a given spread (or angle) and range (or radius). We give algorithms for orienting the antennae at each sensor so that the resulting directed graph induced by the directed antennae on the nodes is strongly connected. We also study trade-offs between the total angle spread and range for maintaining connectivity.

Abstract We consider a generalization of the median and center facility location problem called the collection depots facility location (CDFL) problem. We are given a set of client locations and a set of collection depots and we are required to find the placement for a certain number of facilities, so that the cost of dispatching a vehicle from a facility, to a client, to a collection depot, and back, is optimized for all clients. The CDFL center problem minimizes the cost of the most expensive vehicle tour among all clients, and the CDFL median problem minimizes the sum of the tour costs for all clients. We provide the first polynomial time algorithms to solve the 1 and k median problems in trees with time complexities O(n log n) and O(kn3), respectively, where n is the number of vertices in the tree. In contrast, a restricted version of the k‐median problem, where clients are given lists of allowed collection depots, is NP‐complete even for star graphs. We also give an optimal linear time algorithm to solve the discrete and continuous weighted 1‐center problem, improving on the O(n log n) result of Tamir and Halman [Discrete Optimization 2(2005), 168–184]. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Attribute data and relationship data are two principal types of data, representing the intrinsic and extrinsic properties of entities. While attribute data have been the main source of data for cluster analysis, relationship data such as social networks or metabolic networks are becoming increasingly available. It is also common to observe both data types carry complementary information such as in market segmentation and community identification, which calls for a joint cluster analysis of both data types so as to achieve better results. In this article, we introduce the novel Connected k -Center ( CkC ) problem, a clustering model taking into account attribute data as well as relationship data. We analyze the complexity of the problem and prove its NP-hardness. Therefore, we analyze the approximability of the problem and also present a constant factor approximation algorithm. For the special case of the CkC problem where the relationship data form a tree structure, we propose a dynamic programming method giving an optimal solution in polynomial time. We further present NetScan, a heuristic algorithm that is efficient and effective for large real databases. Our extensive experimental evaluation on real datasets demonstrates the meaningfulness and accuracy of the NetScan results.

Abstract Thep‐center problem is to locatepfacilities on a network so as to minimize the largest distance from a demand point to its nearest facility. Thep‐median problem is to locatepfacilities on a network so as to minimize the average distance from a demand point to its closest facility. We consider these problems when the network can be modeled by an interval or circular‐arc graph whose edges have unit lengths. We provide, given the interval model of annvertex interval graph, anO(n) time algorithm for the 1‐median problem on the interval graph. We also show how to solve thep‐median problem, for arbitraryp, on an interval graph inO(pnlogn) time and on a circular‐arc graph inO(pn2logn) time. We introduce a spring representation of the objective function and show how to solve thep‐center problem on a circular‐arc graph inO(pn) time, assuming that the arc endpoints are sorted. © 2002 Wiley Periodicals, Inc.

Jung and Gupta reported (1996) a representation, called octree distance map (ODM), for efficient collision detection in static environments. ODM captured partial distance information in a hierarchical manner and traded some memory (2 bytes per white node) for speed gains (as compared to an octree) in collision detection. In this paper, we propose a much more complete and systematic hierarchical representation for distance maps, the extended octree distance map (EODM). Like ODM, it utilizes an octree as the base representation. Along the perimeter of each white node in the octree, it stores a distance function that represents the distance of each boundary point of the white node to the obstacle closest to that point. As a result, EODM is more memory intensive than an ODM (and an octree), however, it would significantly decrease the collision detection time compared to either a conventional octree or the ODM. EODM is computed once and then repeatedly used for collision detection queries. We present algorithms for creating the EODM and use it for collision detection. Our preliminary experiments in 2D show that while EODM requires about three to five times more memory than an octree and four to five times extra memory than an ODM, it speeds up collision detection by a factor of three to six compared to an octree and by a factor of three to four as compared to an ODM.

The k-nearest neighbor decision rule (or k-NNR) is used to classify a point in d-space according to the dominant class among its k nearest neighbors in some reference set (in which each point has a known class). It is useful to find a small subset S' of S that can be used as the reference set instead. If the k-NNR always makes the same decision using either S or S' as the reference set, then S' is called an exact thinning of S for the k-NNR. We show that such an exact thinning can be determined easily from the k-Delaunay graph of S (which is dual to the order-k Voronoi diagram of S). This graph "encodes" a particular subset of S that must be included within any exact thinning for the k-NNR, and it also provides information on how this subset can be augmented into an exact thinning (although perhaps not a minimum one). In addition, we investigate how the k-Gabriel graph (which is a subgraph of the k-Delaunay graph) can be used to derive an inexact thinning of S that performs well in practice for the k-NNR. It is advantageous to use the k-Gabriel graph instead of the k-Delaunay graph, because the k-Gabriel graph is smaller and much easier to compute from the point set S.

We present an $O(n)$algorithm to find a maximum clique in a proper circular arc graph. We assume that the input graph is represented by a sorted simple family of circular arcs or by an equivalent representation. In Deng, Hell, and Huang [SIAM J. Comput., 25 (1996), pp. 390–403], we gave an $O(m + n)$ algorithm to find such a representation for a proper circular arc graph given by its adjacency lists. As an application we also give an $O(n)$ algorithm for q-coloring proper circular arc graphs for a fixed q. (Such an algorithm was first given by Teng and Tucker.) Finally we indicate how our algorithm can be modified to find a maximum weight clique in a weighted graph, also in time $O(n)$.

Given a family of objects in the plane, the line transversal problem is to compute a line that intersects every member of the family.In this paper we examine a variation of the line transversal problem that involves computing a shortest line segment that intersects every member of the family.In particular, we give O(n log n) time algorithms for computing a shortest transversal of a family of n lines and of a family of n line segments.We also present an O(n log2 n) time algorithm for computing a shortest transversal of a family of polygons with a total of n vertices.In general, finding a line transversal for a family of n objects takes fl(n log n) time.This time bound holds for a family of n line segments thus our shortest transversal algorithm for this family is optimal.

Article Optimal algorithms for some smallest intersection radius problems (extended abstract) Share on Authors: Binay K. Bhattacharya School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada, V5A 1S6 School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada, V5A 1S6View Profile , Sreesh Jadhav Department of Computer Science, Indian Institute of Technology, Kanpur, India Department of Computer Science, Indian Institute of Technology, Kanpur, IndiaView Profile , Asish Mukhopadhayay Department of Computer Science, Indian Institute of Technology, Kanpur, India Department of Computer Science, Indian Institute of Technology, Kanpur, IndiaView Profile , Jean-Marc Robert School of Computer Science, McGill University, 3480 University St., Montreal, P.Q., Canada, H3A 2A7 School of Computer Science, McGill University, 3480 University St., Montreal, P.Q., Canada, H3A 2A7View Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 81–88https://doi.org/10.1145/109648.109657Online:01 June 1991Publication History 1citation335DownloadsMetricsTotal Citations1Total Downloads335Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We consider a generalization of notions of external visibility of simple polygons, namely weak external visibility, weak external visibility from a line and monotonicity, that we call sector visibility. Informally, sector visibility addresses the question of external visibility along rays (or sight lines) whose angles are restricted to a sector (wedge) of specified width σ. This provides an interesting measure of the degree of external visibility of a polygon. Our framework also permits a unification and extension of a number of previously unrelated results. Finally, our results uncover a curious complexity discontinuity in this family of problems; algorithms are Θ(n) when σ ≤ π or σ = 2π, but require Ω(n log n) time (at least), when π < σ < 2π.

We consider clustering problems under two different optimization criteria. One is to minimize the maximum intracluster distance (diameter), and the other is to maximize the minimum intercluster distance. In particular, we present an algorithm which partitions a set S of n points in the plane into two subsets so that their larger diameter is minimized in time Ο(n log n) and space Ο(n). Another algorithm with the same bounds computes a k-partition of S for any k so that the minimum intercluster distance is maximized. In both instances it is first shown that an optimal parition is determined by either a maximum or minimum spanning tree of S.

Recently, Snyder and Tang [1] proposed an algorithm for finding the diameter of a convex polygon. In this note a family of convex polygons is described for which their algorithm fails. It is also pointed out that the diameter of an arbitrary simple n-vertex polygon can be computed in O(n) time.