OpenRaiser/Intern-Atlas huggingface dataset:
Efficient coordination mechanisms for unrelated machine scheduling
Venue: arXiv cs.GT 2011
Year: 2011

We present new coordination mechanisms for scheduling selfish jobs on $m$ unrelated machines. A coordination mechanism aims to mitigate the impact of selfishness of jobs on the efficiency of schedules by defining a local scheduling policy on each machine. The scheduling policies induce a game among the jobs and each job prefers to be scheduled on a machine so that its completion time is minimum given the assignments of the other jobs. We consider the maximum completion time among all jobs as the measure of the efficiency of schedules. The approximation ratio of a coordination mechanism quantifies the efficiency of pure Nash equilibria (price of anarchy) of the induced game. Our mechanisms are deterministic, local, and preemptive. Our first coordination mechanism has approximation ratio $Θ(\log m)$ and guarantees that the induced game has pure Nash equilibria. This result improves a bound of $O(\log^2 m)$ due to Azar, Jain, and Mirrokni and uses a global ordering of the jobs according to their distinct IDs. Our second mechanism handles anonymous jobs and has approximation ratio $O(\frac{\log m}{\log \log m})$ although the game induced is not a potential game and, hence, the existence of pure Nash equilibria is not guaranteed by potential function arguments. However, it provides evidence that the known lower bounds for non-preemptive coordination mechanisms could be beaten using preemptive scheduling policies. Our third coordination mechanism also handles anonymous jobs and has a nice cost-revealing potential function. We use this potential function in order to prove the existence of equilibria and to upper-bound the price of anarchy of the induced game by $O(\log^2m)$. Our third coordination mechanism is the first that handles anonymous jobs and simultaneously guarantees that the induced game is a potential game and has bounded price of anarchy.
Where Have You Been? Secure Location Provenance for Mobile Devices
Venue: arXiv cs.CR 2011
Year: 2011

With the advent of mobile computing, location-based services have recently gained popularity. Many applications use the location provenance of users, i.e., the chronological history of the users' location for purposes ranging from access control, authentication, information sharing, and evaluation of policies. However, location provenance is subject to tampering and collusion attacks by malicious users. In this paper, we examine the secure location provenance problem. We introduce a witness-endorsed scheme for generating collusion-resistant location proofs. We also describe two efficient and privacy-preserving schemes for protecting the integrity of the chronological order of location proofs. These schemes, based on hash chains and Bloom filters respectively, allow users to prove the order of any arbitrary subsequence of their location history to auditors. Finally, we present experimental results from our proof-of-concept implementation on the Android platform and show that our schemes are practical in today's mobile devices.
Distributed Robust Multi-Cell Coordinated Beamforming with Imperfect CSI: An ADMM Approach
Venue: arXiv cs.IT 2011
Year: 2011

Multi-cell coordinated beamforming (MCBF), where multiple base stations (BSs) collaborate with each other in the beamforming design for mitigating the inter-cell interference, has been a subject drawing great attention recently. Most MCBF designs assume perfect channel state information (CSI) of mobile stations (MSs); however CSI errors are inevitable at the BSs in practice. Assuming elliptically bounded CSI errors, this paper studies the robust MCBF design problem that minimizes the weighted sum power of BSs subject to worst-case signal-to-interference-plus-noise ratio (SINR) constraints on the MSs. Our goal is to devise a distributed optimization method that can obtain the worst-case robust beamforming solutions in a decentralized fashion, with only local CSI used at each BS and little backhaul signaling for message exchange between BSs. However, the considered problem is difficult to handle even in the centralized form. We first propose an efficient approximation method in the centralized form, based on the semidefinite relaxation (SDR) technique. To obtain the robust beamforming solution in a decentralized fashion, we further propose a distributed robust MCBF algorithm, using a distributed convex optimization technique known as alternating direction method of multipliers (ADMM). We analytically show the convergence of the proposed distributed robust MCBF algorithm to the optimal centralized solution and its better bandwidth efficiency in backhaul signaling over the existing dual decomposition based algorithms. Simulation results are presented to examine the effectiveness of the proposed SDR method and the distributed robust MCBF algorithm.
A note on the generalized min-sum set cover problem
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, we consider the generalized min-sum set cover problem, introduced by Azar, Gamzu, and Yin. Bansal, Gupta, and Krishnaswamy give a 485-approximation algorithm for the problem. We are able to alter their algorithm and analysis to obtain a 28-approximation algorithm, improving the performance guarantee by an order of magnitude. We use concepts from $α$-point scheduling to obtain our improvements.
Study of a Hybrid - Analog TV and Ethernet- Home Data Link using a Coaxial Cable
Venue: arXiv cs.MM 2011
Year: 2011

