OpenRaiser/Intern-Atlas huggingface dataset:
Fast Universalization of Investment Strategies with Provably Good Relative Returns
Venue: arXiv cs.CE 2002
Year: 2002

A universalization of a parameterized investment strategy is an online algorithm whose average daily performance approaches that of the strategy operating with the optimal parameters determined offline in hindsight. We present a general framework for universalizing investment strategies and discuss conditions under which investment strategies are universalizable. We present examples of common investment strategies that fit into our framework. The examples include both trading strategies that decide positions in individual stocks, and portfolio strategies that allocate wealth among multiple stocks. This work extends Cover's universal portfolio work. We also discuss the runtime efficiency of universalization algorithms. While a straightforward implementation of our algorithms runs in time exponential in the number of parameters, we show that the efficient universal portfolio computation technique of Kalai and Vempala involving the sampling of log-concave functions can be generalized to other classes of investment strategies.
A Dynamic Approach to Characterizing Termination of General Logic Programs
Venue: arXiv cs.LO 2002
Year: 2002

We present a new characterization of termination of general logic programs. Most existing termination analysis approaches rely on some static information about the structure of the source code of a logic program, such as modes/types, norms/level mappings, models/interargument relations, and the like. We propose a dynamic approach which employs some key dynamic features of an infinite (generalized) SLDNF-derivation, such as repetition of selected subgoals and recursive increase in term size. We also introduce a new formulation of SLDNF-trees, called generalized SLDNF-trees. Generalized SLDNF-trees deal with negative subgoals in the same way as Prolog and exist for any general logic programs.
Monitoring and Debugging Concurrent and Distributed Object-Oriented Systems
Venue: arXiv cs.SE 2002
Year: 2002

A major part of debugging, testing, and analyzing a complex software system is understanding what is happening within the system at run-time. Some developers advocate running within a debugger to better understand the system at this level. Others embed logging statements, even in the form of hard-coded calls to print functions, throughout the code. These techniques are all general, rough forms of what we call system monitoring, and, while they have limited usefulness in simple, sequential systems, they are nearly useless in complex, concurrent ones. We propose a set of new mechanisms, collectively known as a monitoring system, for understanding such complex systems, and we describe an example implementation of such a system, called IDebug, for the Java programming language.
Qualitative Analysis of Correspondence for Experimental Algorithmics
Venue: arXiv cs.AI 2002
Year: 2002

Correspondence identifies relationships among objects via similarities among their components; it is ubiquitous in the analysis of spatial datasets, including images, weather maps, and computational simulations. This paper develops a novel multi-level mechanism for qualitative analysis of correspondence. Operators leverage domain knowledge to establish correspondence, evaluate implications for model selection, and leverage identified weaknesses to focus additional data collection. The utility of the mechanism is demonstrated in two applications from experimental algorithmics -- matrix spectral portrait analysis and graphical assessment of Jordan forms of matrices. Results show that the mechanism efficiently samples computational experiments and successfully uncovers high-level problem properties. It overcomes noise and data sparsity by leveraging domain knowledge to detect mutually reinforcing interpretations of spatial data.
Intelligent Search of Correlated Alarms for GSM Networks with Model-based Constraints
Venue: arXiv cs.NI 2002
Year: 2002

In order to control the process of data mining and focus on the things of interest to us, many kinds of constraints have been added into the algorithms of data mining. However, discovering the correlated alarms in the alarm database needs deep domain constraints. Because the correlated alarms greatly depend on the logical and physical architecture of networks. Thus we use the network model as the constraints of algorithms, including Scope constraint, Inter-correlated constraint and Intra-correlated constraint, in our proposed algorithm called SMC (Search with Model-based Constraints). The experiments show that the SMC algorithm with Inter-correlated or Intra-correlated constraint is about two times faster than the algorithm with no constraints.
On-Line Paging against Adversarially Biased Random Inputs
Venue: arXiv cs.DS 2002
Year: 2002

