Sensor infrastructures have become key enablers in collecting massive urban data. While representing an invaluable source of geographic information, high deployment costs of air quality stations relying on a chemical principle of operation leads to geographically imbalanced data. Typically, a minority of districts are equipped with such sensors or benefit from data collection campaigns, while others are data-poor. Moreover, the data available is highly heterogeneous, which adding on uncertainties. We present a methodology called ‘Smart Beestricts’ to improve the resolution of spatiotemporal data through Transfer Learning across districts of smart cities, based on: (i) aggregating spatiotemporal urban data into hexagonal grid representations, (ii) multi-variate clustering of the grid for discovering candidate regions for transfer, and (iii) transferring prediction models from data-rich sectors to data-poor ones. The transferred models are finally utilized to predict missing data across the city, thus improving spatiotemporal resolution. The methodology is validated in predicting missing air quality data in Madrid. The datasets generated are available through an open repository including meteorology, air pollution, and traffic data. Our methodology increased the spatial coverage of NO2 data from approximately 98 km2 to 253 km2, achieving coefficients of determination (R2) of up to 0.70 in the test regions.

Smart solutions increasingly involve the use of sensor data to represent the physical world in the digital world and apply intelligence to such representation. The main approach is a vertical end-to-end solution from sensors to intelligence and back to actuators. Recently, a new holistic approach, the so-called Digital Twin, has emerged. This goes beyond traditional smart solutions by replicating, with high-fidelity cross-domain aspects, a physical object into the digital world. The key differentiation is the inclusion of semantics information in the digital replica in a form of knowledge graph. Further, analytics continuously enrich Digital Twin’s information with predictions and insights. In this article, we adopt the Digital Twin approach for the creation of a digital replica of Espinardo’s campus at the University of Murcia (Spain). The starting point is the existing sensor network deployment and the infrastructure under development of Fog–Edge–Cloud computing based on a 5G private network. The smart campus Digital Twin is formed by the Digital Twins of 23 buildings for which different sets of data features have been thoroughly selected. We implement the concept of Digital Twin by merging sensor data with external open data sources, analytics models implemented, and information processed by these analytics. We report our experience showing the issues encountered handling the data and producing various analytics models for predicting energy consumption, building occupancy, room usage, solar energy, and anomaly detection. From our experience, we highlight some lessons learned and directions toward the full operational smart campus Digital Twin.

Application of deep learning to NP-hard combinatorial optimization problems is an emerging research trend, and a number of interesting approaches have been published over the last few years. In this work we address robust optimization, which is a more complex variant where a max-min problem is to be solved. We obtain robust solutions by solving the inner minimization problem exactly and apply Reinforcement Learning to learn a heuristic for the outer problem. The minimization term in the inner objective represents an obstacle to existing RL-based approaches, as its value depends on the full solution in a non-linear manner and cannot be evaluated for partial solutions constructed by the agent over the course of each episode. We overcome this obstacle by defining the reward in terms of the one-step advantage over a baseline policy whose role can be played by any fast heuristic for the given problem. The agent is trained to maximize the total advantage, which, as we show, is equivalent to the original objective. We validate our approach by solving min-max versions of standard benchmarks for the Capacitated Vehicle Routing and the Traveling Salesperson Problem, where our agents obtain near-optimal solutions and improve upon the baselines.

Automated hyperparameter tuning aspires to facilitate the application of machine learning for non-experts. In the literature, different optimization approaches are applied for that purpose. This paper investigates the performance of Differential Evolution for tuning hyperparameters of supervised learning algorithms for classification tasks. This empirical study involves a range of different machine learning algorithms and datasets with various characteristics to compare the performance of Differential Evolution with Sequential Model-based Algorithm Configuration (SMAC), a reference Bayesian Optimization approach. The results indicate that Differential Evolution outperforms SMAC for most datasets when tuning a given machine learning algorithm - particularly when breaking ties in a first-to-report fashion. Only for the tightest of computational budgets SMAC performs better. On small datasets, Differential Evolution outperforms SMAC by 19% (37% after tie-breaking). In a second experiment across a range of representative datasets taken from the literature, Differential Evolution scores 15% (23% after tie-breaking) more wins than SMAC.

We explore the opportunities and design options enabled by novel SDN and NFV technologies, by re-designing a dynamic content delivery network (CDN) service. Our system, named MOSTO, provides performance levels comparable to that of a regular CDN, but does not require the deployment of a large distributed infrastructure. In the process of designing the system, we identify relevant functions that could be integrated in the future Internet infrastructure. Such functions greatly simplify the design and effectiveness of services, such as MOSTO. We demonstrate our system using a mixture of simulation, emulation, testbed experiments, and by realizing a proof-of-concept deployment in a planet-wide commercial cloud system.

