OpenRaiser/Intern-Atlas huggingface dataset:
The Geometry of Scheduling
Venue: arXiv cs.DS 2010
Year: 2010

We consider the following general scheduling problem: The input consists of n jobs, each with an arbitrary release time, size, and a monotone function specifying the cost incurred when the job is completed at a particular time. The objective is to find a preemptive schedule of minimum aggregate cost. This problem formulation is general enough to include many natural scheduling objectives, such as weighted flow, weighted tardiness, and sum of flow squared. Our main result is a randomized polynomial-time algorithm with an approximation ratio O(log log nP), where P is the maximum job size. We also give an O(1) approximation in the special case when all jobs have identical release times. The main idea is to reduce this scheduling problem to a particular geometric set-cover problem which is then solved using the local ratio technique and Varadarajan's quasi-uniform sampling technique. This general algorithmic approach improves the best known approximation ratios by at least an exponential factor (and much more in some cases) for essentially all of the nontrivial common special cases of this problem. Our geometric interpretation of scheduling may be of independent interest.
Managing Clouds in Cloud Platforms
Venue: arXiv cs.DC 2010
Year: 2010

Managing cloud services is a fundamental challenge in todays virtualized environments. These challenges equally face both providers and consumers of cloud services. The issue becomes even more challenging in virtualized environments that support mobile clouds. Cloud computing platforms such as Amazon EC2 provide customers with flexible, on demand resources at low cost. However, they fail to provide seamless infrastructure management and monitoring capabilities that many customers may need. For instance, Amazon EC2 doesn't fully support cloud services automated discovery and it requires a private set of authentication credentials. Salesforce.com, on the other hand, do not provide monitoring access to their underlying systems. Moreover, these systems fail to provide infrastructure monitoring of heterogenous and legacy systems that don't support agents. In this work, we explore how to build a cloud management system that combines heterogeneous management of virtual resources with comprehensive management of physical devices. We propose an initial prototype for automated cloud management and monitoring framework. Our ultimate goal is to develop a framework that have the capability of automatically tracking configuration and relationships while providing full event management, measuring performance and testing thresholds, and measuring availability consistently. Armed with such a framework, operators can make better decisions quickly and more efficiently.
User interfaces and data entry with real time inverse arithmetic coding
Venue: arXiv cs.HC 2010
Year: 2010

This paper introduces real time inverse arithmetic coding and user interfaces based thereupon. The main idea is that information-efficient data entry can be achieved by ensuring that each input's associated display space and ease of selection are at all times related to the input's probability of being selected. As with data entry based on inverse arithmetic coding, the layout initially depends on the probabilities of the possible inputs; however, real time inverse arithmetic coding differs in that the user's actions are interpreted not to navigate this probability distribution but rather to modify it according to a learned update rule, which approximates the conditioning of the probability distribution on the user's actions. Potential applications of real time inverse arithmetic coding include text entry, file browsing, integrated multi-program user interfaces, assistive technologies for users with movement disabilities, and ergonomic input methods.
Stability analysis of the split-step Fourier method on the background of a soliton of the nonlinear Schrödinger equation
Venue: arXiv cs.NA 2010
Year: 2010

We analyze a numerical instability that occurs in the well-known split-step Fourier method on the background of a soliton. This instability is found to be very sensitive to small changes of the parameters of both the numerical grid and the soliton, unlike the instability of most finite-difference schemes. % on the background of a monochromatic wave, considered earlier in the literature. Moreover, the principle of ``frozen coefficients", in which variable coefficients are treated as ``locally constant" for the purpose of stability analysis, is strongly violated for the instability of the split-step method on the soliton background. Our analysis explains all these features. It is enabled by the fact that the period of oscillations of the unstable Fourier modes is much smaller than the width of the soliton.
Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} \log n)$ time
Venue: arXiv cs.DS 2010
Year: 2010

