OpenRaiser/Intern-Atlas huggingface dataset:
Residential Demand Response Applications Using Batch Reinforcement Learning
Venue: arXiv cs.SY 2015
Year: 2015

Driven by recent advances in batch Reinforcement Learning (RL), this paper contributes to the application of batch RL to demand response. In contrast to conventional model-based approaches, batch RL techniques do not require a system identification step, which makes them more suitable for a large-scale implementation. This paper extends fitted Q-iteration, a standard batch RL technique, to the situation where a forecast of the exogenous data is provided. In general, batch RL techniques do not rely on expert knowledge on the system dynamics or the solution. However, if some expert knowledge is provided, it can be incorporated by using our novel policy adjustment method. Finally, we tackle the challenge of finding an open-loop schedule required to participate in the day-ahead market. We propose a model-free Monte-Carlo estimator method that uses a metric to construct artificial trajectories and we illustrate this method by finding the day-ahead schedule of a heat-pump thermostat. Our experiments show that batch RL techniques provide a valuable alternative to model-based controllers and that they can be used to construct both closed-loop and open-loop policies.
A New Index Coding Scheme Exploiting Interlinked Cycles
Venue: arXiv cs.IT 2015
Year: 2015

We study the index coding problem in the unicast message setting, i.e., where each message is requested by one unique receiver. This problem can be modeled by a directed graph. We propose a new scheme called interlinked cycle cover, which exploits interlinked cycles in the directed graph, for designing index codes. This new scheme generalizes the existing clique cover and cycle cover schemes. We prove that for a class of infinitely many digraphs with messages of any length, interlinked cycle cover provides an optimal index code. Furthermore, the index code is linear with linear time encoding complexity.
Quantization Design for Distributed Optimization
Venue: arXiv cs.SY 2015
Year: 2015

We consider the problem of solving a distributed optimization problem using a distributed computing platform, where the communication in the network is limited: each node can only communicate with its neighbours and the channel has a limited data-rate. A common technique to address the latter limitation is to apply quantization to the exchanged information. We propose two distributed optimization algorithms with an iteratively refining quantization design based on the inexact proximal gradient method and its accelerated variant. We show that if the parameters of the quantizers, i.e. the number of bits and the initial quantization intervals, satisfy certain conditions, then the quantization error is bounded by a linearly decreasing function and the convergence of the distributed algorithms is guaranteed. Furthermore, we prove that after imposing the quantization scheme, the distributed algorithms still exhibit a linear convergence rate, and show complexity upper-bounds on the number of iterations to achieve a given accuracy. Finally, we demonstrate the performance of the proposed algorithms and the theoretical findings for solving a distributed optimal control problem.
Exploring EEG for Object Detection and Retrieval
Venue: arXiv cs.HC 2015
Year: 2015

This paper explores the potential for using Brain Computer Interfaces (BCI) as a relevance feedback mechanism in content-based image retrieval. We investigate if it is possible to capture useful EEG signals to detect if relevant objects are present in a dataset of realistic and complex images. We perform several experiments using a rapid serial visual presentation (RSVP) of images at different rates (5Hz and 10Hz) on 8 users with different degrees of familiarization with BCI and the dataset. We then use the feedback from the BCI and mouse-based interfaces to retrieve localized objects in a subset of TRECVid images. We show that it is indeed possible to detect such objects in complex images and, also, that users with previous knowledge on the dataset or experience with the RSVP outperform others. When the users have limited time to annotate the images (100 seconds in our experiments) both interfaces are comparable in performance. Comparing our best users in a retrieval task, we found that EEG-based relevance feedback outperforms mouse-based feedback. The realistic and complex image dataset differentiates our work from previous studies on EEG for image retrieval.
Multi-Objective Power Allocation for Energy Efficient Wireless Information and Power Transfer Systems
Venue: arXiv cs.IT 2015
Year: 2015

Simultaneous wireless information and power transfer (SWIPT) provides a promising solution for enabling perpetual wireless networks. As energy efficiency (EE) is an im- portant evaluation of system performance, this thesis studies energy-efficient resource allocation algorithm designs in SWIPT systems. We first investigate the trade-off between the EE for information transmission, the EE for power transfer, and the total transmit power in a basic SWIPT system with separated receivers. A multi-objective optimization problem is formulated under the constraint of maximum transmit power. We propose an algorithm which achieves flexible resource allocation for energy efficiencies maxi- mization and transmit power minimization. The trade-off region of the system design objectives is shown in simulation results. Further, we consider secure communication in a SWIPT system with power splitting receivers. Artificial noise is injected to the com- munication channel to combat the eavesdropping capability of potential eavesdroppers. A power-efficient resource allocation algorithm is developed when multiple legitimate information receivers and multi-antenna potential eavesdroppers co-exist in the system. Simulation results demonstrate a significant performance gain by the proposed optimal algorithm compared to suboptimal baseline schemes.
Analyzing and Modeling Special Offer Campaigns in Location-based Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

