OpenRaiser/Intern-Atlas huggingface dataset:
A Checklist for the Evaluation of Pedestrian Simulation Software Functionalities
Venue: arXiv cs.MA 2014
Year: 2014

The employment of micro-simulation (agent-based) tools in the phase of design of public and private spaces and facilities and for the definition of transport schemes that impact on pedestrian flows, thanks to their achieved accuracy and predictive capacity, has become a consolidated practice. These instruments provide support to the organization of spaces, services and facilities and to the definition of management procedures for normal and emergency situations. The employment of these tools is effective for various but not for all the contexts, nevertheless new features and functions are under constant development and new products are often launched on the market. Therefore, there is a higher necessity of a standard criteria both for the evaluation of the kinds of function that these software provide, at use of practitioners and end-users, and for the definition of software requirements as a reference for the developers that aim at being competitive on this market. On the basis of our experience as pedestrian modellers and as researchers in the crowd modelling area, we designed a comprehensive and detailed ready-to-use checklist for the quantitative evaluation of Pedestrian Simulation Software functionalities that aims at capturing all the aspects that we claim that are useful to undertake a professional study. These functions in our opinion are necessary to provide accurate results in the planning of new facilities or schemes that involve pedestrian activities. With this work we propose a set of criteria of evaluation for these products also to encourage a debate for the definition of objective standards for pedestrian simulation software certification.
Compact Argumentation Frameworks
Venue: arXiv cs.AI 2014
Year: 2014

Abstract argumentation frameworks (AFs) are one of the most studied formalisms in AI. In this work, we introduce a certain subclass of AFs which we call compact. Given an extension-based semantics, the corresponding compact AFs are characterized by the feature that each argument of the AF occurs in at least one extension. This not only guarantees a certain notion of fairness; compact AFs are thus also minimal in the sense that no argument can be removed without changing the outcome. We address the following questions in the paper: (1) How are the classes of compact AFs related for different semantics? (2) Under which circumstances can AFs be transformed into equivalent compact ones? (3) Finally, we show that compact AFs are indeed a non-trivial subclass, since the verification problem remains coNP-hard for certain semantics.
A graph-based mathematical morphology reader
Venue: arXiv cs.CV 2014
Year: 2014

This survey paper aims at providing a "literary" anthology of mathematical morphology on graphs. It describes in the English language many ideas stemming from a large number of different papers, hence providing a unified view of an active and diverse field of research.
A Flow Sensitive Security Model for Cloud Computing Systems
Venue: arXiv cs.CR 2014
Year: 2014

The extent and importance of cloud computing is rapidly increasing due to the ever increasing demand for internet services and communications. Instead of building individual information technology infrastructure to host databases or software, a third party can host them in its large server clouds. Large organizations may wish to keep sensitive information on their more restricted servers rather than in the public cloud. This has led to the introduction of federated cloud computing (FCC) in which both public and private cloud computing resources are used.
Building Effective Virtual Teams: How to Overcome the Problems of Trust and Identity in Virtual Teams
Venue: arXiv cs.CY 2014
Year: 2014

This article explores some of the challenges faced when managing virtual teams, in particular the role played by trust and identity in virtual teams. It outlines why teams and virtual teams have become a valuable part of the modern organization and presents ten short case studies that illustrate the range of activities in which virtual teams can be found. Following this, the article examines some of the common problems encountered in virtual team working. It discusses two broad classes of solutions. The first are solutions that are essentially technical in nature (i.e., where changes to or improvements in technology would help to solve or ameliorate the problem); the second are more organizationally based (i.e., where the root of the problem is in people and how they are managed). The article concludes that both the technical and the organizational solutions need to be considered in parallel if an attempt to build an effective virtual team is to be successful.
Deployment Calculation and Analysis for a Fail-Operational Automotive Platform
Venue: arXiv cs.SE 2014
Year: 2014