We give an $O(n^{1.5} \log n)$ algorithm that, given a directed planar graph with arc capacities, a set of source nodes and a single sink node, finds a maximum flow from the sources to the sink . This is the first subquadratic-time strongly polynomial algorithm for the problem.
Explicit Proofs and The Flip
Venue: arXiv cs.CC 2010
Year: 2010

This article describes a formal strategy of geometric complexity theory (GCT) to resolve the {\em self referential paradox} in the $P$ vs. $NP$ and related problems. The strategy, called the {\em flip}, is to go for {\em explicit proofs} of these problems. By an explicit proof we mean a proof that constructs proof certificates of hardness that are easy to verify, construct and decode. The main result in this paper says that (1) any proof of the arithmetic implication of the $P$ vs. $NP$ conjecture is close to an explicit proof in the sense that it can be transformed into an explicit proof by proving in addition that arithmetic circuit identity testing can be derandomized in a blackbox fashion, and (2) stronger forms of these arithmetic hardness and derandomization conjectures together imply a polynomial time algorithm for a formidable explicit construction problem in algebraic geometry. This may explain why these conjectures, which look so elementary at the surface, have turned out to be so hard.
Rationalizations of Condorcet-Consistent Rules via Distances of Hamming Type
Venue: arXiv cs.GT 2010
Year: 2010

The main idea of the {\em distance rationalizability} approach to view the voters' preferences as an imperfect approximation to some kind of consensus is deeply rooted in social choice literature. It allows one to define ("rationalize") voting rules via a consensus class of elections and a distance: a candidate is said to be an election winner if she is ranked first in one of the nearest (with respect to the given distance) consensus elections. It is known that many classic voting rules can be distance rationalized. In this paper, we provide new results on distance rationalizability of several Condorcet-consistent voting rules. In particular, we distance rationalize Young's rule and Maximin rule using distances similar to the Hamming distance. We show that the claim that Young's rule can be rationalized by the Condorcet consensus class and the Hamming distance is incorrect; in fact, these consensus class and distance yield a new rule which has not been studied before. We prove that, similarly to Young's rule, this new rule has a computationally hard winner determination problem.
A Complexity View of Markets with Social Influence
Venue: arXiv cs.GT 2010
Year: 2010

In this paper, inspired by the work of Megiddo on the formation of preferences and strategic analysis, we consider an early market model studied in the field of economic theory, in which each trader's utility may be influenced by the bundles of goods obtained by her social neighbors. The goal of this paper is to understand and characterize the impact of social influence on the complexity of computing and approximating market equilibria. We present complexity-theoretic and algorithmic results for approximating market equilibria in this model with focus on two concrete influence models based on the traditional linear utility functions. Recall that an Arrow-Debreu market equilibrium in a conventional exchange market with linear utility functions can be computed in polynomial time by convex programming. Our complexity results show that even a bounded-degree, planar influence network can significantly increase the difficulty of equilibrium computation even in markets with only a constant number of goods. Our algorithmic results suggest that finding an approximate equilibrium in markets with hierarchical influence networks might be easier than that in markets with arbitrary neighborhood structures. By demonstrating a simple market with a constant number of goods and a bounded-degree, planar influence graph whose equilibrium is PPAD-hard to approximate, we also provide a counterexample to a common belief, which we refer to as the myth of a constant number of goods, that equilibria in markets with a constant number of goods are easy to compute or easy to approximate.
Solving the Resource Constrained Project Scheduling Problem with Generalized Precedences by Lazy Clause Generation
Venue: arXiv cs.AI 2010
Year: 2010

The technical report presents a generic exact solution approach for minimizing the project duration of the resource-constrained project scheduling problem with generalized precedences (Rcpsp/max). The approach uses lazy clause generation, i.e., a hybrid of finite domain and Boolean satisfiability solving, in order to apply nogood learning and conflict-driven search on the solution generation. Our experiments show the benefit of lazy clause generation for finding an optimal solutions and proving its optimality in comparison to other state-of-the-art exact and non-exact methods. The method is highly robust: it matched or bettered the best known results on all of the 2340 instances we examined except 3, according to the currently available data on the PSPLib. Of the 631 open instances in this set it closed 573 and improved the bounds of 51 of the remaining 58 instances.
Dichotomy for tree-structured trigraph list homomorphism problems
Venue: arXiv cs.CC 2010
Year: 2010