The paper presents an implementation and compatibility tests of a simple home network implemented in a nonconventional manner using a CATV coaxial cable. Reusing the cable, normally designated to supply RF modulated TV signals from cable TV networks, makes possible to add data services as well. A short presentation of the technology is given with an investigation of the main performances obtained using this technique. The measurements revealed that this simple solution makes possible to have both TV and data services with performances close to traditional home data services: cable modems or ADSL, with minimal investments. This technology keeps also open the possibility for future improvements of the network: DVB-C or Data via Cable Modems.
The parallel versus branching recurrences in computability logic
Venue: arXiv cs.LO 2011
Year: 2011

This paper shows that the basic logic induced by the parallel recurrence of Computability Logic is a proper superset of the basic logic induced by the branching recurrence. The latter is known to be precisely captured by the cirquent calculus system CL15, conjectured by Japaridze to remain sound---but not complete---with parallel recurrence instead of branching recurrence. The present result is obtained by positively verifying that conjecture. A secondary result of the paper is showing that parallel recurrence is strictly weaker than branching recurrence in the sense that, while the latter logically implies the former, vice versa does not hold.
iBGP and Constrained Connectivity
Venue: arXiv cs.DS 2011
Year: 2011

We initiate the theoretical study of the problem of minimizing the size of an iBGP overlay in an Autonomous System (AS) in the Internet subject to a natural notion of correctness derived from the standard "hot-potato" routing rules. For both natural versions of the problem (where we measure the size of an overlay by either the number of edges or the maximum degree) we prove that it is NP-hard to approximate to a factor better than $Ω(\log n)$ and provide approximation algorithms with ratio $\tilde{O}(\sqrt{n})$. In addition, we give a slightly worse $\tilde{O}(n^{2/3})$-approximation based on primal-dual techniques that has the virtue of being both fast and good in practice, which we show via simulations on the actual topologies of five large Autonomous Systems. The main technique we use is a reduction to a new connectivity-based network design problem that we call Constrained Connectivity. In this problem we are given a graph $G=(V,E)$, and for every pair of vertices $u,v \in V$ we are given a set $S(u,v) \subseteq V$ called the safe set of the pair. The goal is to find the smallest subgraph $H$ of $G$ in which every pair of vertices $u,v$ is connected by a path contained in $S(u,v)$. We show that the iBGP problem can be reduced to the special case of Constrained Connectivity where $G = K_n$ and safe sets are defined geometrically based on the IGP distances in the AS. We also believe that Constrained Connectivity is an interesting problem in its own right, so provide stronger hardness results ($2^{\log^{1-ε} n}$-hardness of approximation) and integrality gaps ($n^{1/3 - ε}$) for the general case. On the positive side, we show that Constrained Connectivity turns out to be much simpler for some interesting special cases other than iBGP: when safe sets are symmetric and hierarchical, we give a polynomial time algorithm that computes an optimal solution.
On the Approximability and Hardness of Minimum Topic Connected Overlay and Its Special Instances
Venue: arXiv cs.DS 2011
Year: 2011