The proliferation of mobile handheld devices in combination with the technological advancements in mobile computing has led to a number of innovative services that make use of the location information available on such devices. Traditional yellow pages websites have now moved to mobile platforms, giving the opportunity to local businesses and potential, near-by, customers to connect. These platforms can offer an affordable advertisement channel to local businesses. One of the mechanisms offered by location-based social networks (LBSNs) allows businesses to provide special offers to their customers that connect through the platform. We collect a large time-series dataset from approximately 14 million venues on Foursquare and analyze the performance of such campaigns using randomization techniques and (non-parametric) hypothesis testing with statistical bootstrapping. Our main finding indicates that this type of promotions are not as effective as anecdote success stories might suggest. Finally, we design classifiers by extracting three different types of features that are able to provide an educated decision on whether a special offer campaign for a local business will succeed or not both in short and long term.
A Collection of Challenging Optimization Problems in Science, Engineering and Economics
Venue: arXiv cs.NA 2015
Year: 2015

Function optimization and finding simultaneous solutions of a system of nonlinear equations (SNE) are two closely related and important optimization problems. However, unlike in the case of function optimization in which one is required to find the global minimum and sometimes local minima, a database of challenging SNEs where one is required to find stationary points (extrama and saddle points) is not readily available. In this article, we initiate building such a database of important SNE (which also includes related function optimization problems), arising from Science, Engineering and Economics. After providing a short review of the most commonly used mathematical and computational approaches to find solutions of such systems, we provide a preliminary list of challenging problems by writing the Mathematical formulation down, briefly explaning the origin and importance of the problem and giving a short account on the currently known results, for each of the problems. We anticipate that this database will not only help benchmarking novel numerical methods for solving SNEs and function optimization problems but also will help advancing the corresponding research areas.
Earthquakes, Hurricanes, and Mobile Communication Patterns in the New York Metro Area: Collective Behavior during Extreme Events
Venue: arXiv cs.SI 2015
Year: 2015

We use wireless voice-call and text-message volumes to quantify spatiotemporal communication patterns in the New York Metro area before, during, and after the Virginia earthquake and Hurricane Irene in 2011. The earthquake produces an instantaneous and pervasive increase in volume and a ~90-minute temporal disruption to both call and text volume patterns, but call volume anomalies are much larger. The magnitude of call volume anomaly diminishes with distance from earthquake epicenter, with multiple clusters of high response in Manhattan. The hurricane produces a two-day, spatially varying disruption to normal call and text volume patterns. In most coastal areas, call volumes dropped anomalously in the afternoon before the hurricane's arrival, but text volumes showed a much less consistent pattern. These spatial patterns suggest partial, but not full, compliance with evacuation orders for low-lying areas. By helping us understand how people behave in actual emergencies, wireless data patterns may assist network operators and emergency planners who want to provide the best possible services to the community. We have been careful to preserve privacy throughout this work by using only anonymous and aggregate data.
Line-Broadcasting in Complete k-Trees
Venue: arXiv cs.DM 2015
Year: 2015

A line-broadcasting model in a connected graph $G=(V,E)$, $|V|=n$, is a model in which one vertex, called the {\it originator} of the broadcast holds a message that has to be transmitted to all vertices of the graph through placement of a series of calls over the graph. In this model, an informed vertex can transmit a message through a path of any length in a single time unit, as long as two transmissions do not use the same edge at the same time. Farley \cite{f} has shown that the process is completed within at most $\lceil \log_{2}n \rceil$ time units from any originator in a tree (and thus in any connected undirected graph). and that the cost of broadcasting one message from any vertex is at most $(n-1) \lceil \log_{2}n \rceil$. In this paper, we present lower and upper bounds for the cost to broadcast one message in a complete $k-$tree, from any vertex using the line-broadcasting model. We prove that if $B(u)$ is the minimum cost to broadcast in a graph $G=(V,E)$ from a vertex $u \in V$ using the line-broadcasting model, then $(1+o(1))n \le B(u) \le (2+o(1))n$, where $u$ is any vertex in a complete $k$-tree. Furthermore, for certain conditions, $B(u) \le (2-o(1))n$.
Application of the war of attrition game to the analysis of intellectual property disputes
Venue: arXiv cs.CY 2015
Year: 2015