Trigraph list homomorphism problems (also known as list matrix partition problems) have generated recent interest, partly because there are concrete problems that are not known to be polynomial time solvable or NP-complete. Thus while digraph list homomorphism problems enjoy dichotomy (each problem is NP-complete or polynomial time solvable), such dichotomy is not necessarily expected for trigraph list homomorphism problems. However, in this paper, we identify a large class of trigraphs for which list homomorphism problems do exhibit a dichotomy. They consist of trigraphs with a tree-like structure, and, in particular, include all trigraphs whose underlying graphs are trees. In fact, we show that for these tree-like trigraphs, the trigraph list homomorphism problem is polynomially equivalent to a related digraph list homomorphism problem. We also describe a few examples illustrating that our conditions defining tree-like trigraphs are not unnatural, as relaxing them may lead to harder problems.
Clustering high dimensional data using subspace and projected clustering algorithms
Venue: arXiv cs.DB 2010
Year: 2010

Problem statement: Clustering has a number of techniques that have been developed in statistics, pattern recognition, data mining, and other fields. Subspace clustering enumerates clusters of objects in all subspaces of a dataset. It tends to produce many over lapping clusters. Approach: Subspace clustering and projected clustering are research areas for clustering in high dimensional spaces. In this research we experiment three clustering oriented algorithms, PROCLUS, P3C and STATPC. Results: In general, PROCLUS performs better in terms of time of calculation and produced the least number of un-clustered data while STATPC outperforms PROCLUS and P3C in the accuracy of both cluster points and relevant attributes found. Conclusions/Recommendations: In this study, we analyze in detail the properties of different data clustering method.
Analyzing the performance of probabilistic algorithm in noisy manets
Venue: arXiv cs.NI 2010
Year: 2010

Probabilistic broadcast has been widely used as a flooding optimization mechanism to alleviate the effect of broadcast storm problem (BSP) in mobile ad hoc networks (MANETs). Many research studies have been carried-out to develop and evaluate the performance of this mechanism in an error-free (noiseless) environment. In reality, wireless communication channels in MANETs are an error-prone and suffer from high packet-loss due to presence of noise, i.e., noisy environment. In this paper, we propose a simulation model that can be used to evaluate the performance of probabilistic broadcast for flooding in noisy environment. In the proposed model, the noise-level is represented by a generic name, probability of reception (pc) (0<=pc<=1), where pc=1 for noiseless and <1 for noisy environment. The effect of noise is determined randomly by generating a random number ζ(0<=ζ<1); if ζ<=pc means the packet is successfully delivered to the receiving node, otherwise, unsuccessful delivery occurs. The proposed model is implemented on a MANET simulator, namely, MANSim. The effect of noise on the performance of probabilistic algorithm was investigated in four scenarios. The main conclusions of these scenarios are: the performance of probabilistic algorithm suffers in presence of noise. However, this suffering is less in high density networks, or if the nodes characterized by high retransmission probability or large radio transmission range. The nodes' speed has no or insignificant effect on the performance.
Power-efficient Routing & Increased Yield Approach For WSNs
Venue: arXiv cs.NI 2010
Year: 2010

The sensor nodes in a Wireless Sensor Network are generally constrained with limited power supply. Efficient power management is a must for any sensor network to keep the sensor nodes in the network to be operational for a longer period of time this increasing the lifetime of the sensor network. Hierarchy based routing enables the sensor networks to be deployed in larger areas. In this paper we present a hierarchical cluster based routing protocol which improves the scalability as the data travels from one cluster level to another covering a greater amount of distance and increases the lifetime of the wireless sensor network by distributing the power dissipation load evenly among all the sensor nodes within the network. Also the time delay in case of critical data to be received by the Base Station has also been lowered.
Layered Depth-Normal Images: a Sparse Implicit Representation of Solid Models
Venue: arXiv cs.CG 2010
Year: 2010

