OpenRaiser/Intern-Atlas huggingface dataset:
The Periodic Joint Replenishment Problem is Strongly NP-Hard
Venue: arXiv cs.CC 2015
Year: 2015

In this paper we study the long-standing open question regarding the computational complexity of one of the core problems in supply chains management, the periodic joint replenishment problem. This problem has received a lot of attention over the years and many heuristic and approximation algorithms were suggested. However, in spite of the vast effort, the complexity of the problem remained unresolved. In this paper, we provide a proof that the problem is indeed strongly NP-hard.
Graph Isomorphism for Bounded Genus Graphs In Linear Time
Venue: arXiv cs.DS 2015
Year: 2015

For every integer $g$, isomorphism of graphs of Euler genus at most $g$ can be decided in linear time. This improves previously known algorithms whose time complexity is $n^{O(g)}$ (shown in early 1980's), and in fact, this is the first fixed-parameter tractable algorithm for the graph isomorphism problem for bounded genus graphs in terms of the Euler genus $g$. Our result also generalizes the seminal result of Hopcroft and Wong in 1974, which says that the graph isomorphism problem can be decided in linear time for planar graphs. Our proof is quite lengthly and complicated, but if we are satisfied with an $O(n^3)$ time algorithm for the same problem, the proof is shorter and easier.
Distributed Security Constrained Economic Dispatch
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we investigate two decomposition methods for their convergence rate which are used to solve security constrained economic dispatch (SCED): 1) Lagrangian Relaxation (LR), and 2) Augmented Lagrangian Relaxation (ALR). First, the centralized SCED problem is posed for a 6-bus test network and then it is decomposed into subproblems using both of the methods. In order to model the tie-line between decomposed areas of the test network, a novel method is proposed. The advantages and drawbacks of each method are discussed in terms of accuracy and information privacy. We show that there is a tradeoff between the information privacy and the convergence rate. It has been found that ALR converges faster compared to LR, due to the large amount of shared data.
How far can we go without convolution: Improving fully-connected networks
Venue: arXiv cs.LG 2015
Year: 2015

We propose ways to improve the performance of fully connected networks. We found that two approaches in particular have a strong effect on performance: linear bottleneck layers and unsupervised pre-training using autoencoders without hidden unit biases. We show how both approaches can be related to improving gradient flow and reducing sparsity in the network. We show that a fully connected network can yield approximately 70% classification accuracy on the permutation-invariant CIFAR-10 task, which is much higher than the current state-of-the-art. By adding deformations to the training data, the fully connected network achieves 78% accuracy, which is just 10% short of a decent convolutional network.
Normalisation by Traversals
Venue: arXiv cs.PL 2015
Year: 2015

We present a novel method of computing the beta-normal eta-long form of a simply-typed lambda-term by constructing traversals over a variant abstract syntax tree of the term. In contrast to beta-reduction, which changes the term by substitution, this method of normalisation by traversals leaves the original term intact. We prove the correctness of the normalisation procedure by game semantics. As an application, we establish a path-traversal correspondence theorem which is the basis of a key decidability result in higher-order model checking.
Comments on Bridging Service-Oriented Architecture and IEC 61499 for Flexibility and Interoperability
Venue: arXiv cs.SE 2015
Year: 2015

In the paper by W. Dai et al. (IEEE Trans. On Industrial Informatics, vol. 11, no. 3, pp. 771-781, June 2015), a formal mapping between IEC 61499 and SOA is presented and a SOA-based execution environment architecture is described. In this letter, the proposed in the above paper mapping and the execution environment architecture are discussed and their potential for the exploitation is disputed.
The Impact of Beamwidth on Temporal Channel Variation in Vehicular Channels and its Implications
Venue: arXiv cs.IT 2015
Year: 2015

