OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Approximations for the Online Dispersion Problem
Venue: arXiv cs.CG 2017
Year: 2017

The dispersion problem has been widely studied in computational geometry and facility location, and is closely related to the packing problem. The goal is to locate n points (e.g., facilities or persons) in a k-dimensional polytope, so that they are far away from each other and from the boundary of the polytope. In many real-world scenarios however, the points arrive and depart at different times, and decisions must be made without knowing future events. Therefore we study, for the first time in the literature, the online dispersion problem in Euclidean space. There are two natural objectives when time is involved: the all-time worst-case (ATWC) problem tries to maximize the minimum distance that ever appears at any time; and the cumulative distance (CD) problem tries to maximize the integral of the minimum distance throughout the whole time interval. Interestingly, the online problems are highly non-trivial even on a segment. For cumulative distance, this remains the case even when the problem is time-dependent but offline, with all the arriving and departure times given in advance. For the online ATWC problem on a segment, we construct a deterministic polynomial-time algorithm which is (2ln2+epsilon)-competitive, where epsilon>0 can be arbitrarily small and the algorithm's running time is polynomial in 1/epsilon. We show this algorithm is actually optimal. For the same problem in a square, we provide a 1.591-competitive algorithm and a 1.183 lower-bound. Furthermore, for arbitrary k-dimensional polytopes with k>=2, we provide a 2/(1-epsilon)-competitive algorithm and a 7/6 lower-bound. Interestingly, for the offline CD problem in arbitrary k-dimensional polytopes, we provide a polynomial-time black-box reduction to the online ATWC problem, and the resulting competitive ratio increases by a factor of at most 2.
A Decomposition Algorithm to Solve the Multi-Hop Peer-to-Peer Ride-Matching Problem
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we mathematically model the multi-hop Peer-to-Peer (P2P) ride-matching problem as a binary program. We formulate this problem as a many-to-many problem in which a rider can travel by transferring between multiple drivers, and a driver can carry multiple riders. We propose a pre-processing procedure to reduce the size of the problem, and devise a decomposition algorithm to solve the original ride-matching problem to optimality by means of solving multiple smaller problems. We conduct extensive numerical experiments to demonstrate the computational efficiency of the proposed algorithm and show its practical applicability to reasonably-sized dynamic ride-matching contexts. Finally, in the interest of even lower solution times, we propose heuristic solution methods, and investigate the trade-offs between solution time and accuracy.
Exploring Symmetry in Wireless Propagation Channels
Venue: arXiv cs.IT 2017
Year: 2017

Wireless communications literature is very rich with empirical studies and measurement campaigns that study the nature of the wireless propagation channel. However, despite their undoubted usefulness, many of these studies have omitted a fundamental yet key feature of the physical signal propagation, that is, wireless propagation asymmetry. This feature does not agree with the electromagnetic reciprocity theorem, and the many research papers that adopt wireless channel symmetry, and hence rendering their modeling, unexpectedly, inaccurate. Besides, asymmetry is unquestionably an important characteristic of wireless channels, which needs to be accurately characterized for vehicular/mobile communications, 5G networks, and associated applications such as indoor/outdoor localization. This paper presents a modest and a preliminary study that reports potential causes of propagation asymmetry. Measurements conducted on Khalifa University campus in UAE show that wireless channels are symmetric in the absence of symmetry impairments. Therefore, care should be taken when considering some practical wireless propagation scenarios. Key conclusions and recommendation are summarized. We believe that this study will be inspiring for the academic community and will trigger further investigations within wireless propagation assumptions.
Population Seeding Techniques for Rolling Horizon Evolution in General Video Game Playing
Venue: arXiv cs.AI 2017
Year: 2017

