OpenRaiser/Intern-Atlas huggingface dataset:
Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set
Venue: arXiv cs.DS 2018
Year: 2018

Feedback Vertex Set is a classic combinatorial optimization problem that asks for a minimum set of vertices in a given graph whose deletion makes the graph acyclic. From the point of view of parameterized algorithms and fixed-parameter tractability, Feedback Vertex Set is one of the landmark problems: a long line of study resulted in multiple algorithmic approaches and deep understanding of the combinatorics of the problem. Because of its central role in parameterized complexity, the first edition of the Parameterized Algorithms and Computational Experiments Challenge (PACE) in 2016 featured Feedback Vertex Set as the problem of choice in one of its tracks. The results of PACE 2016 on one hand showed large discrepancy between performance of different classic approaches to the problem, and on the other hand indicated a new approach based on half-integral relaxations of the problem as probably the most efficient approach to the problem. In this paper we provide an exhaustive experimental evaluation of fixed-parameter and branching algorithms for Feedback Vertex Set.
An Overview of Robust Subspace Recovery
Venue: arXiv cs.LG 2018
Year: 2018

This paper will serve as an introduction to the body of work on robust subspace recovery. Robust subspace recovery involves finding an underlying low-dimensional subspace in a dataset that is possibly corrupted with outliers. While this problem is easy to state, it has been difficult to develop optimal algorithms due to its underlying nonconvexity. This work emphasizes advantages and disadvantages of proposed approaches and unsolved problems in the area.
Specialized Interior Point Algorithm for Stable Nonlinear System Identification
Venue: arXiv cs.SY 2018
Year: 2018

Estimation of nonlinear dynamic models from data poses many challenges, including model instability and non-convexity of long-term simulation fidelity. Recently Lagrangian relaxation has been proposed as a method to approximate simulation fidelity and guarantee stability via semidefinite programming (SDP), however the resulting SDPs have large dimension, limiting their utility in practical problems. In this paper we develop a path-following interior point algorithm that takes advantage of special structure in the problem and reduces computational complexity from cubic to linear growth with the length of the data set. The new algorithm enables empirical comparisons to established methods including Nonlinear ARX, and we demonstrate superior generalization to new data. We also explore the "regularizing" effect of stability constraints as an alternative to regressor subset selection.
Model-Based Stochastic Search for Large Scale Optimization of Multi-Agent UAV Swarms
Venue: arXiv cs.MA 2018
Year: 2018

Recent work from the reinforcement learning community has shown that Evolution Strategies are a fast and scalable alternative to other reinforcement learning methods. In this paper we show that Evolution Strategies are a special case of model-based stochastic search methods. This class of algorithms has nice asymptotic convergence properties and known convergence rates. We show how these methods can be used to solve both cooperative and competitive multi-agent problems in an efficient manner. We demonstrate the effectiveness of this approach on two complex multi-agent UAV swarm combat scenarios: where a team of fixed wing aircraft must attack a well-defended base, and where two teams of agents go head to head to defeat each other.
On Developers' Personality in Large-scale Distributed Projects: The Case of the Apache Ecosystem
Venue: arXiv cs.SE 2018
Year: 2018

Large-scale distributed projects are typically the results of collective efforts performed by multiple developers, each one having a different personality. The study of developers' personalities has the potential of explaining their' behavior in various contexts. For example, the propensity to trust others, a critical factor to the success of global software engineering - has been found to influence positively the result of code reviews in distributed projects. In this paper, we perform a quantitative analysis of developers' personality in open source software projects, intended as an extreme form of distributed projects in which no single organization controls the project. We mine ecosystem-level data from the code commits and email messages contributed by the developers working on the Apache Software Foundation (ASF) projects, as representative of large scale-distributed projects. We find that developers become over time more conscientious, agreeable, and neurotic. Moreover, personality traits do not vary with their role, membership, and extent of contribution to the projects. We also find evidence that more open and more agreeable developers are more likely to become project contributors.
Coverage and Connectivity Analysis of Millimeter Wave Vehicular Networks
Venue: arXiv cs.NI 2018
Year: 2018