In many developing countries intellectual property infringement and the commerce of pirate goods is an entrepreneurial activity. Digital piracy is very often the only media for having access to music, cinema, books and software. At the same time, bio-prospecting and infringement of indigenous knowledge rights by international consortiums is usual in places with high biodiversity. In these arenas transnational actors interact with local communities. Accusations of piracy often go both ways. This article analyzes the case of southeast Mexico. Using a war of attrition game theory model it explains different situations of intellectual property rights piracy and protection. It analyzes different levels of interaction and institutional settings from the global to the very local. The article proposes free IP zones as a solution of IP disputes. The formation of technological local clusters through Free Intellectual Property Zones (FIPZ) would allow firms to copy and share de facto public domain content for developing new products inside the FIPZ. Enforcement of intellectual property could be pursuit outside of the FIPZ. FIPZ are envisioned as a new type of a sui generis intellectual property regime.
Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity
Venue: arXiv cs.DC 2015
Year: 2015

We provide the first protocol that solves Byzantine agreement with optimal early stopping ($\min\{f+2,t+1\}$ rounds) and optimal resilience ($n>3t$) using polynomial message size and computation. All previous approaches obtained sub-optimal results and used resolve rules that looked only at the immediate children in the EIG (\emph{Exponential Information Gathering}) tree. At the heart of our solution are new resolve rules that look at multiple layers of the EIG tree.
Time Critical Multitasking for Multicore Microcontroller using XMOS Kit
Venue: arXiv cs.DC 2015
Year: 2015

This paper presents the research work on multicore microcontrollers using parallel, and time critical programming for the embedded systems. Due to the high complexity and limitations, it is very hard to work on the application development phase on such architectures. The experimental results mentioned in the paper are based on xCORE multicore microcontroller form XMOS. The paper also imitates multi-tasking and parallel programming for the same platform. The tasks assigned to multiple cores are executed simultaneously, which saves the time and energy. The relative study for multicore processor and multicore controller concludes that micro architecture based controller having multiple cores illustrates better performance in time critical multi-tasking environment. The research work mentioned here not only illustrates the functionality of multicore microcontroller, but also express the novel technique of programming, profiling and optimization on such platforms in real time environments.
Stop It, and Be Stubborn!
Venue: arXiv cs.LO 2015
Year: 2015

A system is AG EF terminating, if and only if from every reachable state, a terminal state is reachable. This publication argues that it is beneficial for both catching non-progress errors and stubborn set state space reduction to try to make verification models AG EF terminating. An incorrect mutual exclusion algorithm is used as an example. The error does not manifest itself, unless the first action of the customers is modelled differently from other actions. An appropriate method is to add an alternative first action that models the customer stopping for good. This method typically makes the model AG EF terminating. If the model is AG EF terminating, then the basic strong stubborn set method preserves safety and some progress properties without any additional condition for solving the ignoring problem. Furthermore, whether the model is AG EF terminating can be checked efficiently from the reduced state space.
Study of Some Recent Crossovers Effects on Speed and Accuracy of Genetic Algorithm, Using Symmetric Travelling Salesman Problem
Venue: arXiv cs.NE 2015
Year: 2015

The Travelling Salesman Problem (TSP) is one of the most famous optimization problems. The Genetic Algorithm (GA) is one of metaheuristics that have been applied to TSP. The Crossover and mutation operators are two important elements of GA. There are many TSP solver crossover operators. In this paper, we state implementation of some recent TSP solver crossovers at first and then we use each of them in GA to solve some Symmetric TSP (STSP) instances and finally compare their effects on speed and accuracy of presented GA.
Dynamic Programming on Nominal Graphs
Venue: arXiv cs.LO 2015
Year: 2015

Many optimization problems can be naturally represented as (hyper) graphs, where vertices correspond to variables and edges to tasks, whose cost depends on the values of the adjacent variables. Capitalizing on the structure of the graph, suitable dynamic programming strategies can select certain orders of evaluation of the variables which guarantee to reach both an optimal solution and a minimal size of the tables computed in the optimization process. In this paper we introduce a simple algebraic specification with parallel composition and restriction whose terms up to structural axioms are the graphs mentioned above. In addition, free (unrestricted) vertices are labelled with variables, and the specification includes operations of name permutation with finite support. We show a correspondence between the well-known tree decompositions of graphs and our terms. If an axiom of scope extension is dropped, several (hierarchical) terms actually correspond to the same graph. A suitable graphical structure can be found, corresponding to every hierarchical term. Evaluating such a graphical structure in some target algebra yields a dynamic programming strategy. If the target algebra satisfies the scope extension axiom, then the result does not depend on the particular structure, but only on the original graph. We apply our approach to the parking optimization problem developed in the ASCENS e-mobility case study, in collaboration with Volkswagen. Dynamic programming evaluations are particularly interesting for autonomic systems, where actual behavior often consists of propagating local knowledge to obtain global knowledge and getting it back for local decisions.
Detecting and Refactoring Operational Smells within the Domain Name System
Venue: arXiv cs.NI 2015
Year: 2015

