| 1. |
- Alt, Helmut, et al.
(författare)
-
Scandinavian Thins on Top of Cake : New and Improved Algorithms for Stacking and Packing
- 2014
-
Ingår i: Theory of Computing Systems. - : Springer Science and Business Media LLC. - 1432-4350 .- 1433-0490. ; 54:4, s. 689-714
-
Tidskriftsartikel (refereegranskat)abstract
- We show how to compute the smallest rectangle that can enclose any polygon, from a given set of polygons, in nearly linear time; we also present a PTAS for the problem, as well as a linear-time algorithm for the case when the polygons are rectangles themselves. We prove that finding a smallest convex polygon that encloses any of the given polygons is NP-hard, and give a PTAS for minimizing the perimeter of the convex enclosure. We also give efficient algorithms to find the smallest rectangle simultaneously enclosing a given pair of convex polygons.
|
|
| 2. |
- Angelakis, Vangelis, et al.
(författare)
-
BBTM: New life for old ATM
- 2016
-
Ingår i: 2016 IEEE/AIAA 35TH DIGITAL AVIONICS SYSTEMS CONFERENCE (DASC). - : IEEE. - 9781509025237
-
Konferensbidrag (refereegranskat)abstract
- This paper investigates algorithmic questions related to the possibility of managing UAV traffic with beacon-based navigation, which we dub BBTM - Beacon-Based Traffic Management. The specific problem addressed is: How to install the minimum number of beacons in a mountainous terrain to ensure connectivity among a given set of UAS terminals on the terrain? BBTM is relevant for low-cost UAVs operating in remote areas not on time-critical missions, and may also be used as a backup system for better-equipped UAS in case the precise positioning or control information is lost, spoofed or jammed. We give algorithms for the beacon tower placement and evaluate their performance both on synthetic and real-world terrain data; the experiments suggest that our solutions can be used to efficiently quantify costs of establishing direct-visibility routing networks for UAS management.
|
|
| 3. |
- Arkin, Esther M, et al.
(författare)
-
Shortest path to a segment and quickest visibility queries
- 2016
-
Ingår i: LIPIcs-Leibniz International Proceedings in Informatics. ; , s. 77-100
-
Konferensbidrag (refereegranskat)abstract
- We show how to preprocess a polygonal domain with a xed starting point s in order to answer eciently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortestpath- to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a di erent generalization of shortest-path-to-a-point queries, which may be of independent interest: to report eciently a shortest path from s to a query segment in the domain.
|
|
| 4. |
- Aronov, Boris, et al.
(författare)
-
Are Friends of My Friends Too Social? Limitations of Location Privacy in a Socially-Connected World
- 2018
-
Ingår i: PROCEEDINGS OF THE 2018 THE NINETEENTH INTERNATIONAL SYMPOSIUM ON MOBILE AD HOC NETWORKING AND COMPUTING (MOBIHOC 18). - New York, NY, USA : ASSOC COMPUTING MACHINERY. - 9781450357708 ; , s. 280-289
-
Konferensbidrag (refereegranskat)abstract
- With the ubiquitous adoption of smartphones and mobile devices, it is now common practice for ones location to be sensed, collected and likely shared through social platforms. While such data can be helpful for many applications, users start to be aware of the privacy issue in handling location and trajectory data. While some users may voluntarily share their location information (e.g., for receiving location-based services, or for crowdsourcing systems), their location information may lead to information leaks about the whereabouts of other users, through the co-location of events when two users are at the same location at the same time and other side information, such as upper bounds of movement speed. It is therefore crucial to understand how much information one can derive about others positions through the co-location of events and occasional GPS location leaks of some of the users. In this paper we formulate the problem of inferring locations of mobile agents, present theoretically-proven bounds on the amount of information that could be leaked in this manner, study their geometric nature, and present algorithms matching these bounds. We will show that even if a very weak set of assumptions is made on trajectories patterns, and users are not obliged to follow any reasonable patterns, one could infer very accurate estimation of users locations even if they opt not to share them. Furthermore, this information could be obtained using almost linear-time algorithms, suggesting the practicality of the method even for huge volumes of data.
|
|
| 5. |
- Efrat, Alon, et al.
(författare)
-
Improved Approximation Algorithms for Relay Placement
- 2016
-
Ingår i: ACM Transactions on Algorithms. - : ACM Press. - 1549-6325 .- 1549-6333. ; 12:2, s. 20-
-
Tidskriftsartikel (refereegranskat)abstract
- In the relay placement problem, the input is a set of sensors and a number r >= 1, the communication range of a relay. In the one-tier version of the problem, the objective is to place a minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays such that the consecutive vertices of the path are within distance r if both vertices are relays and within distance 1 otherwise. The two-tier version adds the restrictions that the path must go through relays, and not through sensors. We present a 3.11-approximation algorithm for the one-tier version and a polynomial-time approximation scheme (PTAS) for the two-tier version. We also show that the one-tier version admits no PTAS, assuming P not equal NP.
|
|
| 6. |
- Krechetov, Mikhail, et al.
(författare)
-
Prediction and prevention of pandemics via graphical model inference and convex programming
- 2022
-
Ingår i: Scientific Reports. - : Nature Portfolio. - 2045-2322. ; 12:1
-
Tidskriftsartikel (refereegranskat)abstract
- Hard-to-predict bursts of COVID-19 pandemic revealed significance of statistical modeling which would resolve spatio-temporal correlations over geographical areas, for example spread of the infection over a city with census tract granularity. In this manuscript, we provide algorithmic answers to the following two inter-related public health challenges of immense social impact which have not been adequately addressed (1) Inference Challenge assuming that there are N census blocks (nodes) in the city, and given an initial infection at any set of nodes, e.g. any N of possible single node infections, any N(N - 1)/2 of possible two node infections, etc, what is the probability for a subset of census blocks to become infected by the time the spread of the infection burst is stabilized? (2) Prevention Challenge What is the minimal control action one can take to minimize the infected part of the stabilized state footprint? To answer the challenges, we build a Graphical Model of pandemic of the attractive !sing (pair-wise, binary) type, where each node represents a census tract and each edge factor represents the strength of the pairwise interaction between a pair of nodes, e.g. representing the inter-node travel, road closure and related, and each local bias/field represents the community level of immunization, acceptance of the social distance and mask wearing practice, etc. Resolving the Inference Challenge requires finding the Maximum-A-Posteriory (MAP), i.e. most probable, state of the !sing Model constrained to the set of initially infected nodes. (An infected node is in the +1state and a node which remained safe is in the - 1 state.) We show that almost all attractive !sing Models on dense graphs result in either of the two possibilities (modes) for the MAP state: either all nodes which were not infected initially became infected, or all the initially uninfected nodes remain uninfected (susceptible). This bi-modal solution of the Inference Challenge allows us to re-state the Prevention Challenge as the following tractable convex programming: for the bare !sing Model with pair-wise and bias factors representing the system without prevention measures, such that the MAP state is fully infected for at least one of the initial infection patterns, find the closest, for example in l(1), l(2) or any other convexity-preserving norm, therefore prevention-optimal, set of factors resulting in all the MAP states of the !sing model, with the optimal prevention measures applied, to become safe. We have illustrated efficiency of the scheme on a quasi-realistic model of Seattle. Our experiments have also revealed useful features, such as sparsity of the prevention solution in the case of the l(1) norm, and also somehow unexpected features, such as localization of the sparse prevention solution at pair-wise links which are NOT these which are most utilized/traveled.
|
|
| 7. |
|
|
| 8. |
- Sankararaman, Swaminathan, et al.
(författare)
-
Optimization schemes for protective jamming
- 2014
-
Ingår i: Mobile Networks and Applications. - : Springer Science and Business Media LLC. - 1383-469X .- 1572-8153. ; 19:1, s. 45-60
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper, we study strategies for allocating and managing friendly jammers, so as to create virtual barriers that would prevent hostile eavesdroppers from tapping sensitive wireless communication. Our scheme precludes the use of any encryption technique. Applications include domains such as (i) protecting the privacy of storage locations where RFID tags are used for item identication, (ii) secure reading of RFID tags embedded in credit cards, (iii) protecting data transmitted through wireless networks, sensor networks, etc. By carefully managing jammers to produce noise, we show how to reduce the SINR of eavesdroppers to below a threshold for successful reception, without jeopardizing network performance. We present algorithms targeted towards optimizing power allocation and number of jammers needed in several settings. Experimental simulations back up our results.
|
|