The next generations of vehicles will require data transmission rates in the order of terabytes per driving hour, to support advanced automotive services. This unprecedented amount of data to be exchanged goes beyond the capabilities of existing communication technologies for vehicular communication and calls for new solutions. A possible answer to this growing demand for ultra-high transmission speeds can be found in the millimeter-wave (mmWave) bands which, however, are subject to high signal attenuation and challenging propagation characteristics. In particular, mmWave links are typically directional, to benefit from the resulting beamforming gain, and require precise alignment of the transmitter and the receiver beams, an operation which may increase the latency of the communication and lead to deafness due to beam misalignment. In this paper, we propose a stochastic model for characterizing the beam coverage and connectivity probability in mmWave automotive networks. The purpose is to exemplify some of the complex and interesting tradeoffs that have to be considered when designing solutions for vehicular scenarios based on mmWave links. The results show that the performance of the automotive nodes in highly mobile mmWave systems strictly depends on the specific environment in which the vehicles are deployed, and must account for several automotive-specific features such as the nodes speed, the beam alignment periodicity, the base stations density and the antenna geometry.
Security issues in a group key establishment protocol
Venue: arXiv cs.CR 2018
Year: 2018

Major shortcomings in a recently published group key establishment protocol are described. These shortcomings are sufficiently serious that the protocol should not be used.
Management of Network Slicing in 5G Radio Access Networks: Functional Framework and Information Models
Venue: arXiv cs.NI 2018
Year: 2018

Network slicing is one of the key features for 5G networks to be able to accommodate the anticipated diversity of applications and business actors in a resource-efficient manner. While significant progress has already been achieved at 3GPP specifications level with regard to the system architectural and functional aspects for the realisation of network slicing in 5G networks, management solutions for the exploitation of this feature in the Next Generation Radio Access Network (NG-RAN) are still at a very incipient stage. In this context, this paper presents a framework for the management of network slicing in a NG-RAN infrastructure, identifying the functions, interfaces and information models that are necessary to enable the automation of the RAN slicing provisioning and management processes. Accordingly, a plausible information model intended to describe the manageable characteristics and behaviour of a RAN slice is developed and its applicability discussed in an illustrative neutral host provider scenario.
Designing Interactions with Furniture: Towards Multi-Sensorial Interaction Design Processes for Interactive Furniture
Venue: arXiv cs.HC 2018
Year: 2018

In this paper, we argue for novel user experience design methods, in the context of reimagining ergonomics of interactive furniture.
AdaM: Adapting Multi-User Interfaces for Collaborative Environments in Real-Time
Venue: arXiv cs.HC 2018
Year: 2018

Developing cross-device multi-user interfaces (UIs) is a challenging problem. There are numerous ways in which content and interactivity can be distributed. However, good solutions must consider multiple users, their roles, their preferences and access rights, as well as device capabilities. Manual and rule-based solutions are tedious to create and do not scale to larger problems nor do they adapt to dynamic changes, such as users leaving or joining an activity. In this paper, we cast the problem of UI distribution as an assignment problem and propose to solve it using combinatorial optimization. We present a mixed integer programming formulation which allows real-time applications in dynamically changing collaborative settings. It optimizes the allocation of UI elements based on device capabilities, user roles, preferences, and access rights. We present a proof-of-concept designer-in-the-loop tool, allowing for quick solution exploration. Finally, we compare our approach to traditional paper prototyping in a lab study.
Byzantine-Resilient Locally Optimum Detection Using Collaborative Autonomous Networks
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, we propose a locally optimum detection (LOD) scheme for detecting a weak radioactive source buried in background clutter. We develop a decentralized algorithm, based on alternating direction method of multipliers (ADMM), for implementing the proposed scheme in autonomous sensor networks. Results show that algorithm performance approaches the centralized clairvoyant detection algorithm in the low SNR regime, and exhibits excellent convergence rate and scaling behavior (w.r.t. number of nodes). We also devise a low-overhead, robust ADMM algorithm for Byzantine-resilient detection, and demonstrate its robustness to data falsification attacks.
GAN-based Synthetic Medical Image Augmentation for increased CNN Performance in Liver Lesion Classification
Venue: arXiv cs.CV 2018
Year: 2018

Deep learning methods, and in particular convolutional neural networks (CNNs), have led to an enormous breakthrough in a wide range of computer vision tasks, primarily by using large-scale annotated datasets. However, obtaining such datasets in the medical domain remains a challenge. In this paper, we present methods for generating synthetic medical images using recently presented deep learning Generative Adversarial Networks (GANs). Furthermore, we show that generated medical images can be used for synthetic data augmentation, and improve the performance of CNN for medical image classification. Our novel method is demonstrated on a limited dataset of computed tomography (CT) images of 182 liver lesions (53 cysts, 64 metastases and 65 hemangiomas). We first exploit GAN architectures for synthesizing high quality liver lesion ROIs. Then we present a novel scheme for liver lesion classification using CNN. Finally, we train the CNN using classic data augmentation and our synthetic data augmentation and compare performance. In addition, we explore the quality of our synthesized examples using visualization and expert assessment. The classification performance using only classic data augmentation yielded 78.6% sensitivity and 88.4% specificity. By adding the synthetic data augmentation the results increased to 85.7% sensitivity and 92.4% specificity. We believe that this approach to synthetic data augmentation can generalize to other medical classification applications and thus support radiologists' efforts to improve diagnosis.
A Swift Heuristic Method for Work Order Scheduling under the Skilled-Workforce Constraint
Venue: arXiv cs.AI 2018
Year: 2018