Millimeter wave (mmWave) has great potential in realizing high data rate thanks to the large spectral channels. It is considered as a key technology for the fifth generation wireless networks and is already used in wireless LAN (e.g., IEEE 802.11ad). Using mmWave for vehicular communications, however, is often viewed with some skepticism due to a misconception that the Doppler spread would become too large at these high frequencies. This is not true when directional beam is employed for communications. In this paper, closed form expressions relating the channel coherence time and beamwidth are derived. Unlike prior work that assumed perfect beam pointing, the pointing error due to the receiver motion is incorporated to show that there exists a non-zero optimal beamwidth that maximizes the coherence time. To investigate the mobility effect on the beam alignment which is an important feature in mmWave systems, a novel concept of beam coherence time is defined. The beam coherence time, which is an effective measure of beam alignment frequency, is shown to be much larger than the conventional channel coherence time and thus results in reduced beam alignment overhead. Using the derived correlation function, the channel coherence time, and the beam coherence time, an overall performance metric considering both the channel time-variation and the beam alignment overhead is derived. Using this metric, it is shown that beam alignment in every beam coherence time performs better than the beam alignment in every channel coherence time due to the large overhead for the latter case.
ELDA: Towards Efficient and Lightweight Detection of Cache Pollution Attacks in NDN
Venue: arXiv cs.CR 2015
Year: 2015

As a promising architectural design for future Internet, named data networking (NDN) relies on in-network caching to efficiently deliver name-based content. However, the in-network caching is vulnerable to cache pollution attacks (CPA), which can reduce cache hits by violating cache locality and significantly degrade the overall performance of NDN. To defend against CPA attacks, the most effective way is to first detect the attacks and then throttle them. Since the CPA attack itself has already imposed a huge burden on victims, to avoid exhausting the remaining resources on the victims for detection purpose, we expect a lightweight detection solution. We thus propose ELDA, an Efficient and Lightweight Detection scheme against cache pollution Attacks, in which we design a Lightweight Flajolet-Martin (LFM) sketch to monitor the interest traffic. Our analysis and simulations demonstrate that, by consuming a few computation and memory resources, ELDA can effectively and efficiently detect CPA attacks.
Semantic processing of EHR data for clinical research
Venue: arXiv cs.DB 2015
Year: 2015

There is a growing need to semantically process and integrate clinical data from different sources for clinical research. This paper presents an approach to integrate EHRs from heterogeneous resources and generate integrated data in different data formats or semantics to support various clinical research applications. The proposed approach builds semantic data virtualization layers on top of data sources, which generate data in the requested semantics or formats on demand. This approach avoids upfront dumping to and synchronizing of the data with various representations. Data from different EHR systems are first mapped to RDF data with source semantics, and then converted to representations with harmonized domain semantics where domain ontologies and terminologies are used to improve reusability. It is also possible to further convert data to application semantics and store the converted results in clinical research databases, e.g. i2b2, OMOP, to support different clinical research settings. Semantic conversions between different representations are explicitly expressed using N3 rules and executed by an N3 Reasoner (EYE), which can also generate proofs of the conversion processes. The solution presented in this paper has been applied to real-world applications that process large scale EHR data.
USFD: Twitter NER with Drift Compensation and Linked Data
Venue: arXiv cs.CL 2015
Year: 2015

This paper describes a pilot NER system for Twitter, comprising the USFD system entry to the W-NUT 2015 NER shared task. The goal is to correctly label entities in a tweet dataset, using an inventory of ten types. We employ structured learning, drawing on gazetteers taken from Linked Data, and on unsupervised clustering features, and attempting to compensate for stylistic and topic drift - a key challenge in social media text. Our result is competitive; we provide an analysis of the components of our methodology, and an examination of the target dataset in the context of this task.
A tight relation between series-parallel graphs and Bipartite Distance Hereditary graphs
Venue: arXiv cs.DM 2015
Year: 2015