In evaluating an algorithm, worst-case analysis can be overly pessimistic. Average-case analysis can be overly optimistic. An intermediate approach is to show that an algorithm does well on a broad class of input distributions. Koutsoupias and Papadimitriou recently analyzed the least-recently-used (LRU) paging strategy in this manner, analyzing its performance on an input sequence generated by a so-called diffuse adversary -- one that must choose each request probabilitistically so that no page is chosen with probability more than some fixed epsilon>0. They showed that LRU achieves the optimal competitive ratio (for deterministic on-line algorithms), but they didn't determine the actual ratio. In this paper we estimate the optimal ratios within roughly a factor of two for both deterministic strategies (e.g. least-recently-used and first-in-first-out) and randomized strategies. Around the threshold epsilon ~ 1/k (where k is the cache size), the optimal ratios are both Theta(ln k). Below the threshold the ratios tend rapidly to O(1). Above the threshold the ratio is unchanged for randomized strategies but tends rapidly to Theta(k) for deterministic ones. We also give an alternate proof of the optimality of LRU.
Polynomial-Time Approximation Scheme for Data Broadcast
Venue: arXiv cs.DS 2002
Year: 2002

The data broadcast problem is to find a schedule for broadcasting a given set of messages over multiple channels. The goal is to minimize the cost of the broadcast plus the expected response time to clients who periodically and probabilistically tune in to wait for particular messages. The problem models disseminating data to clients in asymmetric communication environments, where there is a much larger capacity from the information source to the clients than in the reverse direction. Examples include satellites, cable TV, internet broadcast, and mobile phones. Such environments favor the ``push-based'' model where the server broadcasts (pushes) its information on the communication medium and multiple clients simultaneously retrieve the specific information of individual interest. This paper presents the first polynomial-time approximation scheme (PTAS) for data broadcast with O(1) channels and when each message has arbitrary probability, unit length and bounded cost. The best previous polynomial-time approximation algorithm for this case has a performance ratio of 9/8.
Computing stable models: worst-case performance estimates
Venue: arXiv cs.LO 2002
Year: 2002

We study algorithms for computing stable models of propositional logic programs and derive estimates on their worst-case performance that are asymptotically better than the trivial bound of O(m 2^n), where m is the size of an input program and n is the number of its atoms. For instance, for programs, whose clauses consist of at most two literals (counting the head) we design an algorithm to compute stable models that works in time O(m\times 1.44225^n). We present similar results for several broader classes of programs, as well.
An Overview of a Grid Architecture for Scientific Computing
Venue: arXiv cs.DC 2002
Year: 2002

This document gives an overview of a Grid testbed architecture proposal for the NorduGrid project. The aim of the project is to establish an inter-Nordic testbed facility for implementation of wide area computing and data handling. The architecture is supposed to define a Grid system suitable for solving data intensive problems at the Large Hadron Collider at CERN. We present the various architecture components needed for such a system. After that we go on to give a description of the dynamics by showing the task flow.
Sotto Voce: Exploring the Interplay of Conversation and Mobile Audio Spaces
Venue: arXiv cs.HC 2002
Year: 2002

In addition to providing information to individual visitors, electronic guidebooks have the potential to facilitate social interaction between visitors and their companions. However, many systems impede visitor interaction. By contrast, our electronic guidebook, Sotto Voce, has social interaction as a primary design goal. The system enables visitors to share audio information - specifically, they can hear each other's guidebook activity using a technologically mediated audio eavesdropping mechanism. We conducted a study of visitors using Sotto Voce while touring a historic house. The results indicate that visitors are able to use the system effectively, both as a conversational resource and as an information appliance. More surprisingly, our results suggest that the technologically mediated audio often cohered the visitors' conversation and activity to a far greater degree than audio delivered through the open air.
Optimizing Queries Using a Meta-level Database
Venue: arXiv cs.DB 2002
Year: 2002