The considered problem is how to optimally allocate a set of jobs to technicians of different skills such that the number of technicians of each skill does not exceed the number of persons with that skill designation. The key motivation is the quick sensitivity analysis in terms of the workforce size which is quite necessary in many industries in the presence of unexpected work orders. A time-indexed mathematical model is proposed to minimize the total weighted completion time of the jobs. The proposed model is decomposed into a number of single-skill sub-problems so that each one is a combination of a series of nested binary Knapsack problems. A heuristic procedure is proposed to solve the problem. Our experimental results, based on a real-world case study, reveal that the proposed method quickly produces a schedule statistically close to the optimal one while the classical optimal procedure is very time-consuming.
Study of a Dynamic Cooperative Trading Queue Routing Control Scheme for Freeways and Facilities with Parallel Queues
Venue: arXiv cs.GT 2018
Year: 2018

This article explores the coalitional stability of a new cooperative control policy for freeways and parallel queuing facilities with multiple servers. Based on predicted future delays per queue or lane, a VOT-heterogeneous population of agents can agree to switch lanes or queues and transfer payments to each other in order to minimize the total cost of the incoming platoon. The strategic interaction is captured by an n-level Stackelberg model with coalitions, while the cooperative structure is formulated as a partition function game (PFG). The stability concept explored is the strong-core for PFGs which we found appropiate given the nature of the problem. This concept ensures that the efficient allocation is individually rational and coalitionally stable. We analyze this control mechanism for two settings: a static vertical queue and a dynamic horizontal queue. For the former, we first characterize the properties of the underlying cooperative game. Our simulation results suggest that the setting is always strong-core stable. For the latter, we propose a new relaxation program for the strong-core concept. Our simulation results on a freeway bottleneck with constant outflow using Newell's car-following model show the imputations to be generally strong-core stable and the coalitional instabilities to remain small with regard to users' costs.
Station Assignment with Reallocation
Venue: arXiv cs.DS 2018
Year: 2018

We study a dynamic allocation problem that arises in various scenarios where mobile clients joining and leaving the system have to communicate with static stations via radio transmissions. Restrictions are a maximum delay, or laxity, between consecutive client transmissions and a maximum bandwidth that a station can share among its clients. We study the problem of assigning clients to stations so that every client transmits to some station, satisfying those restrictions. We consider reallocation algorithms, where clients are revealed at its arrival time, the departure time is unknown until they leave, and clients may be reallocated to another station, but at a cost proportional to the reciprocal of the client laxity. We present negative results for previous related protocols that motivate the study; we introduce new protocols that expound trade-offs between station usage and reallocation cost; we determine experimentally a classification of the clients attempting to balance those opposite goals; we prove theoretically bounds on our performance metrics; and we show through simulations that, for realistic scenarios, our protocols behave much better than our theoretical guarantees.
Maximizing Efficiency in Dynamic Matching Markets
Venue: arXiv cs.DS 2018
Year: 2018

We study the problem of matching agents who arrive at a marketplace over time and leave after d time periods. Agents can only be matched while they are present in the marketplace. Each pair of agents can yield a different match value, and the planner's goal is to maximize the total value over a finite time horizon. We study matching algorithms that perform well over any sequence of arrivals when there is no a priori information about the match values or arrival times. Our main contribution is a 1/4-competitive algorithm. The algorithm randomly selects a subset of agents who will wait until right before their departure to get matched, and maintains a maximum-weight matching with respect to the other agents. The primal-dual analysis of the algorithm hinges on a careful comparison between the initial dual value associated with an agent when it first arrives, and the final value after d time steps. It is also shown that no algorithm is 1/2-competitive. We extend the model to the case in which departure times are drawn i.i.d from a distribution with non-decreasing hazard rate, and establish a 1/8-competitive algorithm in this setting. Finally we show on real-world data that a modified version of our algorithm performs well in practice.
The effect of twitter-mediated activities on learning outcome and student engagement: A case study
Venue: arXiv cs.CY 2018
Year: 2018