This paper presents a novel implicit representation of solid models. With this representation, every solid model can be effectively presented by three layered depth-normal images (LDNIs) that are perpendicular to three orthogonal axes respectively. The layered depth-normal images for a solid model, whose boundary is presented by a polygonal mesh, can be generated efficiently with help of the graphics hardware accelerated sampling. Based on this implicit representation - LDNIs, solid modeling operations including the Boolean operations and the offsetting operation have been developed. A contouring algorithm is also introduced in this paper to generate thin structure and sharp feature preserved mesh surfaces from the layered depth-normal images. Comparisons between LDNIs and other implicit representation of solid models are given at the end of the paper to demonstrate the advantages of LDNIs.
Fast Color Space Transformations Using Minimax Approximations
Venue: arXiv cs.CV 2010
Year: 2010

Color space transformations are frequently used in image processing, graphics, and visualization applications. In many cases, these transformations are complex nonlinear functions, which prohibits their use in time-critical applications. In this paper, we present a new approach called Minimax Approximations for Color-space Transformations (MACT).We demonstrate MACT on three commonly used color space transformations. Extensive experiments on a large and diverse image set and comparisons with well-known multidimensional lookup table interpolation methods show that MACT achieves an excellent balance among four criteria: ease of implementation, memory usage, accuracy, and computational speed.
Brief Announcement: Decentralized Construction of Multicast Trees Embedded into P2P Overlay Networks based on Virtual Geometric Coordinates
Venue: arXiv cs.DC 2010
Year: 2010

In this paper we consider the problem of efficiently constructing in a fully distributed manner multicast trees which are embedded into P2P overlays using virtual geometric node coordinates. We consider two objectives: to minimize the number of messages required for constructing a multicast tree by using the geometric properties of the P2P overlay, and to construct stable multicast trees when the lifetime durations of the peers are known.
Near-Oracle Performance of Greedy Block-Sparse Estimation Techniques from Noisy Measurements
Venue: arXiv cs.IT 2010
Year: 2010

This paper examines the ability of greedy algorithms to estimate a block sparse parameter vector from noisy measurements. In particular, block sparse versions of the orthogonal matching pursuit and thresholding algorithms are analyzed under both adversarial and Gaussian noise models. In the adversarial setting, it is shown that estimation accuracy comes within a constant factor of the noise power. Under Gaussian noise, the Cramer-Rao bound is derived, and it is shown that the greedy techniques come close to this bound at high SNR. The guarantees are numerically compared with the actual performance of block and non-block algorithms, highlighting the advantages of block sparse techniques.
Results of Evolution Supervised by Genetic Algorithms
Venue: arXiv cs.NE 2010
Year: 2010

A series of results of evolution supervised by genetic algorithms with interest to agricultural and horticultural fields are reviewed. New obtained original results from the use of genetic algorithms on structure-activity relationships are reported.
Aggregate AP Throughputs for Long File Transfers in a WLAN controlled by Inhomogeneous TCP Connections
Venue: arXiv cs.NI 2010
Year: 2010

The performance analysis of long file TCP controlled transfers in a WLAN in infrastructure mode is available in the present literature with one of the main assumptions being equal window size for all TCP connections. In this paper, we extend the analysis to TCP-controlled long file uploads and downloads with different TCP windows. Our approach is based on simple Markov chain given in the paper [1], [2] with arbitrary window sizes. We presented simulation results to show the accuracy of the analytical model.
Real-Time Implementation of Order-Statistics Based Directional Filters
Venue: arXiv cs.CV 2010
Year: 2010