Bandelt and Mulder's structural characterization of Bipartite Distance Hereditary graphs asserts that such graphs can be built inductively starting from a single vertex and by repeatedly adding either pending vertices or twins (i.e., vertices with the same neighborhood as an existing one). Dirac and Duffin's structural characterization of 2-connected series-parallel graphs asserts that such graphs can be built inductively starting from a single edge by adding either edges in series or in parallel. In this paper we prove that the two constructions are the same construction when bipartite graphs are viewed as the fundamental graphs of a graphic matroid. We then apply the result to re-prove known results concerning bipartite distance hereditary graphs and series-parallel graphs, to characterize self-dual outer-planar graphs and, finally, to provide a new class of polynomially-solvable instances for the integer multi commodity flow of maximum value.
A Handheld Device for the In Situ Acquisition of Multimodal Tactile Sensing Data
Venue: arXiv cs.RO 2015
Year: 2015

Multimodal tactile sensing could potentially enable robots to improve their performance at manipulation tasks by rapidly discriminating between task-relevant objects. Data-driven approaches to this tactile perception problem show promise, but there is a dearth of suitable training data. In this two-page paper, we present a portable handheld device for the efficient acquisition of multimodal tactile sensing data from objects in their natural settings, such as homes. The multimodal tactile sensor on the device integrates a fabric-based force sensor, a contact microphone, an accelerometer, temperature sensors, and a heating element. We briefly introduce our approach, describe the device, and demonstrate feasibility through an evaluation with a small data set that we captured by making contact with 7 task-relevant objects in a bathroom of a person's home.
From Images to Sentences through Scene Description Graphs using Commonsense Reasoning and Knowledge
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we propose the construction of linguistic descriptions of images. This is achieved through the extraction of scene description graphs (SDGs) from visual scenes using an automatically constructed knowledge base. SDGs are constructed using both vision and reasoning. Specifically, commonsense reasoning is applied on (a) detections obtained from existing perception methods on given images, (b) a "commonsense" knowledge base constructed using natural language processing of image annotations and (c) lexical ontological knowledge from resources such as WordNet. Amazon Mechanical Turk(AMT)-based evaluations on Flickr8k, Flickr30k and MS-COCO datasets show that in most cases, sentences auto-constructed from SDGs obtained by our method give a more relevant and thorough description of an image than a recent state-of-the-art image caption based approach. Our Image-Sentence Alignment Evaluation results are also comparable to that of the recent state-of-the art approaches.
A Stochastic Geometry Analysis of Large-scale Cooperative Wireless Networks Powered by Energy Harvesting
Venue: arXiv cs.IT 2015
Year: 2015

Energy harvesting is a technology for enabling green, sustainable, and autonomous wireless networks. In this paper, a large-scale wireless network with energy harvesting transmitters is considered, where a group of transmitters forms a cluster to cooperatively serve a desired receiver amid interference and noise. To characterize the link-level performance, closed-form expressions are derived for the transmission success probability at a receiver in terms of key parameters such as node densities, energy harvesting parameters, channel parameters, and cluster size, for a given cluster geometry. The analysis is further extended to characterize a network-level performance metric, capturing the tradeoff between link quality and the fraction of receivers served. Numerical simulations validate the accuracy of the analytical model. Several useful insights are provided. For example, while more cooperation helps improve the link-level performance, the network-level performance might degrade with the cluster size. Numerical results show that a small cluster size (typically 3 or smaller) optimizes the network-level performance. Furthermore, substantial performance can be extracted with a relatively small energy buffer. Moreover, the utility of having a large energy buffer increases with the energy harvesting rate as well as with the cluster size in sufficiently dense networks.
Information Rate Decomposition for Feedback Systems with Output Disturbance
Venue: arXiv cs.IT 2015
Year: 2015

This technical note considers the problem of resource allocation in linear feedback control system with output disturbance. By decomposing the information rate in the feedback communication channel, the channel resource allocation is thoroughly analyzed. The results show that certain amount of resource is used to transmit the output disturbance and this resource allocation is independent from feedback controller design.
Adaptive Policies for Scheduling with Reconfiguration Delay: An End-to-End Solution for All-Optical Data Centers
Venue: arXiv cs.NI 2015
Year: 2015