In the context of designing a scalable overlay network to support decentralized topic-based pub/sub communication, the Minimum Topic-Connected Overlay problem (Min-TCO in short) has been investigated: Given a set of t topics and a collection of n users together with the lists of topics they are interested in, the aim is to connect these users to a network by a minimum number of edges such that every graph induced by users interested in a common topic is connected. It is known that Min-TCO is NP-hard and approximable within O(log t) in polynomial time. In this paper, we further investigate the problem and some of its special instances. We give various hardness results for instances where the number of topics in which an user is interested in is bounded by a constant, and also for the instances where the number of users interested in a common topic is constant. For the latter case, we present a first constant approximation algorithm. We also present some polynomial-time algorithms for very restricted instances of Min-TCO.
Fuzzy Topological Systems
Venue: arXiv cs.LO 2011
Year: 2011

Dialectica categories are a very versatile categorical model of linear logic. These have been used to model many seemingly different things (e.g., Petri nets and Lambek's calculus). In this note, we expand our previous work on fuzzy petri nets to deal with fuzzy topological systems. One basic idea is to use as the dualizing object in the Dialectica categories construction, the unit real interval [0,1], which has all the properties of a {\em lineale}. The second basic idea is to generalize Vickers's notion of a topological system.
Subset sum phase transitions and data compression
Venue: arXiv cs.IT 2011
Year: 2011

We propose a rigorous analysis approach for the subset sum problem in the context of lossless data compression, where the phase transition of the subset sum problem is directly related to the passage between ambiguous and non-ambiguous decompression, for a compression scheme that is based on specifying the sequence composition. The proposed analysis lends itself to straightforward extensions in several directions of interest, including non-binary alphabets, incorporation of side information at the decoder (Slepian-Wolf coding), and coding schemes based on multiple subset sums. It is also demonstrated that the proposed technique can be used to analyze the critical behavior in a more involved situation where the sequence composition is not specified by the encoder.
Lower Bound for Envy-Free and Truthful Makespan Approximation on Related Machines
Venue: arXiv cs.GT 2011
Year: 2011

We study problems of scheduling jobs on related machines so as to minimize the makespan in the setting where machines are strategic agents. In this problem, each job $j$ has a length $l_{j}$ and each machine $i$ has a private speed $t_{i}$. The running time of job $j$ on machine $i$ is $t_{i}l_{j}$. We seek a mechanism that obtains speed bids of machines and then assign jobs and payments to machines so that the machines have incentive to report true speeds and the allocation and payments are also envy-free. We show that 1. A deterministic envy-free, truthful, individually rational, and anonymous mechanism cannot approximate the makespan strictly better than $2-1/m$, where $m$ is the number of machines. This result contrasts with prior work giving a deterministic PTAS for envy-free anonymous assignment and a distinct deterministic PTAS for truthful anonymous mechanism. 2. For two machines of different speeds, the unique deterministic scalable allocation of any envy-free, truthful, individually rational, and anonymous mechanism is to allocate all jobs to the quickest machine. This allocation is the same as that of the VCG mechanism, yielding a 2-approximation to the minimum makespan. 3. No payments can make any of the prior published monotone and locally efficient allocations that yield better than an $m$-approximation for $\qcmax$ \cite{aas, at,ck10, dddr, kovacs} a truthful, envy-free, individually rational, and anonymous mechanism.
Homomorphic Self-repairing Codes for Agile Maintenance of Distributed Storage Systems
Venue: arXiv cs.DC 2011
Year: 2011

Distributed data storage systems are essential to deal with the need to store massive volumes of data. In order to make such a system fault-tolerant, some form of redundancy becomes crucial, incurring various overheads - most prominently in terms of storage space and maintenance bandwidth requirements. Erasure codes, originally designed for communication over lossy channels, provide a storage efficient alternative to replication based redundancy, however entailing high communication overhead for maintenance, when some of the encoded fragments need to be replenished in news ones after failure of some storage devices. We propose as an alternative a new family of erasure codes called self-repairing codes (SRC) taking into account the peculiarities of distributed storage systems, specifically the maintenance process. SRC has the following salient features: (a) encoded fragments can be repaired directly from other subsets of encoded fragments by downloading less data than the size of the complete object, ensuring that (b) a fragment is repaired from a fixed number of encoded fragments, the number depending only on how many encoded blocks are missing and independent of which specific blocks are missing. This paper lays the foundations by defining the novel self-repairing codes, elaborating why the defined characteristics are desirable for distributed storage systems. Then homomorphic self-repairing codes (HSRC) are proposed as a concrete instance, whose various aspects and properties are studied and compared - quantitatively or qualitatively with respect to other codes including traditional erasure codes as well as other recent codes designed specifically for storage applications.
Fingerprint recognition using standardized fingerprint model
Venue: arXiv cs.CV 2011
Year: 2011

Fingerprint recognition is one of most popular and accuracy Biometric technologies. Nowadays, it is used in many real applications. However, recognizing fingerprints in poor quality images is still a very complex problem. In recent years, many algorithms, models...are given to improve the accuracy of recognition system. This paper discusses on the standardized fingerprint model which is used to synthesize the template of fingerprints. In this model, after pre-processing step, we find the transformation between templates, adjust parameters, synthesize fingerprint, and reduce noises. Then, we use the final fingerprint to match with others in FVC2004 fingerprint database (DB4) to show the capability of the model.
Communication Systems for Grid Integration of Renewable Energy Resources
Venue: arXiv cs.IT 2011
Year: 2011

There is growing interest in renewable energy around the world. Since most renewable sources are intermittent in nature, it is a challenging task to integrate renewable energy resources into the power grid infrastructure. In this grid integration, communication systems are crucial technologies, which enable the accommodation of distributed renewable energy generation and play extremely important role in monitoring, operating, and protecting both renewable energy generators and power systems. In this paper, we review some communication technologies available for grid integration of renewable energy resources. Then, we present the communication systems used in a real renewable energy project, Bear Mountain Wind Farm (BMW) in British Columbia, Canada. In addition, we present the communication systems used in Photovoltaic Power Systems (PPS). Finally, we outline some research challenges and possible solutions about the communication systems for grid integration of renewable energy resources.
Discovering Knowledge using a Constraint-based Language
Venue: arXiv cs.LG 2011
Year: 2011

Discovering pattern sets or global patterns is an attractive issue from the pattern mining community in order to provide useful information. By combining local patterns satisfying a joint meaning, this approach produces patterns of higher level and thus more useful for the data analyst than the usual local patterns, while reducing the number of patterns. In parallel, recent works investigating relationships between data mining and constraint programming (CP) show that the CP paradigm is a nice framework to model and mine such patterns in a declarative and generic way. We present a constraint-based language which enables us to define queries addressing patterns sets and global patterns. The usefulness of such a declarative approach is highlighted by several examples coming from the clustering based on associations. This language has been implemented in the CP framework.
Privacy-Enhanced Methods for Comparing Compressed DNA Sequences
Venue: arXiv cs.CR 2011
Year: 2011

In this paper, we study methods for improving the efficiency and privacy of compressed DNA sequence comparison computations, under various querying scenarios. For instance, one scenario involves a querier, Bob, who wants to test if his DNA string, $Q$, is close to a DNA string, $Y$, owned by a data owner, Alice, but Bob does not want to reveal $Q$ to Alice and Alice is willing to reveal $Y$ to Bob \emph{only if} it is close to $Q$. We describe a privacy-enhanced method for comparing two compressed DNA sequences, which can be used to achieve the goals of such a scenario. Our method involves a reduction to set differencing, and we describe a privacy-enhanced protocol for set differencing that achieves absolute privacy for Bob (in the information theoretic sense), and a quantifiable degree of privacy protection for Alice. One of the important features of our protocols, which makes them ideally suited to privacy-enhanced DNA sequence comparison problems, is that the communication complexity of our solutions is proportional to a threshold that bounds the cardinality of the set differences that are of interest, rather than the cardinality of the sets involved (which correlates to the length of the DNA sequences). Moreover, in our protocols, the querier, Bob, can easily compute the set difference only if its cardinality is close to or below a specified threshold.
3-Phase Recognition Approach to Pseudo 3D Building Generation from 2D Floor Plan
Venue: arXiv cs.GR 2011
Year: 2011

Nowadays three dimension (3D) architectural visualisation has become a powerful tool in the conceptualisation, design and presentation of architectural products in the construction industry, providing realistic interaction and walkthrough on engineering products. Traditional ways of implementing 3D models involves the use of specialised 3D authoring tools along with skilled 3D designers with blueprints of the model and this is a slow and laborious process. The aim of this paper is to automate this process by simply analyzing the blueprint document and generating the 3D scene automatically. For this purpose we have devised a 3-Phase recognition approach to pseudo 3D building generation from 2D floor plan and developed a software accordingly. Our 3-phased 3D building system has been implemented using C, C++ and OpenCV library [24] for the Image Processing module; The Save Module generated an XML file for storing the processed floor plan objects attributes; while the Irrlitch [14] game engine was used to implement the Interactive 3D module. Though still at its infancy, our proposed system gave commendable results. We tested our system on 6 floor plans with complexities ranging from low to high and the results seems to be very promising with an average processing time of around 3s and a 3D generation in 4s. In addition the system provides an interactive walk-though and allows users to modify components.
Decentralized List Scheduling
Venue: arXiv cs.DC 2011
Year: 2011

Classical list scheduling is a very popular and efficient technique for scheduling jobs in parallel and distributed platforms. It is inherently centralized. However, with the increasing number of processors, the cost for managing a single centralized list becomes too prohibitive. A suitable approach to reduce the contention is to distribute the list among the computational units: each processor has only a local view of the work to execute. Thus, the scheduler is no longer greedy and standard performance guarantees are lost. The objective of this work is to study the extra cost that must be paid when the list is distributed among the computational units. We first present a general methodology for computing the expected makespan based on the analysis of an adequate potential function which represents the load unbalance between the local lists. We obtain an equation on the evolution of the potential by computing its expected decrease in one step of the schedule. Our main theorem shows how to solve such equations to bound the makespan. Then, we apply this method to several scheduling problems, namely, for unit independent tasks, for weighted independent tasks and for tasks with precendence constraints. More precisely, we prove that the time for scheduling a global workload W composed of independent unit tasks on m processors is equal to W/m plus an additional term proportional to log_2 W. We provide a lower bound which shows that this is optimal up to a constant. This result is extended to the case of weighted independent tasks. In the last setting, precedence task graphs, our analysis leads to an improvement on the bound of Arora et al. We finally provide some experiments using a simulator. The distribution of the makespan is shown to fit existing probability laws. The additive term is shown by simulation to be around 3 \log_2 W confirming the tightness of our analysis.
MAC Centered Cooperation - Synergistic Design of Network Coding, Multi-Packet Reception, and Improved Fairness to Increase Network Throughput
Venue: arXiv cs.NI 2011
Year: 2011

We design a cross-layer approach to aid in develop- ing a cooperative solution using multi-packet reception (MPR), network coding (NC), and medium access (MAC). We construct a model for the behavior of the IEEE 802.11 MAC protocol and apply it to key small canonical topology components and their larger counterparts. The results obtained from this model match the available experimental results with fidelity. Using this model, we show that fairness allocation by the IEEE 802.11 MAC can significantly impede performance; hence, we devise a new MAC that not only substantially improves throughput, but provides fairness to flows of information rather than to nodes. We show that cooperation between NC, MPR, and our new MAC achieves super-additive gains of up to 6.3 times that of routing with the standard IEEE 802.11 MAC. Furthermore, we extend the model to analyze our MAC's asymptotic and throughput behaviors as the number of nodes increases or the MPR capability is limited to only a single node. Finally, we show that although network performance is reduced under substantial asymmetry or limited implementation of MPR to a central node, there are some important practical cases, even under these conditions, where MPR, NC, and their combination provide significant gains.