While Monte Carlo Tree Search and closely related methods have dominated General Video Game Playing, recent research has demonstrated the promise of Rolling Horizon Evolutionary Algorithms as an interesting alternative. However, there is little attention paid to population initialization techniques in the setting of general real-time video games. Therefore, this paper proposes the use of population seeding to improve the performance of Rolling Horizon Evolution and presents the results of two methods, One Step Look Ahead and Monte Carlo Tree Search, tested on 20 games of the General Video Game AI corpus with multiple evolution parameter values (population size and individual length). An in-depth analysis is carried out between the results of the seeding methods and the vanilla Rolling Horizon Evolution. In addition, the paper presents a comparison to a Monte Carlo Tree Search algorithm. The results are promising, with seeding able to boost performance significantly over baseline evolution and even match the high level of play obtained by the Monte Carlo Tree Search.
Stable Desynchronization for Wireless Sensor Networks: (III) Stability Analysis
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we use dynamical systems to analyze stability of desynchronization algorithms at equilibrium. We start by illustrating the equilibrium of a dynamic systems and formalizing force components and time phases. Then, we use Linear Approximation to obtain Jaconian (J) matrixes which are used to find the eigenvalues. Next, we employ the Hirst and Macey theorem and Gershgorins theorem to find the bounds of those eigenvalues. Finally, if the number of nodes (n) is within such bounds, the systems are stable at equilibrium. (This paper is the last part of the series Stable Desynchronization for Wireless Sensor Networks - (I) Concepts and Algorithms (II) Performance Evaluation (III) Stability Analysis)
Non-Convex Weighted Lp Nuclear Norm based ADMM Framework for Image Restoration
Venue: arXiv cs.CV 2017
Year: 2017

Since the matrix formed by nonlocal similar patches in a natural image is of low rank, the nuclear norm minimization (NNM) has been widely used in various image processing studies. Nonetheless, nuclear norm based convex surrogate of the rank function usually over-shrinks the rank components and makes different components equally, and thus may produce a result far from the optimum. To alleviate the above-mentioned limitations of the nuclear norm, in this paper we propose a new method for image restoration via the non-convex weighted Lp nuclear norm minimization (NCW-NNM), which is able to more accurately enforce the image structural sparsity and self-similarity simultaneously. To make the proposed model tractable and robust, the alternative direction multiplier method (ADMM) is adopted to solve the associated non-convex minimization problem. Experimental results on various types of image restoration problems, including image deblurring, image inpainting and image compressive sensing (CS) recovery, demonstrate that the proposed method outperforms many current state-of-the-art methods in both the objective and the perceptual qualities.
Rerouting flows when links fail
Venue: arXiv cs.DM 2017
Year: 2017

We introduce and investigate reroutable flows, a robust version of network flows in which link failures can be mitigated by rerouting the affected flow. Given a capacitated network, a path flow is reroutable if after failure of an arbitrary arc, we can reroute the interrupted flow from the tail of that arc to the sink, without modifying the flow that is not affected by the failure. Similar types of restoration, which are often termed "local", were previously investigated in the context of network design, such as min-cost capacity planning. In this paper, our interest is in computing maximum flows under this robustness assumption. An important new feature of our model, distinguishing it from existing max robust flow models, is that no flow can get lost in the network. We also study a tightening of reroutable flows, called strictly reroutable flows, making more restrictive assumptions on the capacities available for rerouting. For both variants, we devise a reroutable-flow equivalent of an s-t-cut and show that the corresponding max flow/min cut gap is bounded by 2. It turns out that a strictly reroutable flow of maximum value can be found using a compact LP formulation, whereas the problem of finding a maximum reroutable flow is NP-hard, even when all capacities are in {1, 2}. However, the tightening can be used to get a 2-approximation for reroutable flows. This ratio is tight in general networks, but we show that in the case of unit capacities, every reroutable flow can be transformed into a strictly reroutable flow of same value. While it is NP-hard to compute a maximal integral flow even for unit capacities, we devise a surprisingly simple combinatorial algorithm that finds a half-integral strictly reroutable flow of value 1, or certifies that no such solutions exits. Finally, we also give a hardness result for the case of multiple arc failures.
Compositional abstraction and safety synthesis using overlapping symbolic models
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we develop a compositional approach to abstraction and safety synthesis for a general class of discrete time nonlinear systems. Our approach makes it possible to define a symbolic abstraction by composing a set of symbolic subsystems that are overlapping in the sense that they can share some common state variables. We develop compositional safety synthesis techniques using such overlapping symbolic subsystems. Comparisons, in terms of conservativeness and of computational complexity, between abstractions and controllers obtained from different system decompositions are provided. Numerical experiments show that the proposed approach for symbolic control synthesis enables a significant complexity reduction with respect to the centralized approach, while reducing the conservatism with respect to compositional approaches using non-overlapping subsystems.
Dense 3D Facial Reconstruction from a Single Depth Image in Unconstrained Environment
Venue: arXiv cs.CV 2017
Year: 2017