Graph simulation (using graph schemata or data guides) has been successfully proposed as a technique for adding structure to semistructured data. Design patterns for description (such as meta-classes and homomorphisms between schema layers), which are prominent in the object-oriented programming community, constitute a generalization of this graph simulation approach. In this paper, we show description applicable to a wide range of data models that have some notion of object (-identity), and propose to turn it into a data model primitive much like, say, inheritance. We argue that such an extension fills a practical need in contemporary data management. Then, we present algebraic techniques for query optimization (using the notions of described and description queries). Finally, in the semistructured setting, we discuss the pruning of regular path queries (with nested conditions) using description meta-data. In this context, our notion of meta-data extends graph schemata and data guides by meta-level values, allowing to boost query performance and to reduce the redundancy of data.
Effectiveness of Preference Elicitation in Combinatorial Auctions
Venue: arXiv cs.GT 2002
Year: 2002

Combinatorial auctions where agents can bid on bundles of items are desirable because they allow the agents to express complementarity and substitutability between the items. However, expressing one's preferences can require bidding on all bundles. Selective incremental preference elicitation by the auctioneer was recently proposed to address this problem (Conen & Sandholm 2001), but the idea was not evaluated. In this paper we show, experimentally and theoretically, that automated elicitation provides a drastic benefit. In all of the elicitation schemes under study, as the number of items for sale increases, the amount of information elicited is a vanishing fraction of the information collected in traditional ``direct revelation mechanisms'' where bidders reveal all their valuation information. Most of the elicitation schemes also maintain the benefit as the number of agents increases. We develop more effective elicitation policies for existing query types. We also present a new query type that takes the incremental nature of elicitation to a new level by allowing agents to give approximate answers that are refined only on an as-needed basis. In the process, we present methods for evaluating different types of elicitation policies.
Assessing System Agreement and Instance Difficulty in the Lexical Sample Tasks of Senseval-2
Venue: arXiv cs.CL 2002
Year: 2002

This paper presents a comparative evaluation among the systems that participated in the Spanish and English lexical sample tasks of Senseval-2. The focus is on pairwise comparisons among systems to assess the degree to which they agree, and on measuring the difficulty of the test instances included in these tasks.
Machine Learning with Lexical Features: The Duluth Approach to Senseval-2
Venue: arXiv cs.CL 2002
Year: 2002

This paper describes the sixteen Duluth entries in the Senseval-2 comparative exercise among word sense disambiguation systems. There were eight pairs of Duluth systems entered in the Spanish and English lexical sample tasks. These are all based on standard machine learning algorithms that induce classifiers from sense-tagged training text where the context in which ambiguous words occur are represented by simple lexical features. These are highly portable, robust methods that can serve as a foundation for more tailored approaches.
Complexity Results about Nash Equilibria
Venue: arXiv cs.GT 2002
Year: 2002

Noncooperative game theory provides a normative framework for analyzing strategic interactions. However, for the toolbox to be operational, the solutions it defines will have to be computed. In this paper, we provide a single reduction that 1) demonstrates NP-hardness of determining whether Nash equilibria with certain natural properties exist, and 2) demonstrates the #P-hardness of counting Nash equilibria (or connected sets of Nash equilibria). We also show that 3) determining whether a pure-strategy Bayes-Nash equilibrium exists is NP-hard, and that 4) determining whether a pure-strategy Nash equilibrium exists in a stochastic (Markov) game is PSPACE-hard even if the game is invisible (this remains NP-hard if the game is finite). All of our hardness results hold even if there are only two players and the game is symmetric. Keywords: Nash equilibrium; game theory; computational complexity; noncooperative game theory; normal form game; stochastic game; Markov game; Bayes-Nash equilibrium; multiagent systems.
A Spectrum of Applications of Automated Reasoning
Venue: arXiv cs.AI 2002
Year: 2002