The Domain Name System (DNS) is one of the most important components of the Internet infrastructure. DNS relies on a delegation-based architecture, where resolution of names to their IP addresses requires resolving the names of the servers responsible for those names. The recursive structures of the inter dependencies that exist between name servers associated with each zone are called dependency graphs. System administrators' operational decisions have far reaching effects on the DNSs qualities. They need to be soundly made to create a balance between the availability, security and resilience of the system. We utilize dependency graphs to identify, detect and catalogue operational bad smells. Our method deals with smells on a high-level of abstraction using a consistent taxonomy and reusable vocabulary, defined by a DNS Operational Model. The method will be used to build a diagnostic advisory tool that will detect configuration changes that might decrease the robustness or security posture of domain names before they become into production.
Maximum Entropy Linear Manifold for Learning Discriminative Low-dimensional Representation
Venue: arXiv cs.LG 2015
Year: 2015

Representation learning is currently a very hot topic in modern machine learning, mostly due to the great success of the deep learning methods. In particular low-dimensional representation which discriminates classes can not only enhance the classification procedure, but also make it faster, while contrary to the high-dimensional embeddings can be efficiently used for visual based exploratory data analysis. In this paper we propose Maximum Entropy Linear Manifold (MELM), a multidimensional generalization of Multithreshold Entropy Linear Classifier model which is able to find a low-dimensional linear data projection maximizing discriminativeness of projected classes. As a result we obtain a linear embedding which can be used for classification, class aware dimensionality reduction and data visualization. MELM provides highly discriminative 2D projections of the data which can be used as a method for constructing robust classifiers. We provide both empirical evaluation as well as some interesting theoretical properties of our objective function such us scale and affine transformation invariance, connections with PCA and bounding of the expected balanced accuracy error.
Longest Common Extensions in Sublinear Space
Venue: arXiv cs.DS 2015
Year: 2015

The longest common extension problem (LCE problem) is to construct a data structure for an input string $T$ of length $n$ that supports LCE$(i,j)$ queries. Such a query returns the length of the longest common prefix of the suffixes starting at positions $i$ and $j$ in $T$. This classic problem has a well-known solution that uses $O(n)$ space and $O(1)$ query time. In this paper we show that for any trade-off parameter $1 \leq τ\leq n$, the problem can be solved in $O(\frac{n}τ)$ space and $O(τ)$ query time. This significantly improves the previously best known time-space trade-offs, and almost matches the best known time-space product lower bound.
A Delay Aware Routing Protocol for Wireless Sensor Networks
Venue: arXiv cs.NI 2015
Year: 2015

Wireless Sensor Networks (WSNs) consist of sensor nodes which can be deployed for various operations such as agriculture and environmental sensing, wild life monitoring, health care, military surveillance, industrial control, home automation, security etc. Quality of Service (QoS) is an important issue in wireless sensor networks (WSNs) and providing QoS support in WSNs is an emerging area of research. Due to resource constraints nature of sensor networks like processing power, memory, bandwidth, energy etc. providing QoS support in WSNs is a challenging task. Delay is an important QoS parameter for forwarding data in a time constraint WSNs environment. In this paper we propose a delay aware routing protocol for transmission of time critical event information to the Sink of WSNs. The performance of the proposed protocol is evaluated by NS2 simulations under different scenarios.
Fundamental Relations Between Reactive and Proactive Relay-Selection Strategies
Venue: arXiv cs.IT 2015
Year: 2015

Two major relay-selection strategies widely applied in cooperative decode-and-forward (DF) relaying networks, namely, reactive relay selection (RRS) and proactive relay selection (PRS), are generally looked upon as independent and studied separately. In this paper, RRS and PRS are proven to be equivalent with respect to the end-to-end outage probability from the first principle, i.e. their respective relay-selection criteria. On the other hand, RRS is shown to be superior to PRS with respect to the end-to-end symbol error rate. Afterwards, a case study of a general DF relaying system, subject to co-channel interferences and additive white Gaussian noise at both the relaying nodes and the destination, is performed to explicitly illustrate the aforementioned outage equivalence. These fundamental relations provide intuitive yet insightful performance benchmarks for comparing various applications of these two relay-selection strategies.
On absorption in semigroups and $n$-ary semigroups
Venue: arXiv cs.LO 2015
Year: 2015

The notion of absorption was developed a few years ago by Barto and Kozik and immediately found many applications, particularly in topics related to the constraint satisfaction problem. We investigate the behavior of absorption in semigroups and n-ary semigroups (that is, algebras with one n-ary associative operation). In the case of semigroups, we give a simple necessary and sufficient condition for a semigroup to be absorbed by its subsemigroup. We then proceed to n-ary semigroups, where we conjecture an analogue of this necessary and sufficient condition, and prove that the conjectured condition is indeed necessary and sufficient for B to absorb A (where A is an n-ary semigroup and B is its n-ary subsemigroup) in the following three cases: when A is commutative, when |A-B|=1 and when A is an idempotent ternary semigroup.