In domains like automotive, safety-critical features are increasingly realized by software. Some features might even require fail-operational behavior, so that they must be provided even in the presence of random hardware failures. A new fault-tolerant SW/HW architecture for electric vehicles provides inherent safety capabilities that enable fail-operational features. In this paper we introduce a formal model of this architecture and an approach to calculate valid deployments of mixed-critical software-components to the execution nodes, while ensuring fail-operational behavior of certain components. Calculated redeployments cover the cases in which faulty execution nodes have to be isolated. This allows to formally analyze which set of features can be provided under decreasing available execution resources.
Fault Modelling in System-of-Systems Contracts
Venue: arXiv cs.SE 2014
Year: 2014

The nature of Systems of Systems (SoSs), large complex systems composed of independent, geographically distributed and continuously evolving constituent systems, means that faults are unavoidable. Previous work on defining contractual specifications of the constituent systems of SoSs does not provide any explicit consideration for faults. In this paper we address that gap by extending an existing pattern for modelling contracts with fault modelling concepts. The proposed extensions are introduced with respect to an Audio Visual SoS case study from Bang and Olufsen, before discussing how they relate to previous work on modelling faults in SoSs.
Monotonicity, Revenue Equivalence and Budgets
Venue: arXiv cs.GT 2014
Year: 2014

We study multidimensional mechanism design in a common scenario where players have private information about their willingness to pay and their ability to pay. We provide a complete characterization of dominant-strategy incentive-compatible direct mechanisms where over-reporting the budget is not possible. In several settings, reporting larger budgets can be made suboptimal with a small randomized modification to the payments. We then derive a closely related partial characterization for the general case where players can arbitrarily misreport their private budgets. Immediate applications of these results include simple characterizations for mechanisms with publicly-known budgets and for mechanisms without monetary transfers. The celebrated revenue equivalence theorem states that the seller"s revenue for a broad class of standard auction formats and settings will be the same in equilibrium. Our main application is a revenue equivalence theorem for financially constrained bidders.
OSCAR: Object Security Architecture for the Internet of Things
Venue: arXiv cs.NI 2014
Year: 2014

Billions of smart, but constrained objects wirelessly connected to the global network require novel paradigms in network design. New protocol standards, tailored to constrained devices, have been designed taking into account requirements such as asynchronous application traffic, need for caching, and group communication. The existing connection oriented security architecture is not able to keep up---first, in terms of the supported features, but also in terms of the scale and resulting latency on small constrained devices. In this paper, we propose an architecture that leverages the security concepts both from content-centric and traditional connection-oriented approaches. We rely on secure channels established by means of (D)TLS for key exchange, but we get rid of the notion of the 'state' among communicating entities. We provide a mechanism to protect from replay attacks by coupling our scheme with the CoAP application protocol. Our object-based security architecture (OSCAR) intrinsically supports caching and multicast, and does not affect the radio duty-cycling operation of constrained objects. We evaluate OSCAR in two cases: 802.15.4 Low Power and Lossy Networks (LLN) and Machine-to-Machine (M2M) communication for two different hardware platforms and MAC layers on a real testbed and using the Cooja emulator. We show significant energy savings at constrained servers and reasonable delays. We also discuss the applicability of OSCAR to Smart City deployments.
Quantum(-like) common knowledge: Binmore-Brandenburger operator approach
Venue: arXiv cs.LO 2014
Year: 2014

We present the detailed account of the quantum(-like) viewpoint to common knowledge. The Binmore-Brandenburger operator approach to the notion of common knowledge is extended to the quantum case. We develop a special quantum(-like) model of common knowledge based on information representations of agents which can be operationally represented by Hermitian operators. For simplicity, we assume that each agent constructs her/his information representation by using just one operator. However, different agents use in general representations based on noncommuting operators, i.e., incompatible representations. The quantum analog of basic system of common knowledge features ${\cal K}1-{\cal K}5$ is derived.
Domination games played on line graphs of complete multipartite graphs
Venue: arXiv cs.DM 2014
Year: 2014