The likelihood of an automated reasoning program being of substantial assistance for a wide spectrum of applications rests with the nature of the options and parameters it offers on which to base needed strategies and methodologies. This article focuses on such a spectrum, featuring W. McCune's program OTTER, discussing widely varied successes in answering open questions, and touching on some of the strategies and methodologies that played a key role. The applications include finding a first proof, discovering single axioms, locating improved axiom systems, and simplifying existing proofs. The last application is directly pertinent to the recently found (by R. Thiele) Hilbert's twenty-fourth problem--which is extremely amenable to attack with the appropriate automated reasoning program--a problem concerned with proof simplification. The methodologies include those for seeking shorter proofs and for finding proofs that avoid unwanted lemmas or classes of term, a specific option for seeking proofs with smaller equational or formula complexity, and a different option to address the variable richness of a proof. The type of proof one obtains with the use of OTTER is Hilbert-style axiomatic, including details that permit one sometimes to gain new insights. We include questions still open and challenges that merit consideration.
Mining All Non-Derivable Frequent Itemsets
Venue: arXiv cs.DB 2002
Year: 2002

Recent studies on frequent itemset mining algorithms resulted in significant performance improvements. However, if the minimal support threshold is set too low, or the data is highly correlated, the number of frequent itemsets itself can be prohibitively large. To overcome this problem, recently several proposals have been made to construct a concise representation of the frequent itemsets, instead of mining all frequent itemsets. The main goal of this paper is to identify redundancies in the set of all frequent itemsets and to exploit these redundancies in order to reduce the result of a mining operation. We present deduction rules to derive tight bounds on the support of candidate itemsets. We show how the deduction rules allow for constructing a minimal representation for all frequent itemsets. We also present connections between our proposal and recent proposals for concise representations and we give the results of experiments on real-life datasets that show the effectiveness of the deduction rules. In fact, the experiments even show that in many cases, first mining the concise representation, and then creating the frequent itemsets from this representation outperforms existing frequent set mining algorithms.
Characterization of Strongly Equivalent Logic Programs in Intermediate Logics
Venue: arXiv cs.LO 2002
Year: 2002

The non-classical, nonmonotonic inference relation associated with the answer set semantics for logic programs gives rise to a relationship of 'strong equivalence' between logical programs that can be verified in 3-valued Goedel logic, G3, the strongest non-classical intermediate propositional logic (Lifschitz, Pearce and Valverde, 2001). In this paper we will show that KC (the logic obtained by adding axiom ~A v ~~A to intuitionistic logic), is the weakest intermediate logic for which strongly equivalent logic programs, in a language allowing negations, are logically equivalent.
High-order fundamental and general solutions of convection-diffusion equation and their applications with boundary particle method
Venue: arXiv cs.CE 2002
Year: 2002

In this study, we presented the high-order fundamental solutions and general solutions of convection-diffusion equation. To demonstrate their efficacy, we applied the high-order general solutions to the boundary particle method (BPM) for the solution of some inhomogeneous convection-diffusion problems, where the BPM is a new truly boundary-only meshfree collocation method based on multiple reciprocity principle. For the sake of completeness, the BPM is also briefly described here.
On Simultaneous Graph Embedding
Venue: arXiv cs.CG 2002
Year: 2002

We consider the problem of simultaneous embedding of planar graphs. There are two variants of this problem, one in which the mapping between the vertices of the two graphs is given and another where the mapping is not given. In particular, we show that without mapping, any number of outerplanar graphs can be embedded simultaneously on an $O(n)\times O(n)$ grid, and an outerplanar and general planar graph can be embedded simultaneously on an $O(n^2)\times O(n^3)$ grid. If the mapping is given, we show how to embed two paths on an $n \times n$ grid, a caterpillar and a path on an $n \times 2n$ grid, or two caterpillar graphs on an $O(n^2)\times O(n^3)$ grid. We also show that 5 paths, or 3 caterpillars, or two general planar graphs cannot be simultaneously embedded given the mapping.
Sierpinski Gaskets for Logic Functions Representation
Venue: arXiv cs.LO 2002
Year: 2002