The study reported in this paper, examines the effects of a rigorously designed introduction of Twitter in the educational process. In specific, it examines the relation between the students use of Twitter in the context of well-organized educational activities and their grades in an academic course. The results demonstrated a significant correlation between the use of Twitter by the students and their performance in the course. Moreover, it emerged that their participation on Twitter, could improve the students academic engagement and their sense of belonging to the academic community. Finally, possible effects of Twitter s use on students perceived internet self-efficacy were also examined. The findings and their implications of the study are discussed in detail.
SAFE: Spectral Evolution Analysis Feature Extraction for Non-Stationary Time Series Prediction
Venue: arXiv cs.LG 2018
Year: 2018

This paper presents a practical approach for detecting non-stationarity in time series prediction. This method is called SAFE and works by monitoring the evolution of the spectral contents of time series through a distance function. This method is designed to work in combination with state-of-the-art machine learning methods in real time by informing the online predictors to perform necessary adaptation when a non-stationarity presents. We also propose an algorithm to proportionally include some past data in the adaption process to overcome the Catastrophic Forgetting problem. To validate our hypothesis and test the effectiveness of our approach, we present comprehensive experiments in different elements of the approach involving artificial and real-world datasets. The experiments show that the proposed method is able to significantly save computational resources in term of processor or GPU cycles while maintaining high prediction performances.
Process Ordering in a Process Calculus for Spatially-Explicit Ecological Models
Venue: arXiv cs.LO 2018
Year: 2018

In this paper we extend PALPS, a process calculus proposed for the spatially-explicit individual-based modeling of ecological systems, with the notion of a policy. A policy is an entity for specifying orderings between the different activities within a system. It is defined externally to a PALPS model as a partial order which prescribes the precedence order between the activities of the individu- als of which the model is comprised. The motivation for introducing policies is twofold: one the one hand, policies can help to reduce the state-space of a model, on the other hand, they are useful for exploring the behavior of an ecosystem under different assumptions on the ordering of events within the system. To take account of policies, we refine the semantics of PALPS via a transition relation which prunes away executions that do not respect the defined policy. Furthermore, we propose a translation of PALPS into the probabilistic model checker PRISM . We illustrate our framework by applying PRISM on PALPS models with policies for conducting simulation and reachability analysis.
Finite Length Analysis of Irregular Repetition Slotted ALOHA in the Waterfall Region
Venue: arXiv cs.IT 2018
Year: 2018

A finite length analysis is introduced for irregular repetition slotted ALOHA (IRSA) that enables to accurately estimate its performance in the moderate-to-high packet loss probability regime, i.e., in the so-called waterfall region. The analysis is tailored to the collision channel model, which enables mapping the description of the successive interference cancellation process onto the iterative erasure decoding of low-density parity-check codes. The analysis provides accurate estimates of the packet loss probability of IRSA in the waterfall region as demonstrated by Monte Carlo simulations.
Optimal Transmit Antenna Selection for Massive MIMO Wiretap Channels
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we study the impacts of transmit antenna selection on the secrecy performance of massive MIMO systems. We consider a wiretap setting in which a fixed number of transmit antennas are selected and then confidential messages are transmitted over them to a multi-antenna legitimate receiver while being overheard by a multi-antenna eavesdropper. For this setup, we derive an accurate approximation of the instantaneous secrecy rate. Using this approximation, it is shown that in some wiretap settings under antenna selection the growth in the number of active antennas enhances the secrecy performance of the system up to some optimal number and degrades it when this optimal number is surpassed. This observation demonstrates that antenna selection in some massive MIMO settings not only reduces the RF-complexity, but also enhances the secrecy performance. We then consider various scenarios and derive the optimal number of active antennas analytically using our large-system approximation. Numerical investigations show an accurate match between simulations and the analytic results.
Robust Abstractions for Control Synthesis: Robustness Equals Realizability for Linear-Time Properties
Venue: arXiv cs.SY 2018
Year: 2018

We define robust abstractions for synthesizing provably correct and robust controllers for (possibly infinite) uncertain transition systems. It is shown that robust abstractions are sound in the sense that they preserve robust satisfaction of linear-time properties. We then focus on discrete-time control systems modelled by nonlinear difference equations with inputs and define concrete robust abstractions for them. While most abstraction techniques in the literature for nonlinear systems focus on constructing sound abstractions, we present computational procedures for constructing both sound and approximately complete robust abstractions for general nonlinear control systems without stability assumptions. Such procedures are approximately complete in the sense that, given a concrete discrete-time control system and an arbitrarily small perturbation of this system, there exists a finite transition system that robustly abstracts the concrete system and is abstracted by the slightly perturbed system simultaneously. A direct consequence of this result is that robust control synthesis for discrete-time nonlinear systems and linear-time specifications is robustly decidable. More specifically, if there exists a robust control strategy that realizes a given linear-time specification, we can algorithmically construct a (potentially less) robust control strategy that realizes the same specification. The theoretical results are illustrated with a simple motion planning example.