The domination game on a graph $G$ (introduced by B. Brešar, S. Klavžar, D.F. Rall \cite{BKR2010}) consists of two players, Dominator and Staller, who take turns choosing a vertex from $G$ such that whenever a vertex is chosen by either player, at least one additional vertex is dominated. Dominator wishes to dominate the graph in as few steps as possible, and Staller wishes to delay this process as much as possible. The game domination number $γ_{\small g}(G)$ is the number of vertices chosen when Dominator starts the game; when Staller starts, it is denoted by $γ_{\small g}^{\prime }(G).$ In this paper, the domination game on line graph $L\left( K_{\overline{m}}\right) $ of complete multipartite graph $K_{\overline{m}}$ $(\overline{m}\equiv (m_{1},...,m_{n})\in \mathbb{N} ^{n})$ is considered, the exact values for game domination numbers are obtained and optimal strategy for both players is described. Particularly, it is proved that for $m_{1}\leq m_{2}\leq ...\leq m_{n}$ both $γ_{\small g}\left( L\left( K_{\overline{m}}\right) \right) =\min \left\{ \left\lceil \frac{2}{3}\left\vert V\left( K_{\overline{m}}\right) \right\vert \right\rceil ,\right.$ $\left. 2\max \left\{ \left\lceil \frac{1}{2}\left( m_{1}+...+m_{n-1}\right) \right\rceil ,\text{ }m_{n-1}\right\} \right\} -1$ when $n\geq 2$ and $γ_{g}^{\prime }(L\left( K_{\overline{m}}\right) )=\min \left\{ \left\lceil \frac{2}{3}\left( \left\vert V(K_{_{\overline{m}}})\right\vert -2\right) \right\rceil ,\right.$ $\left. 2\max \left\{ \left\lceil \frac{1}{2}\left( m_{1}+...+m_{n-1}-1\right) \right\rceil ,\text{ }m_{n-1}\right\} \right\} $ when $n\geq 4$.
Parameterized Streaming Algorithms for Vertex Cover
Venue: arXiv cs.DS 2014
Year: 2014

As graphs continue to grow in size, we seek ways to effectively process such data at scale. The model of streaming graph processing, in which a compact summary is maintained as each edge insertion/deletion is observed, is an attractive one. However, few results are known for optimization problems over such dynamic graph streams. In this paper, we introduce a new approach to handling graph streams, by instead seeking solutions for the parameterized versions of these problems where we are given a parameter $k$ and the objective is to decide whether there is a solution bounded by $k$. By combining kernelization techniques with randomized sketch structures, we obtain the first streaming algorithms for the parameterized versions of the Vertex Cover problem. We consider the following three models for a graph stream on $n$ nodes: 1. The insertion-only model where the edges can only be added. 2. The dynamic model where edges can be both inserted and deleted. 3. The \emph{promised} dynamic model where we are guaranteed that at each timestamp there is a solution of size at most $k$. In each of these three models we are able to design parameterized streaming algorithms for the Vertex Cover problem. We are also able to show matching lower bound for the space complexity of our algorithms. (Due to the arXiv limit of 1920 characters for abstract field, please see the abstract in the paper for detailed description of our results)
Estimation of Optimized Energy and Latency Constraints for Task Allocation in 3d Network on Chip
Venue: arXiv cs.OH 2014
Year: 2014

In Network on Chip (NoC) rooted system, energy consumption is affected by task scheduling and allocation schemes which affect the performance of the system. In this paper we test the pre-existing proposed algorithms and introduced a new energy skilled algorithm for 3D NoC architecture. An efficient dynamic and cluster approaches are proposed along with the optimization using bio-inspired algorithm. The proposed algorithm has been implemented and evaluated on randomly generated benchmark and real life application such as MMS, Telecom and VOPD. The algorithm has also been tested with the E3S benchmark and has been compared with the existing mapping algorithm spiral and crinkle and has shown better reduction in the communication energy consumption and shows improvement in the performance of the system. On performing experimental analysis of proposed algorithm results shows that average reduction in energy consumption is 49%, reduction in communication cost is 48% and average latency is 34%. Cluster based approach is mapped onto NoC using Dynamic Diagonal Mapping (DDMap), Crinkle and Spiral algorithms and found DDmap provides improved result. On analysis and comparison of mapping of cluster using DDmap approach the average energy reduction is 14% and 9% with crinkle and spiral.
Symmetric Algorithm Survey: A Comparative Analysis
Venue: arXiv cs.CR 2014
Year: 2014

