This article considers the problem of finding a shortest tour to visit viewing sets of points on a plane. Each viewing set is represented as an inverted view cone with apex angle alpha and height h. The apex of each c...
详细信息
This article considers the problem of finding a shortest tour to visit viewing sets of points on a plane. Each viewing set is represented as an inverted view cone with apex angle alpha and height h. The apex of each cone is restricted to lie on the ground plane. Its orientation angle (tilt) epsilon is the angle difference between the cone bisector and the ground plane normal. This is a novel variant of the 3D Traveling Salesman Problem with Neighborhoods (TSPN) called Cone-TSPN. One application of Cone-TSPN is to compute a trajectory to observe a given set of locations with a camera: for each location, we can generate a set of cones whose apex and orientation angles alpha and epsilon correspond to the camera's field of view and tilt. The height of each cone h corresponds to the desired resolution. Recently, Plonski and Isler presented an approximation algorithm for Cone-TSPN for the case where all cones have a uniform orientation angle of epsilon=0. We study a new variant of Cone-TSPN where we relax this constraint and allow the cones to have non-uniform orientations. We call this problem Tilted Cone-TSPN and present a polynomial-time approximation algorithm with ratio O(1+tan alpha 1-tan epsilon tan alpha(1+logmax(H)min(H))), where H is the set of all cone heights. We demonstrate through simulations that our algorithm can be implemented in a practical way and that by exploiting the structure of the cones we can achieve shorter tours. Finally, we present experimental results from various agriculture applications that show the benefit of considering view angles for path planning.
Given a k-vertex-connected graph G and a set S of extra edges (links), the goal of the k-vertex-connectivity augmentation problem is to find a subset S′ of S of minimum size such that adding S′ to G makes it (k+ 1 )...
详细信息
Graph routing problem (GRP) and its generalizations have been extensively studied because of their broad applications in the real world. In this paper, we study a variant of GRP called the general cluster routing prob...
详细信息
Graph parameters such as the diameter, radius, and vertex eccentricities are not defined in a useful way in Directed Acyclic Graphs (DAGs) using the standard measure of distance, since for any two nodes, there is no p...
详细信息
ISBN:
(纸本)9783959771955
Graph parameters such as the diameter, radius, and vertex eccentricities are not defined in a useful way in Directed Acyclic Graphs (DAGs) using the standard measure of distance, since for any two nodes, there is no path between them in one of the two directions. So it is natural to consider the distance between two nodes as the length of the shortest path in the direction in which this path exists, motivating the definition of the min-distance. The min-distance between two nodes u and v is the minimum of the shortest path distances from u to v and from v to u. As with the standard distance problems, the Strong Exponential Time Hypothesis [Impagliazzo- Paturi-Zane 2001, Calabro-Impagliazzo-Paturi 2009] leaves little hope for computing min-distance problems faster than computing All Pairs Shortest Paths, which can be solved in Õ(mn) time. So it is natural to resort to approximation algorithms in Õ(mn1-∈) time for some positive ∈. Abboud, Vassilevska W., and Wang [SODA 2016] first studied min-distance problems achieving constant factor approximation algorithms on DAGs, and Dalirrooyfard et al [ICALP 2019] gave the first constant factor approximation algorithms on general graphs for min-diameter, min-radius and min-eccentricities. Abboud et al obtained a 3-approximation algorithm for min-radius on DAGs which works in Õ(m√n) time, and showed that any (2 - δ)-approximation requires n2-o(1) time for any δ > 0, under the Hitting Set Conjecture. We close the gap, obtaining a 2-approximation algorithm which runs in Õ(m√n) time. As the lower bound of Abboud et al only works for sparse DAGs, we further show that our algorithm is conditionally tight for dense DAGs using a reduction from Boolean matrix multiplication. Moreover, Abboud et al obtained a linear time 2-approximation algorithm for min-diameter along with a lower bound stating that any (3/2 - δ)-approximation algorithm for sparse DAGs requires n2-o(1) time under SETH. We close this gap for dense DAGs by obtaining a 3/
In this paper, we study the maximum bounded connected bipartition problem (2-BCBP): given a vertex-weighted connected graph G= (V, E; w) and an upper bound B, the vertex set V is partitioned into two subsets denoted a...
详细信息
Designing and analyzing algorithms with provable performance guarantees enables efficient optimization problem solving in different application domains, e.g. communication networks, transportation, economics, and manu...
详细信息
Designing and analyzing algorithms with provable performance guarantees enables efficient optimization problem solving in different application domains, e.g. communication networks, transportation, economics, and manufacturing. Despite the significant contributions of approximation algorithms in engineering, only limited and isolated works contribute from this perspective in process systems engineering. The current paper discusses three representative, NP-hard problems in process systems engineering: (i) pooling, (ii) process scheduling, and (iii) heat exchanger network synthesis. We survey relevant results and raise major open questions. Further, we present approximation algorithms applications which are relevant to process systems engineering: (i) better mathematical modeling, (ii) problem classification, (iii) designing solution methods, and (iv) dealing with uncertainty. This paper aims to motivate further research at the intersection of approximation algorithms and process systems engineering. (C) 2019 Elsevier Ltd. All rights reserved.
We study the minimum connected sensor cover problem (MIN-CSC) and the budgeted connected sensor cover (Budgeted-CSC) problem, both motivated by important applications (e.g., reduce the communication cost among sensors...
详细信息
We study the minimum connected sensor cover problem (MIN-CSC) and the budgeted connected sensor cover (Budgeted-CSC) problem, both motivated by important applications (e.g., reduce the communication cost among sensors) in wireless sensor networks. In both problems, we are given a set of sensors and a set of target points in the Euclidean plane. In MIN-CSC, our goal is to find a set of sensors of minimum cardinality, such that all target points are covered, and all sensors can communicate with each other (i.e., the communication graph is connected). We obtain a constant factor approximation algorithm, assuming that the ratio between the sensor radius and communication radius is bounded. In Budgeted-CSC problem, our goal is to choose a set of B sensors, such that the number of targets covered by the chosen sensors is maximized and the communication graph is connected. We also obtain a constant approximation under the same assumption. (C) 2020 Published by Elsevier B.V.
In this paper, we consider the 1-line Euclidean minimum Steiner tree problem, which is a variation of the Euclidean minimum Steiner tree problem and defined as follows. Given a set P=of n points in the Euclidean plane...
详细信息
In this paper, we consider the 1-line Euclidean minimum Steiner tree problem, which is a variation of the Euclidean minimum Steiner tree problem and defined as follows. Given a set P=of n points in the Euclidean plane R2, we are asked to find the location of a line l and an Euclidean Steiner tree T(l) in R2 such that at least one Steiner point is located at such a line l, the objective is to minimize total weight of such an Euclidean Steiner tree T(l), i.e., min{ n-ary sumation e is an element of T(l)w(e)|T(l)\ is an Euclidean Steiner tree as mentioned-above}, where we define weight w(e)=0 if the end-points u, v of each edge e=uv is an element of T(l) are both located at such a line l and otherwise we denote weight w(e) to be the Euclidean distance between u and v. Given a fixed line l as an input in R2, we refer this problem as the 1-line-fixed Euclidean minimum Steiner tree problem;In addition, when Steiner points added are all located at such a fixed line l, we refer this problem as the constrained Euclidean minimum Steiner tree problem. We obtain the following two main results. (1) Using a polynomial-time exact algorithm to find a constrained Euclidean minimum Steiner tree, we can design a 1.214-approximation algorithm to solve the 1-line-fixed Euclidean minimum Steiner tree problem, and this algorithm runs in time O(nlogn);(2) Using a combination of the algorithm designed in Sect. 1 for many times, a technique of finding linear facility location and an important lemma proved by some techniques of computational geometry, we can provide a 1.214-approximation algorithm to solve the 1-line Euclidean minimum Steiner tree problem, and this new algorithm runs in time O(n(3)log n).
We consider the market mechanism to sell two types of products, A and B, to a set of buyers I={1,2,...n}. . The amounts of products are m(A) and m(B) respectively. Each buyer i has his information including the budget...
详细信息
We consider the market mechanism to sell two types of products, A and B, to a set of buyers I={1,2,...n}. . The amounts of products are m(A) and m(B) respectively. Each buyer i has his information including the budget, the preference and the utility function. On collecting the information from all buyers, the market maker determines the price of each product and allocates some amount of product to each buyer. The objective of the market maker is designing a mechanism to maximize the total utility of the buyers in satisfying the semi market equilibrium. In this paper, we show that this problem is NP-hard and give an iterative algorithm with the approximation ratio 1.5. Moreover, we introduce a PTAS for the problem, which is an (1+epsilon)-approximation algorithm with the running time O(2(1/epsilon) +n log n) for any positive epsilon.
An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S subset of V that maximizes the number of edges in the cut delta(S) such that t...
详细信息
An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S subset of V that maximizes the number of edges in the cut delta(S) such that the induced graph G[S] is connected. We present the first non-trivial Omega(1/log n) approximation algorithm for the Connected Maximum Cut problem in general graphs using novel techniques. We then extend our algorithm to edge weighted case and obtain a poly-logarithmic approximation algorithm. Interestingly, in contrast to the classical Max-Cut problem that can be solved in polynomial time on planar graphs, we show that the Connected Maximum Cut problem remains NP-hard on unweighted, planar graphs. On the positive side, we obtain a polynomial time approximation scheme for the Connected Maximum Cut problem on planar graphs and more generally on bounded genus graphs. (C) 2020 Elsevier B.V. All rights reserved.
暂无评论