Web Service discovery a fundamental operation in SOA-based systems. In a landscape of Web Services that is growing in size and complexity, discovering a suitable atomic or composite Service for a given task requires a considerable amount of computation and communication resources, including semantic reasoning, the use of composition algorithms, and communication with multiple Service repositories. We study the approach of introducing a cache for Service discovery results to reduce the load on the backend discovery system. In this setting the bottleneck is the cache refresh frequency rather than the cache size, thus the caching algorithm needs to decide in which order to refresh the cached contents. We derive a theoretical upper bound on the number of cache hits possible to achieve for a given set of discovery queries, and we propose a number of heuristics for this caching problem, some of which turn out to have provable approximation guarantees. In an extensive experimental study we evaluate these methods. Our findings are that the best algorithms lead to a cache performance of more than 95 percent of the theoretical upper bound in all tested scenarios.

We consider a single-machine scheduling problem. Given some continuous, nondecreasing cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is determined by the cost function value at its completion time. This problem is closely related to scheduling a single machine with nonuniform processing speed. We show that for piecewise linear cost functions it is strongly NP-hard. The main contribution of this article is a tight analysis of the approximation guarantee of Smith’s rule under any convex or concave cost function. More specifically, for these wide classes of cost functions we reduce the task of determining a worst-case problem instance to a continuous optimization problem, which can be solved by standard algebraic or numerical methods. For polynomial cost functions with positive coefficients, it turns out that the tight approximation ratio can be calculated as the root of a univariate polynomial. We show that this approximation ratio is asymptotically equal to k ( k − 1)/( k + 1) , denoting by k the degree of the cost function. To overcome unrealistic worst-case instances, we also give tight bounds for the case of integral processing times that are parameterized by the maximum and total processing time.

We study the problem of extracting information from social networks whose structure is initially unknown. Given a network G = (V, E) with unknown edge set E, the objective is to discover as many links as possible by applying a limited number of edge tests. Each such test reveals for a given pair of nodes v1, v2∈ V whether or not they are connected. Outcomes of previous tests can be taken into account for deciding which edge to test next. As a basic approach to this link discovery problem, we evaluate the performance of a number of scoring functions which have been proposed for predicting the future evolution of social networks. Furthermore, we develop a mechanism to apply supervised learning methods to the link discovery problem, where edge tests are utilized both for feature extraction and training sample generation. Our experiments with real and synthetic social networks demonstrate that, despite the sparsity of social network graphs, link discovery methods show a success rate improving upon random guessing by factors of up to 7. In addition, we also evaluate our link discovery methods in the context of an application where the nodes of the graph represent moving objects and only links to nearby objects are beneficial to be discovered. Also here we achieve comparable success rates.

We consider the problem of scheduling jobs on a single machine. Given a quadratic cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is defined as the cost function value at the job's completion time. Throughout the past decades, great effort has been made to develop fast exact algorithms for the case of quadratic costs. The efficiency of these methods heavily depends on the utilization of structural properties of optimal schedules such as order constraints, i.e., sufficient conditions for pairs of jobs to appear in a certain order. A considerable number of different kinds of such constraints have been proposed. In this work we enhance the map of known order constraints by proving an extended version of a constraint that has been conjectured by Mondal and Sen more than a decade ago. Besides proving this conjecture, our main contribution is an extensive experimental study where the influence of different kinds order constraints on the performance of exact algorithms is systematically evaluated. In addition to a best-first graph search algorithm, we test a Quadratic Integer Programming formulation that admits to add order constraints as additional linear constraints. We also evaluate the optimality gap of well known Smith's rule for different monomial cost functions. Our experiments are based on sets of problem instances that have been generated using a new method which allows us to adjust a certain degree of difficulty of the instances.

The concept of hotlink assignment aims at reducing the navigation effort for the users of a Web directory or similar structure by inserting a limited number of additional hyperlinks called hotlinks . The k -hotlink assignment problem denotes the task of adding at most k outgoing hotlinks to each page of a tree-like site, minimizing the path length , that is, the expected number of “clicks” necessary for the user to reach her destination page. Another common formulation of this problem is to maximize the gain , that is, the path length reduction achieved by the assignment. In this work we analyze the natural greedy strategy, proving that it reaches the optimal gain up to the constant factor of 2. Considering the gain, we also prove the existence of a PTAS. Finally, we give a polynomial-time 2-approximation for the 1-hotlink assignment problem, which constitutes the first constant factor approximation in terms of the path length. The algorithms' performance analyses are made possible by a set of three new basic operations for the transformation of hotlink assignments.

The concept of hotlink assignment aims at enhancing the structure of web sites such that the user's expected navigation effort is minimized. We concentrate on sites that are representable by trees and assume that each leaf carries a weight representing its popularity. The problem of optimally adding at most one additional outgoing edge (hotlink) to each inner node has been widely studied. A considerable number of approximation algorithms have been proposed and worst-case bounds for the quality of the computed solutions have been given. However, only little is known about the practical behaviour of most of these algorithms yet. This paper contributes to close this gap by evaluating all recent strategies experimentally. Our experiments are based on trees extracted from real websites as well as on synthetic instances. The latter are generated by a new method that simulates the growth of a web site over time. We also propose a memory-efficient way to implement an optimal hotlink assignment algorithm, making it possible to compute optimal solutions for larger instances than before. Finally, we present a new approximation algorithm that is easy to implement and exhibits an excellent behaviour in practice.