With the increasing demands of applications in virtual reality such as 3D films, virtual Human-Machine Interactions and virtual agents, the analysis of 3D human face analysis is considered to be more and more important as a fundamental step for those virtual reality tasks. Due to information provided by an additional dimension, 3D facial reconstruction enables aforementioned tasks to be achieved with higher accuracy than those based on 2D facial analysis. The denser the 3D facial model is, the more information it could provide. However, most existing dense 3D facial reconstruction methods require complicated processing and high system cost. To this end, this paper presents a novel method that simplifies the process of dense 3D facial reconstruction by employing only one frame of depth data obtained with an off-the-shelf RGB-D sensor. The experiments showed competitive results with real world data.
Exploiting Feature Confidence for Forward Motion Estimation
Venue: arXiv cs.RO 2017
Year: 2017

Visual-Inertial Odometry (VIO) utilizes an Inertial Measurement Unit (IMU) to overcome the limitations of Visual Odometry (VO). However, the VIO for vehicles in large-scale outdoor environments still has some difficulties in estimating forward motion with distant features. To solve these difficulties, we propose a robust VIO method based on the analysis of feature confidence in forward motion estimation using an IMU. We first formulate the VIO problem by using effective trifocal tensor geometry. Then, we infer the feature confidence by using the motion information obtained from an IMU and incorporate the confidence into the Bayesian estimation framework. Experimental results on the public KITTI dataset show that the proposed VIO outperforms the baseline VIO, and it also demonstrates the effectiveness of the proposed feature confidence analysis and confidence-incorporated egomotion estimation framework.
Can MPTCP Secure Internet Communications from Man-in-the-Middle Attacks?
Venue: arXiv cs.NI 2017
Year: 2017

-Multipath communications at the Internet scale have been a myth for a long time, with no actual protocol being deployed so that multiple paths could be taken by a same connection on the way towards an Internet destination. Recently, the Multipath Transport Control Protocol (MPTCP) extension was standardized and is undergoing a quick adoption in many use-cases, from mobile to fixed access networks, from data-centers to core networks. Among its major benefits -- i.e., reliability thanks to backup path rerouting; throughput increase thanks to link aggregation; and confidentiality thanks to harder capacity to intercept a full connection -- the latter has attracted lower attention. How interesting would it be using MPTCP to exploit multiple Internet-scale paths hence decreasing the probability of man-in-the-middle (MITM) attacks is a question to which we try to answer. By analyzing the Autonomous System (AS) level graph, we identify which countries and regions show a higher level of robustness against MITM AS-level attacks, for example due to core cable tapping or route hijacking practices.
Z2Z4Z8-Cyclic Codes
Venue: arXiv cs.IT 2017
Year: 2017

In this paper we study Z2Z4Z8-additive codes, which are the extension of recently introduced Z2Z4-additive codes. We determine the standard forms of the generator and parity-check matrices of Z2Z4Z8-additive codes. Moreover, we investigate Z2Z4Z8-cyclic codes giving their generator polynomials and spanning sets. We also give some illustrative examples of both Z2Z4Z8-additive codes and Z2Z4Z8-cyclic codes.
Reductions for Transition Systems at Work: Deriving a Logical Characterization of Quantitative Bisimulation
Venue: arXiv cs.LO 2017
Year: 2017