All-optical switching networks have been considered a promising candidate for the next generation data center networks thanks to its scalability in data bandwidth and power efficiency. However, the bufferless nature and the nonzero recon- figuration delay of optical switches remain great challenges in deploying all-optical networks. This paper considers the end-to- end scheduling for all-optical data center networks with no in- network buffer and nonzero reconfiguration delay. A framework is proposed to deal with the nonzero reconfiguration delay. The proposed approach constructs an adaptive variant of any given scheduling policy. It is shown that if a scheduling policy guarantees its schedules to have schedule weights close to the MaxWeight schedule (and thus is throughput optimal in the zero reconfiguration regime), then the throughput optimality is inherited by its adaptive variant (in any nonzero reconfiguration delay regime). As a corollary, a class of adaptive variants of the well known MaxWeight policy is shown to achieve throughput optimality without prior knowledge of the traffic load. Further- more, through numerical simulations, the simplest such policy, namely the Adaptive MaxWeight (AMW), is shown to exhibit better delay performance than all prior work.
IBMMS Decision Support Tool For Management of Bank Telemarketing Campaigns
Venue: arXiv cs.AI 2015
Year: 2015

Although direct marketing is a good method for banks to utilize in the face of global competition and the financial crisis, it has been shown to exhibit poor performance. However, there are some drawbacks to direct campaigns, such as those related to improving the negative attributes that customers ascribe to banks. To overcome these problems, attractive long-term deposit campaigns should be organized and managed more effectively. The aim of this study is to develop an Intelligent Bank Market Management System (IBMMS) for bank managers who want to manage efficient marketing campaigns. IBMMS is the first system developed by combining the power of data mining with the capabilities of expert systems in this area. Moreover, IBMMS includes important features that enable it to be intelligent: a knowledge base, an inference engine and an advisor. Using this system, a manager can successfully direct marketing campaigns and follow the decision schemas of customers both as individuals and as a group; moreover, a manager can make decisions that lead to the desired response by customers.
Analysis of Intel's Haswell Microarchitecture Using The ECM Model and Microbenchmarks
Venue: arXiv cs.DC 2015
Year: 2015

This paper presents an in-depth analysis of Intel's Haswell microarchitecture for streaming loop kernels. Among the new features examined is the dual-ring Uncore design, Cluster-on-Die mode, Uncore Frequency Scaling, core improvements as new and improved execution units, as well as improvements throughout the memory hierarchy. The Execution-Cache-Memory diagnostic performance model is used together with a generic set of microbenchmarks to quantify the efficiency of the microarchitecture. The set of microbenchmarks is chosen such that it can serve as a blueprint for other streaming loop kernels.
Cloud Offloading for Multi-Radio Enabled Mobile Devices
Venue: arXiv cs.NI 2015
Year: 2015

The advent of 5G networking technologies has increased the expectations from mobile devices, in that, more sophisticated, computationally intense applications are expected to be delivered on the mobile device which are themselves getting smaller and sleeker. This predicates a need for offloading computationally intense parts of the applications to a resource strong cloud. Parallely, in the wireless networking world, the trend has shifted to multi-radio (as opposed to multi-channel) enabled communications. In this paper, we provide a comprehensive computation offloading solution that uses the multiple radio links available for associated data transfer, optimally. Our contributions include: a comprehensive model for the energy consumption from the perspective of the mobile device; the formulation of the joint optimization problem to minimize the energy consumed as well as allocating the associated data transfer optimally through the available radio links and an iterative algorithm that converges to a locally optimal solution. Simulations on an HTC phone, running a 14-component application and using the Amazon EC2 as the cloud, show that the solution obtained through the iterative algorithm consumes only 3% more energy than the optimal solution (obtained via exhaustive search).
When Naïve Bayes Nearest Neighbours Meet Convolutional Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

