The d-dimensional weighted region shortest path problem asks for finding a shortest path between two given points s and t in a d-dimensional polyhedral structure consisting of polyhedral cells having ...individual positive weights. It is a generalization of the d-dimensional unweighted (Euclidean) shortest path problem for polyhedral structures.
In the unweighted (Euclidean) setting, a shortest path visits, due to cell convexity, each polyhedral cell at most once. Surprisingly, this is no longer true for the weighted setting, which is a strong motivation for studying the complexity of weighted shortest paths in polyhedral structures.
Previously, Ω(n2), respectively Ω(n3) lower bounds on the maximum number of cell crossings for weighted shortest paths in 2-dimensional, respectively 3-dimensional polyhedral structures have been obtained.
In this paper, a new lower bound of Ω(nd) is derived on the maximum number of cell crossings a weighted shortest path could take in d-dimensional polyhedral structures consisting of a linear number of O(n) polyhedral cells and cell faces. This new result is a generalization and sharpening of the formerly known lower bounds and has been a long-standing open problem for the general d-dimensional case.
From smartphones owned by the majority of teenage and adult populations to omnipresent closed-circuit television systems, the ubiquity of image-capturing devices in our everyday lives ensures that ...digital images of individuals are taken in the hundreds of millions on a daily basis. Many of these images capture individuals’ faces which, through facial recognition techniques, identify the individuals and thus represent a major privacy concern. Many countries and companies require facial obfuscation to conform to privacy laws or policies. Since images should be useful and look realistic, a trade-off arises between privacy and utility. The task is therefore to find a method of obfuscation that offers a formal privacy guarantee while preserving visual quality and maintaining facial attributes deemed acceptable for release (e.g., the pose of the head, gender, etc.). We address this task by proposing facial identity obfuscation through the application of differential privacy to image encodings in a generative adversarial network. We provide details on the design of the model architecture and training process that allow for the generation of photo-realistic obfuscated images. Through the use of principal component analysis, we control the application of noise to the model encodings in order to achieve a favourable trade-off between privacy and utility. We demonstrate the effectiveness of our approach through an experimental comparison against other methods of obfuscation which also offer a formal guarantee of privacy.
•Facial obfuscation via differential privacy in a generative adversarial network.•Principal component analysis combined with generalized differential privacy.•Theoretical and practical interpretations of distance-generalized privacy guarantee.•Results demonstrate photo-realistic obfuscated images with utility preservation.
•Recast CiteScore prediction as prediction of inputs for the final CiteScore year.•Identified effective hyperparameter configurations for 7 predictive models.•Provided a detailed breakdown of ...performance for each predictive model.•Obtained the best performance among the models from a recurrent neural net.
Prediction of the future performance of academic journals is a task that can benefit a variety of stakeholders including editorial staff, publishers, indexing services, researchers, university administrators and granting agencies. Using historical data on journal performance, this can be framed as a machine learning regression problem. In this work, we study two such regression tasks: 1) prediction of the number of citations a journal will receive during the next calendar year, and 2) prediction of the Elsevier CiteScore a journal will be assigned for the next calendar year. To address these tasks, we first create a dataset of historical bibliometric data for journals indexed in Scopus. We propose the use of neural network models trained on our dataset to predict the future performance of journals. To this end, we perform feature selection and model configuration for a Multi-Layer Perceptron and a Long Short-Term Memory. Through experimental comparisons to heuristic prediction baselines and classical machine learning models, we demonstrate superior performance in our proposed models for the prediction of future citation and CiteScore values.
Continuous and discrete models as well as algorithms Bressan (2007) and Finbow and MacGillivray (2009) for firefighting problems are well-studied in Theoretical Computer Science. We introduce a new, ...discrete, and more general framework based on a graph to study firefighting problems in various terrains. In the context of this model, we present two different firefighting problems called village protection problems, where the goal is to protect a specific set of locations and provide efficient polynomial time algorithms for their solutions. We also discuss extensions of the model.
Constituting the refereed proceedings of the 12th Algorithms and Data Structures Symposium held in New York in August 2011, this text presents original research on the theory and application of ...algorithms and data structures in all areas, including combinatorics, computational geometry and databases.
The papers in this volume were presented at the 10th Workshop on Algorithms and Data Structures (WADS 2005). The workshop took place August 15 - 17, 2007, at Dalhousie University, Halifax, Canada. ...The workshop alternates with the Scandinavian Workshop on Algorithm Theory (SWAT), continuing the t- dition of SWAT and WADS starting with SWAT 1988 and WADS 1989. From 142 submissions, the Program Committee selected 54 papers for presentation at the workshop. In addition, invited lectures were given by the following dist- guished researchers: Je? Erickson (University of Illinois at Urbana-Champaign) and Mike Langston (University of Tennessee). On behalf of the Program Committee, we would like to express our sincere appreciation to the many persons whose e?ort contributed to making WADS 2007 a success. These include the invited speakers, members of the Steering and ProgramCommittees, the authorswho submitted papers, andthe manyreferees who assisted the Program Committee. We are indebted to Gerardo Reynaga for installing and modifying the submission software, maintaining the submission server and interacting with authors as well as for helping with the preparation of the program.
Algorithms and Data Structures Dehne, Frank; López-Ortiz, Alejandro; Sack, Jörg-Rüdiger
2005, 2005-08-04, Letnik:
3608
eBook
A collection of papers that address searching and sorting, approximation, graph and network computations, computational geometry, randomization, communications, combinatorial optimization, ...scheduling, routing, navigation, coding, and pattern matching.
We revisit the problem of deciding whether a given curve resembles some
part
of a larger curve under a fixed Fréchet distance, achieving a running time of
O
(
nm
), for
n
and
m
being the number of ...segments in the two curves. This improves the long-standing result of Alt and Godau by an
O
(log(
nm
)) factor. Our solution is based on constructing a simple data structure which we call
free-space map
. Using this data structure, we obtain improved algorithms for several variants of the Fréchet distance problem, including the Fréchet distance between two closed curves, and the so-called minimum/maximum walk problems. We also improve the map matching algorithm of Alt et al. for the particular case in which the map is a directed acyclic graph.
Motivated by a security problem in geographic information systems, we study the following graph theoretical problem: given a graph
G
, two special nodes
s
and
t
in
G
, and a number
k
, find
k
paths ...from
s
to
t
in
G
so as to minimize the number of edges shared among the paths. This is a generalization of the well-known disjoint paths problem. While disjoint paths can be computed efficiently, we show that finding paths with minimum shared edges is NP-hard. Moreover, we show that it is even hard to approximate the minimum number of shared edges within a factor of
, for any constant
ε
>0. On the positive side, we show that there exists a (
k
−1)-approximation algorithm for the problem, using an adaption of a network flow algorithm. We design some heuristics to improve the quality of the output, and provide empirical results.
In this paper, we study the
time-dependent shortest paths problem
for two types of time-dependent FIFO networks. First, we consider networks where the availability of links, given by a set of ...disjoint time intervals for each link, changes over time. Here, each interval is assigned a non-negative real value which represents the travel time on the link during the corresponding interval. The resulting shortest path problem is the time-dependent shortest path problem for availability intervals (
), which asks to compute all shortest paths to any (or all) destination node(s)
d
for all possible start times at a given source node
s
. Second, we study time-dependent networks where the cost of using a link is given by a non-decreasing piece-wise linear function of a real-valued argument. Here, each piece-wise linear function represents the travel time on the link based on the time when the link is used. The resulting shortest paths problem is the time-dependent shortest path problem for piece-wise linear functions (
) which asks to compute, for a given source node
s
and destination
d
, the shortest paths from
s
to
d
, for all possible starting times.
We present an algorithm for the
problem that runs in time
O
((
F
d
+
γ
)(|
E
|+|
V
|log |
V
|)) where
F
d
is the output size (i.e., number of linear pieces needed to represent the earliest arrival time function to
d
) and
γ
is the input size (i.e., number of linear pieces needed to represent the local earliest arrival time functions for all links in the network). We then solve the
problem in
O
(
λ
(|
E
|+|
V
|log |
V
|)) time by reducing it to an instance of the
problem. Here,
λ
denotes the total number of availability intervals in the entire network. Both methods improve significantly on the previously known algorithms.
PDF
