We propose a method of decision rule generation in object-oriented rough set models proposed by Kudo and Murai. the object-oriented rough set model is an extension of the "traditional" rough set theory by in...
详细信息
ISBN:
(纸本)3540476938
We propose a method of decision rule generation in object-oriented rough set models proposed by Kudo and Murai. the object-oriented rough set model is an extension of the "traditional" rough set theory by introducing object-oriented paradigm used in computerscience. the object-oriented rough set model treats objects as instances of some classes, and illustrate structural hierarchies among objects based on is-a relationship and has-a relationship. In this paper, we introduce decision rules in the object-oriented rough set model, and revise discernibility matrices proposed by Skowron and Rauser to generate decision rules in the object-oriented rough set model.
We show that the interactive knapsack heuristic optimization problem is APX-hard. Moreover, we discuss the relationship between the interactive knapsack heuristic optimization problem and some other knapsack problems....
详细信息
the traditional client/server architecture for web service delivery fails to naturally scale. this results in growing costs to the service provider for powerful hardware or extensive use of Content Distribution Networ...
详细信息
the proceedings contain 22 papers. the topics discussed include: equivalence-checking with infinite-state systems: techniques and results;database support for multisource multiresolution scientific data;semantic annot...
ISBN:
(纸本)354000145X
the proceedings contain 22 papers. the topics discussed include: equivalence-checking with infinite-state systems: techniques and results;database support for multisource multiresolution scientific data;semantic annotation and indexing of news and sports videos;multimedia presentations databases;interactive indexing and retrieval of multimedia content;a model-based approach to semantic-based retrieval of visual information;Hungarian speech synthesis using a phase exact HNM approach;modelling resource transitions in constraint-based scheduling;a specification framework for real-time scheduling;string transformation for N-dimensional image compression;validation and decomposition of partially occluded images;solving conflicts of agent knowledge states in multiagent systems;specification and verification of secure business transaction systems;and the reconstruction of some 3D convex polyominoes from orthogonal projections.
To specify the set of tractable (practically solvable) computing problems is one of the few main research tasks of theoretical computerscience. Because of this the investigation of the possibility or the impossibilit...
详细信息
ISBN:
(纸本)354066694X
To specify the set of tractable (practically solvable) computing problems is one of the few main research tasks of theoretical computerscience. Because of this the investigation of the possibility or the impossibility to efficiently compute approximations of hard optimization problems becomes one of the central and most fruitful areas of recent algorithm and complexity theory. the current point of view is that optimization problems are considered to be tractable if there exist polynomial-time randomized approximation algorithms that solve them with a reasonable approximation ratio. If a optimization problem does not admit such a polynomial-time algorithm, then the problem is considered to be not tractable. the main goal of this paper is to relativize this specification of tractability. the main reason for this attempt is that we consider the requirement for the tractability to be strong because of the definition of the complexity as the "worst-case" complexity. this definition is also related to the approximation ratio of approximation algorithms and then an optimization problem is considered to be intractable because some subset of problem instances is hard. But in the practice we often have the situation that the hard problem instances do not occur. the general idea of this paper is to try to partition the set of all problem instances of a hard optimization problem into a (possibly infinite) spectrum of subclasses according to their polynomial-time approximability. Searching for a method enabling such a fine problem analysis (classification of problem instances) we introduce the concept of stability of approximation. To show that the application of this concept may lead to a "fine" characterisation of the hardness of particular problem instances we consider the traveling salesperson problem and the knapsack problem.
We survey recent results from different areas, studying how introducing per-instance a-priori information affects the solvability and complexity of given tasks. We mainly focus on distributed, and online computation, ...
详细信息
ISBN:
(纸本)9783319042978;9783319042985
We survey recent results from different areas, studying how introducing per-instance a-priori information affects the solvability and complexity of given tasks. We mainly focus on distributed, and online computation, where some sort of hidden information plays a crucial role: in the distributed computing, typically nodes have no or only limited information about the global state of the network;in online problems, the algorithm lacks the information about the future input. the traditional approach in both areas is to study how the properties of the problem change if some partial information is available (e. g., nodes of a distributed system have sense of direction, the online algorithm has the promise that the input requests come in some specified order etc.). Recently, attempts have been made to study this information from a quantitative point of view: there is an oracle that delivers (per-instance) best-case information of a limited size, and the relationship between the amount of the additional information, and the benefit it can provide to the algorithm, is investigated. We show cases where this relationship has a form of a trade-off, and others where one or more thresholds can be identified.
this book constitutes the refereed proceedings of the 35thconference on currenttrends in theory and practice of computerscience, SOFSEM 2009, held in pindleruv Mln, Czech Republic, in January 2009. the 49 revised f...
ISBN:
(数字)9783540958918
ISBN:
(纸本)9783540958901
this book constitutes the refereed proceedings of the 35thconference on currenttrends in theory and practice of computerscience, SOFSEM 2009, held in pindleruv Mln, Czech Republic, in January 2009. the 49 revised full papers, presented together with 9 invited contributions, were carefully reviewed and selected from 132 submissions. SOFSEM 2009 was organized around the following four tracks: Foundations of computerscience; theory and practice of Software Services; Game theoretic Aspects of E-commerce; and Techniques and Tools for Formal Verification.
Although practised as an art and science for ages, cryptography had to wait until the mid-twentieth century before Claude Shannon gave it a strong mathematical foundation. However, Shannon’s approach was rooted is hi...
详细信息
In the working environment of distribution hub in practice, we have difficulty in dispatching transportation vehicles because of the characteristics of the uncertain environment information, e.g. goods quantity, road/...
详细信息
In the working environment of distribution hub in practice, we have difficulty in dispatching transportation vehicles because of the characteristics of the uncertain environment information, e.g. goods quantity, road/traffic condition, and weather variation. Most of all, we must consider different transfer demands of goods that have timing constrain. In order to overcome the difficulty. this paper develops a unified-vehicle dispatch system for a multi- service distribution hub currently operated for a leading logistics company in Taiwan. the fuzzy theory is applied to facilitate the description of the uncertain transportation environment. this paper also develops a two-phased fuzzy vehicle dispatching algorithm (TP-FVD) that applies the fuzzy optimization technique withthe consideration of various time window constraints to minimize the total dispatching cost. the simulation results show that the unified-vehicle dispatch system outperforms the traditional point-to-point vehicle dispatch method in various transportation and dispatching demands conditions.
the shortest common superstring problem (SCS) is one of the fundamental optimization problems in the. area of data compression and DNA sequencing. the SCS is known to be APX-hard [1]. this paper focuses on the analysi...
详细信息
ISBN:
(纸本)3540413480
the shortest common superstring problem (SCS) is one of the fundamental optimization problems in the. area of data compression and DNA sequencing. the SCS is known to be APX-hard [1]. this paper focuses on the analysis of the approximation ratio of two greedy-based approximation algorithms for it, namely the naive Greedy algorithm and the Group-Merge algorithm. the main results of this paper are: (i) We disprove the claim that the input instances of Jiang and Li (4) prove that the Group-Merge algorithm does not provide any constant approximation for the SCS. We even prove that the Group-Merge algorithm always finds optimal solutions for these instances. (ii) We show that the Greedy algorithm and the Group-Merge algorithm are incomparable according to the approximation ratio. (iii) We attack the main problem whether the Group-Merge algorithm has a constant approximation ratio by showing that this is the case for a slightly modified algorithm denoted as Group-Merge-1 if all strings have approximately the same length and the compression is limited by a constant fraction of the trivial solution.
暂无评论