Since Convolutional Neural Networks (CNNs) have become the leading learning paradigm in visual recognition, Naive Bayes Nearest Neighbour (NBNN)-based classifiers have lost momentum in the community. This is because (1) such algorithms cannot use CNN activations as input features; (2) they cannot be used as final layer of CNN architectures for end-to-end training , and (3) they are generally not scalable and hence cannot handle big data. This paper proposes a framework that addresses all these issues, thus bringing back NBNNs on the map. We solve the first by extracting CNN activations from local patches at multiple scale levels, similarly to [1]. We address simultaneously the second and third by proposing a scalable version of Naive Bayes Non-linear Learning (NBNL, [2]). Results obtained using pre-trained CNNs on standard scene and domain adaptation databases show the strength of our approach, opening a new season for NBNNs.
The scalability of the matrices in direct Trefftz method in 2D Laplace problem
Venue: arXiv cs.NA 2015
Year: 2015

This paper presents an interesting property of the matrices that may be obtained with the use of direct Trefftz method. It is proved analytically for 2D Laplace problem that values of the elements of matrices describing the capacitance of two scaled domains are inversely proportional to the scalability factor. As an example of the application the capacitance extraction problem is chosen. Concise description of the algorithm in which the scalability property can be utilized is given. Furthermore some numerical results of the algorithm are presented.
Human Curation and Convnets: Powering Item-to-Item Recommendations on Pinterest
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents Pinterest Related Pins, an item-to-item recommendation system that combines collaborative filtering with content-based ranking. We demonstrate that signals derived from user curation, the activity of users organizing content, are highly effective when used in conjunction with content-based ranking. This paper also demonstrates the effectiveness of visual features, such as image or object representations learned from convnets, in improving the user engagement rate of our item-to-item recommendation system.
Time and Location Aware Mobile Data Pricing
Venue: arXiv cs.NI 2015
Year: 2015

Mobile users' correlated mobility and data consumption patterns often lead to severe cellular network congestion in peak hours and hot spots. This paper presents an optimal design of time and location aware mobile data pricing, which incentivizes users to smooth traffic and reduce network congestion. We derive the optimal pricing scheme through analyzing a two-stage decision process, where the operator determines the time and location aware prices by minimizing his total cost in Stage I, and each mobile user schedules his mobile traffic by maximizing his payoff (i.e., utility minus payment) in Stage II. We formulate the two-stage decision problem as a bilevel optimization problem, and propose a derivative-free algorithm to solve the problem for any increasing concave user utility functions. We further develop low complexity algorithms for the commonly used logarithmic and linear utility functions. The optimal pricing scheme ensures a win-win situation for the operator and users. Simulations show that the operator can reduce the cost by up to 97.52% in the logarithmic utility case and 98.70% in the linear utility case, and users can increase their payoff by up to 79.69% and 106.10% for the two types of utilities, respectively, comparing with a time and location independent pricing benchmark. Our study suggests that the operator should provide price discounts at less crowded time slots and locations, and the discounts need to be significant when the operator's cost of provisioning excessive traffic is high or users' willingness to delay traffic is low.
An Optimal Algorithm for the Separating Common Tangents of two Polygons
Venue: arXiv cs.CG 2015
Year: 2015

We describe an algorithm for computing the separating common tangents of two simple polygons using linear time and only constant workspace. A tangent of a polygon is a line touching the polygon such that all of the polygon lies to the same side of the line. A separating common tangent of two polygons is a tangent of both polygons where the polygons are lying on different sides of the tangent. Each polygon is given as a read-only array of its corners. If a separating common tangent does not exist, the algorithm reports that. Otherwise, two corners defining a separating common tangent are returned. The algorithm is simple and implies an optimal algorithm for deciding if the convex hulls of two polygons are disjoint or not. This was not known to be possible in linear time and constant workspace prior to this paper. An outer common tangent is a tangent of both polygons where the polygons are on the same side of the tangent. In the case where the convex hulls of the polygons are disjoint, we give an algorithm for computing the outer common tangents in linear time using constant workspace.