Weighted labelled transition systems (WLTSs) are an established meta-model aiming to provide general results and tools for a wide range of systems such as non-deterministic, stochastic, and probabilistic systems. In order to encompass processes combining several quantitative aspects, extensions of the WLTS framework have been further proposed, state-to-function transition systems (FuTSs) and uniform labelled transition systems (ULTraSs) being two prominent examples. In this paper we show that this hierarchy of meta-models collapses when studied under the lens of bisimulation-coherent encodings. Taking advantage of these reductions, we derive a fully abstract Hennessy-Milner-style logic for FuTSs, i.e., which characterizes quantitative bisimilarity, from a fully-abstract logic for WLTSs.
Stochastic Constraint Programming as Reinforcement Learning
Venue: arXiv cs.AI 2017
Year: 2017

Stochastic Constraint Programming (SCP) is an extension of Constraint Programming (CP) used for modelling and solving problems involving constraints and uncertainty. SCP inherits excellent modelling abilities and filtering algorithms from CP, but so far it has not been applied to large problems. Reinforcement Learning (RL) extends Dynamic Programming to large stochastic problems, but is problem-specific and has no generic solvers. We propose a hybrid combining the scalability of RL with the modelling and constraint filtering methods of CP. We implement a prototype in a CP system and demonstrate its usefulness on SCP problems.
Downlink Small-cell Base Station Cooperation Strategy in Fractal Small-cell Networks
Venue: arXiv cs.NI 2017
Year: 2017

Coordinated multipoint (CoMP) communications are considered for the fifth-generation (5G) small-cell networks as a tool to improve the high data rates and the cell-edge throughput. The average achievable rates of the small-cell base stations (SBS) cooperation strategies with distance and received signal power constraints are respectively derived for the fractal small-cell networks based on the anisotropic path loss model. Simulation results are presented to show that the average achievable rate with the received signal power constraint is larger than the rate with a distance constraint considering the same number of cooperative SBSs. The average achievable rate with distance constraint decreases with the increase of the intensity of SBSs when the anisotropic path loss model is considered. What's more, the network energy efficiency of fractal smallcell networks adopting the SBS cooperation strategy with the received signal power constraint is analyzed. The network energy efficiency decreases with the increase of the intensity of SBSs which indicates a challenge on the deployment design for fractal small-cell networks.
Entropic Trace Estimates for Log Determinants
Venue: arXiv cs.NA 2017
Year: 2017

The scalable calculation of matrix determinants has been a bottleneck to the widespread application of many machine learning methods such as determinantal point processes, Gaussian processes, generalised Markov random fields, graph models and many others. In this work, we estimate log determinants under the framework of maximum entropy, given information in the form of moment constraints from stochastic trace estimation. The estimates demonstrate a significant improvement on state-of-the-art alternative methods, as shown on a wide variety of UFL sparse matrices. By taking the example of a general Markov random field, we also demonstrate how this approach can significantly accelerate inference in large-scale learning methods involving the log determinant.
Using Speech Technology for Quantifying Behavioral Characteristics in Peer-Led Team Learning Sessions
Venue: arXiv cs.SD 2017
Year: 2017

Peer-Led Team Learning (PLTL) is a learning methodology where a peer-leader co-ordinate a small-group of students to collaboratively solve technical problems. PLTL have been adopted for various science, engineering, technology and maths courses in several US universities. This paper proposed and evaluated a speech system for behavioral analysis of PLTL groups. It could help in identifying the best practices for PLTL. The CRSS-PLTL corpus was used for evaluation of developed algorithms. In this paper, we developed a robust speech activity detection (SAD) by fusing the outputs of a DNN-based pitch extractor and an unsupervised SAD based on voicing measures. Robust speaker diarization system consisted of bottleneck features (from stacked autoencoder) and informed HMM-based joint segmentation and clustering system. Behavioral characteristics such as participation, dominance, emphasis, curiosity and engagement were extracted by acoustic analyses of speech segments belonging to all students. We proposed a novel method for detecting question inflection and performed equal error rate analysis on PLTL corpus. In addition, a robust approach for detecting emphasized speech regions was also proposed. Further, we performed exploratory data analysis for understanding the distortion present in CRSS-PLTL corpus as it was collected in naturalistic scenario. The ground-truth Likert scale ratings were used for capturing the team dynamics in terms of student's responses to a variety of evaluation questions. Results suggested the applicability of proposed system for behavioral analysis of small-group conversations such as PLTL, work-place meetings etc.. Keywords- Behavioral Speech Processing, Bottleneck Features, Curiosity, Deep Neural Network, Dominance, Auto-encoder, Emphasis, Engagement, Peer-Led Team Learning, Speaker Diarization, Small-group Conversations
Elite Bases Regression: A Real-time Algorithm for Symbolic Regression
Venue: arXiv cs.DS 2017
Year: 2017