Vector filters based on order-statistics have proved successful in removing impulsive noise from color images while preserving edges and fine image details. Among these filters, the ones that involve the cosine distance function (directional filters) have particularly high computational requirements, which limits their use in time critical applications. In this paper, we introduce two methods to speed up these filters. Experiments on a diverse set of color images show that the proposed methods provide substantial computational gains without significant loss of accuracy.
Cost-Effective Implementation of Order-Statistics Based Vector Filters Using Minimax Approximations
Venue: arXiv cs.CV 2010
Year: 2010

Vector operators based on robust order statistics have proved successful in digital multichannel imaging applications, particularly color image filtering and enhancement, in dealing with impulsive noise while preserving edges and fine image details. These operators often have very high computational requirements which limits their use in time-critical applications. This paper introduces techniques to speed up vector filters using the minimax approximation theory. Extensive experiments on a large and diverse set of color images show that proposed approximations achieve an excellent balance among ease of implementation, accuracy, and computational speed.
Automatic Detection of Blue-White Veil and Related Structures in Dermoscopy Images
Venue: arXiv cs.CV 2010
Year: 2010

Dermoscopy is a non-invasive skin imaging technique, which permits visualization of features of pigmented melanocytic neoplasms that are not discernable by examination with the naked eye. One of the most important features for the diagnosis of melanoma in dermoscopy images is the blue-white veil (irregular, structureless areas of confluent blue pigmentation with an overlying white "ground-glass" film). In this article, we present a machine learning approach to the detection of blue-white veil and related structures in dermoscopy images. The method involves contextual pixel classification using a decision tree classifier. The percentage of blue-white areas detected in a lesion combined with a simple shape descriptor yielded a sensitivity of 69.35% and a specificity of 89.97% on a set of 545 dermoscopy images. The sensitivity rises to 78.20% for detection of blue veil in those cases where it is a primary feature for melanoma recognition.
M-Learning: A New Paradigm of Learning Mathematics in Malaysia
Venue: arXiv cs.MM 2010
Year: 2010

M-Learning is a new learning paradigm of the new social structure with mobile and wireless technologies.Smart school is one of the four flagship applications for Multimedia Super Corridor (MSC) under Malaysian government initiative to improve education standard in the country. With the advances of mobile devices technologies, mobile learning could help the government in realizing the initiative. This paper discusses the prospect of implementing mobile learning for primary school students. It indicates significant and challenges and analysis of user perceptions on potential mobile applications through a survey done in primary school context. The authors propose the m-Learning for mathematics by allowing the extension of technology in the traditional classroom in term of learning and teaching.
E2XLRADR (Energy Efficient Cross Layer Routing Algorithm with Dynamic Retransmission for Wireless Sensor Networks)
Venue: arXiv cs.NI 2010
Year: 2010

The main focus of this article is to achieve prolonged network lifetime with overall energy efficiency in wireless sensor networks through controlled utilization of limited energy. Major percentage of energy in wireless sensor network is consumed during routing from source to destination, retransmission of data on packet loss. For improvement, cross layered algorithm is proposed for routing and retransmission scheme. Simulation and results shows that this approach can save the overall energy consumption
Component Specification in the Cactus Framework: The Cactus Configuration Language
Venue: arXiv cs.DC 2010
Year: 2010

Component frameworks are complex systems that rely on many layers of abstraction to function properly. One essential requirement is a consistent means of describing each individual component and how it relates to both other components and the whole framework. As component frameworks are designed to be flexible by nature, the description method should be simultaneously powerful, lead to efficient code, and be easy to use, so that new users can quickly adapt their own code to work with the framework. In this paper, we discuss the Cactus Configuration Language (CCL) which is used to describe components ("thorns'') in the Cactus Framework. The CCL provides a description language for the variables, parameters, functions, scheduling and compilation of a component and includes concepts such as interface and implementation which allow thorns providing the same capabilities to be easily interchanged. We include several application examples which illustrate how community toolkits use the CCL and Cactus and identify needed additions to the language.