This paper introduces a new approach to represent logic functions in the form of Sierpinski Gaskets. The structure of the gasket allows to manipulate with the corresponding logic expression using recursive essence of fractals. Thus, the Sierpinski gasket's pattern has myriad useful properties which can enhance practical features of other graphic representations like decision diagrams. We have covered possible applications of Sierpinski gaskets in logic design and justified our assumptions in logic function minimization (both Boolean and multiple-valued cases). The experimental results on benchmarks with advances in the novel structure are considered as well.
Behaviour-based Knowledge Systems: An Epigenetic Path from Behaviour to Knowledge
Venue: arXiv cs.AI 2002
Year: 2002

In this paper we expose the theoretical background underlying our current research. This consists in the development of behaviour-based knowledge systems, for closing the gaps between behaviour-based and knowledge-based systems, and also between the understandings of the phenomena they model. We expose the requirements and stages for developing behaviour-based knowledge systems and discuss their limits. We believe that these are necessary conditions for the development of higher order cognitive capacities, in artificial and natural cognitive systems.
Algorithms for Media
Venue: arXiv cs.DS 2002
Year: 2002

Falmagne recently introduced the concept of a medium, a combinatorial object encompassing hyperplane arrangements, topological orderings, acyclic orientations, and many other familiar structures. We find efficient solutions for several algorithmic problems on media: finding short reset sequences, shortest paths, testing whether a medium has a closed orientation, and listing the states of a medium given a black-box description.
National Infrastructure Contingencies: Survey of Wireless Technology Support
Venue: arXiv cs.DC 2002
Year: 2002

In modern society, the flow of information has become the lifeblood of commerce and social interaction. This movement of data supports most aspects of the United States economy in particular, as well as, serving as the vehicle upon which governmental agencies react to social conditions. In addition, it is understood that the continuance of efficient and reliable data communications during times of national or regional disaster remains a priority in the United States. The coordination of emergency response and area revitalization / rehabilitation efforts between local, state, and federal emergency response is increasingly necessary as agencies strive to work more seamlessly between the affected organizations. Additionally, international support is often made available to react to such adverse conditions as wildfire suppression scenarios and therefore require the efficient management of workforce and associated logistics support. It is through the examination of the issues related to un-tethered data transmission during infrastructure contingencies that responders may best tailor a unified approach to the rapid recovery after disasters occur.
Towards Efficient Calculation of Information Measures for Reordering of Binary Decision Diagrams
Venue: arXiv cs.OH 2002
Year: 2002

This paper introduces new technique for efficient calculation of different Shannon information measures which operates Binary Decision Diagrams (BDDs). We offer an algorithm of BDD reordering which demonstrates the improvement of the obtaining outcomes over the existing reordering approaches. The technique and the reordering algorithm have been implemented, and the results on circuits' benchmarks are analyzed. We point out that the results are quite promising, the algorithm is very fast, and it is easy to implement. Finally, we show that our approach to BDD reordering can yield to reduction in the power dissipation for the circuits derived from BDDs.
Abduction, ASP and Open Logic Programs
Venue: arXiv cs.AI 2002
Year: 2002

Open logic programs and open entailment have been recently proposed as an abstract framework for the verification of incomplete specifications based upon normal logic programs and the stable model semantics. There are obvious analogies between open predicates and abducible predicates. However, despite superficial similarities, there are features of open programs that have no immediate counterpart in the framework of abduction and viceversa. Similarly, open programs cannot be immediately simulated with answer set programming (ASP). In this paper we start a thorough investigation of the relationships between open inference, abduction and ASP. We shall prove that open programs generalize the other two frameworks. The generalized framework suggests interesting extensions of abduction under the generalized stable model semantics. In some cases, we will be able to reduce open inference to abduction and ASP, thereby estimating its computational complexity. At the same time, the aforementioned reduction opens the way to new applications of abduction and ASP.