Symbolic regression is an important but challenging research topic in data mining. It can detect the underlying mathematical models. Genetic programming (GP) is one of the most popular methods for symbolic regression. However, its convergence speed might be too slow for large scale problems with a large number of variables. This drawback has become a bottleneck in practical applications. In this paper, a new non-evolutionary real-time algorithm for symbolic regression, Elite Bases Regression (EBR), is proposed. EBR generates a set of candidate basis functions coded with parse-matrix in specific mapping rules. Meanwhile, a certain number of elite bases are preserved and updated iteratively according to the correlation coefficients with respect to the target model. The regression model is then spanned by the elite bases. A comparative study between EBR and a recent proposed machine learning method for symbolic regression, Fast Function eXtraction (FFX), are conducted. Numerical results indicate that EBR can solve symbolic regression problems more effectively.
Development of An Autonomous Bridge Deck Inspection Robotic System
Venue: arXiv cs.RO 2017
Year: 2017

The threat to safety of aging bridges has been recognized as a critical concern to the general public due to the poor condition of many bridges in the U.S. Currently, the bridge inspection is conducted manually, and it is not efficient to identify bridge condition deterioration in order to facilitate implementation of appropriate maintenance or rehabilitation procedures. In this paper, we report a new development of the autonomous mobile robotic system for bridge deck inspection and evaluation. The robot is integrated with several nondestructive evaluation (NDE) sensors and a navigation control algorithm to allow it to accurately and autonomously maneuver on the bridge deck to collect visual images and conduct NDE measurements. The developed robotic system can reduce the cost and time of the bridge deck data collection and inspection. For efficient bridge deck monitoring, the crack detection algorithm to build the deck crack map is presented in detail. The impact-echo (IE), ultrasonic surface waves (USW) and electrical resistivity (ER) data collected by the robot are analyzed to generate the delamination, concrete elastic modulus, corrosion maps of the bridge deck, respectively. The presented robotic system has been successfully deployed to inspect numerous bridges in more than ten different states in the U.S.
Towards Instance Segmentation with Object Priority: Prominent Object Detection and Recognition
Venue: arXiv cs.CV 2017
Year: 2017

This manuscript introduces the problem of prominent object detection and recognition inspired by the fact that human seems to priorities perception of scene elements. The problem deals with finding the most important region of interest, segmenting the relevant item/object in that area, and assigning it an object class label. In other words, we are solving the three problems of saliency modeling, saliency detection, and object recognition under one umbrella. The motivation behind such a problem formulation is (1) the benefits to the knowledge representation-based vision pipelines, and (2) the potential improvements in emulating bio-inspired vision systems by solving these three problems together. We are foreseeing extending this problem formulation to fully semantically segmented scenes with instance object priority for high-level inferences in various applications including assistive vision. Along with a new problem definition, we also propose a method to achieve such a task. The proposed model predicts the most important area in the image, segments the associated objects, and labels them. The proposed problem and method are evaluated against human fixations, annotated segmentation masks, and object class categories. We define a chance level for each of the evaluation criterion to compare the proposed algorithm with. Despite the good performance of the proposed baseline, the overall evaluations indicate that the problem of prominent object detection and recognition is a challenging task that is still worth investigating further.