Information Security has become an important issue in modern world as the popularity and infiltration of internet commerce and communication technologies has emerged, making them a prospective medium to the security threats. To surmount these security threats modern data communications uses cryptography an effective, efficient and essential component for secure transmission of information by implementing security parameter counting Confidentiality, Authentication, accountability, and accuracy. To achieve data security different cryptographic algorithms (Symmetric & Asymmetric) are used that jumbles data in to scribbled format that can only be reversed by the user that have to desire key. This paper presents a comprehensive comparative analysis of different existing cryptographic algorithms (symmetric) based on their Architecture, Scalability, Flexibility, Reliability, Security and Limitation that are essential for secure communication (Wired or Wireless).
Computational Complexity of Approximate Nash Equilibrium in Large Games
Venue: arXiv cs.GT 2014
Year: 2014

We prove that finding an epsilon-Nash equilibrium in a succinctly representable game with many players is PPAD-hard for constant epsilon. Our proof uses succinct games, i.e. games whose payoff function is represented by a circuit. Our techniques build on a recent query complexity lower bound by Babichenko.
Parallel computation using active self-assembly
Venue: arXiv cs.ET 2014
Year: 2014

We study the computational complexity of the recently proposed nubot model of molecular-scale self-assembly. The model generalises asynchronous cellular automata to have non-local movement where large assemblies of molecules can be pushed and pulled around, analogous to millions of molecular motors in animal muscle effecting the rapid movement of macroscale arms and legs. We show that the nubot model is capable of simulating Boolean circuits of polylogarithmic depth and polynomial size, in only polylogarithmic expected time. In computational complexity terms, we show that any problem from the complexity class NC is solvable in polylogarithmic expected time and polynomial workspace using nubots. Along the way, we give fast parallel nubot algorithms for a number of problems including line growth, sorting, Boolean matrix multiplication and space-bounded Turing machine simulation, all using a constant number of nubot states (monomer types). Circuit depth is a well-studied notion of parallel time, and our result implies that the nubot model is a highly parallel model of computation in a formal sense. Asynchronous cellular automata are not capable of this parallelism, and our result shows that adding a rigid-body movement primitive to such a model, to get the nubot model, drastically increases parallel processing abilities.
Kaggle LSHTC4 Winning Solution
Venue: arXiv cs.AI 2014
Year: 2014

Our winning submission to the 2014 Kaggle competition for Large Scale Hierarchical Text Classification (LSHTC) consists mostly of an ensemble of sparse generative models extending Multinomial Naive Bayes. The base-classifiers consist of hierarchically smoothed models combining document, label, and hierarchy level Multinomials, with feature pre-processing using variants of TF-IDF and BM25. Additional diversification is introduced by different types of folds and random search optimization for different measures. The ensemble algorithm optimizes macroFscore by predicting the documents for each label, instead of the usual prediction of labels per document. Scores for documents are predicted by weighted voting of base-classifier outputs with a variant of Feature-Weighted Linear Stacking. The number of documents per label is chosen using label priors and thresholding of vote scores. This document describes the models and software used to build our solution. Reproducing the results for our solution can be done by running the scripts included in the Kaggle package. A package omitting precomputed result files is also distributed. All code is open source, released under GNU GPL 2.0, and GPL 3.0 for Weka and Meka dependencies.
NetSecCC: A Scalable and Fault-tolerant Architecture without Outsourcing Cloud Network Security
Venue: arXiv cs.CR 2014
Year: 2014

Modern cloud computing platforms based on virtual machine monitors carry a variety of complex business that present many network security vulnerabilities. At present, the traditional architecture employs a number of security devices at front-end of cloud computing to protect its network security. Under the new environment, however, this approach can not meet the needs of cloud security. New cloud security vendors and academia also made great efforts to solve network security of cloud computing, unfortunately, they also cannot provide a perfect and effective method to solve this problem. We introduce a novel network security architecture for cloud computing (NetSecCC) that addresses this problem. NetSecCC not only provides an effective solution for network security issues of cloud computing, but also greatly improves in scalability, fault-tolerant, resource utilization, etc. We have implemented a proof-of-concept prototype about NetSecCC and proved by experiments that NetSecCC is an effective architecture with minimal performance overhead that can be applied to the extensive practical promotion in cloud computing.
On the Impact of Oscillator Phase Noise on the Uplink Performance in a Massive MIMO-OFDM System
Venue: arXiv cs.IT 2014
Year: 2014

In this work we study the effect of oscillator phase noise on the uplink performance of a massive multiple-input multiple output system. Specifically, we consider an orthogonal frequency division multiplexing-based uplink transmission and analyze two scenarios: (a) all the base station (BS) antennas are fed by a common oscillator, and (b) each of the BS antennas is fed by a different oscillator. For the scenarios considered, we derive the instantaneous signal-to-noise ratio on each subcarrier and analyze the ergodic capacity when a linear receiver is used. Furthermore, we propose a phase noise tracking algorithm based on Kalman filtering that mitigates the effect of phase noise on the system performance.
Single machine slack due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we consider the slack due-window assignment model and study a single machine scheduling problem of linear time-dependent deteriorating jobs and a deteriorating maintenance activity. The cost for each job consists of four components: earliness, tardiness, window location and window size. The objective is to schedule the jobs and to assign the maintenance activity and due-windows such that the total cost among all the jobs is minimized. A polynomial-time algorithm with the running time not exceeding $O(n^2logn)$ to give a solution to this problem is introduced, where $n$ is the number of jobs.
Hardness of Graph Pricing through Generalized Max-Dicut
Venue: arXiv cs.DS 2014
Year: 2014

The Graph Pricing problem is among the fundamental problems whose approximability is not well-understood. While there is a simple combinatorial 1/4-approximation algorithm, the best hardness result remains at 1/2 assuming the Unique Games Conjecture (UGC). We show that it is NP-hard to approximate within a factor better than 1/4 under the UGC, so that the simple combinatorial algorithm might be the best possible. We also prove that for any $ε> 0$, there exists $δ> 0$ such that the integrality gap of $n^δ$-rounds of the Sherali-Adams hierarchy of linear programming for Graph Pricing is at most 1/2 + $ε$. This work is based on the effort to view the Graph Pricing problem as a Constraint Satisfaction Problem (CSP) simpler than the standard and complicated formulation. We propose the problem called Generalized Max-Dicut($T$), which has a domain size $T + 1$ for every $T \geq 1$. Generalized Max-Dicut(1) is well-known Max-Dicut. There is an approximation-preserving reduction from Generalized Max-Dicut on directed acyclic graphs (DAGs) to Graph Pricing, and both our results are achieved through this reduction. Besides its connection to Graph Pricing, the hardness of Generalized Max-Dicut is interesting in its own right since in most arity two CSPs studied in the literature, SDP-based algorithms perform better than LP-based or combinatorial algorithms --- for this arity two CSP, a simple combinatorial algorithm does the best.
Polynomial complexity of polar codes for non-binary alphabets, key agreement and Slepian-Wolf coding
Venue: arXiv cs.IT 2014
Year: 2014

We consider polar codes for memoryless sources with side information and show that the blocklength, construction, encoding and decoding complexities are bounded by a polynomial of the reciprocal of the gap between the compression rate and the conditional entropy. This extends the recent results of Guruswami and Xia to a slightly more general setting, which in turn can be applied to (1) sources with non-binary alphabets, (2) key generation for discrete and Gaussian sources, and (3) Slepian-Wolf coding and multiple accessing. In each of these cases, the complexity scaling with respect to the number of users is also controlled. In particular, we construct coding schemes for these multi-user information theory problems which achieve optimal rates with an overall polynomial complexity.