In the graph exploration problem, a searcher explores the whole set of nodes of an unknown graph. The searcher is not aware of the existence of an edge until he/she visits one of its endpoints. The searcher's task...
详细信息
ISBN:
(纸本)9783540695066
In the graph exploration problem, a searcher explores the whole set of nodes of an unknown graph. The searcher is not aware of the existence of an edge until he/she visits one of its endpoints. The searcher's task is to visit all the nodes and go back to the starting node by traveling as a short tour as possible. One of the simplest strategies is the nearest neighbor algorithm (NN), which always chooses the unvisited node nearest to the searcher's current position. The weighted NN (WNN) is an extension of NN, which chooses the next node to visit by using the weighted distance. It is known that WNN with weight 3 is 16-competitive for planar graphs. In this paper we prove that NN achieves the competitive ratio of 1.5 for cycles. In addition, we show that the analysis for the competitive ratio of NN is tight by providing an instance for which the bound of 1.5 is attained, and NN is the best for cycles among WNN with all possible weights. Furthermore, we prove that no online algorithm is better than 1.25-competitive.
Prior algorithms known for exactly solving MAX 2-SAT improve upon the trivial upper bound only for very sparse instances. We present new algorithms for exactly solving (in fact, counting) weighted MAX 2-SAT instances....
详细信息
ISBN:
(纸本)9783540695066
Prior algorithms known for exactly solving MAX 2-SAT improve upon the trivial upper bound only for very sparse instances. We present new algorithms for exactly solving (in fact, counting) weighted MAX 2-SAT instances. One of them has a good performance if the underlying constraint graph has a small separator decomposition, another has a slightly improved worst case performance. For a 2-SAT instance F with n variables, the worst case running time is (O) over tilde (2((1-1/((d) over tilde (F)-1))n)), where d(F) is the average degree in the constraint graph defined by F. We use strict a-gadgets introduced by Trevisan, Sorkin, Sudan, and Williamson to get the same upper bounds for problems like MAX 3-SAT and MAX CUT. We also introduce a notion of strict (alpha,beta)-gadget to provide a framework that allows composition of gadgets. This framework allows us to obtain the same upper bounds for MAX k-SAT and MAX k-LIN-2.
The traditional methods to solve the computer games problem are to use various search algorithms on the game search tree and to combine the situation evaluation to generate the corresponding *** paper introduces the i...
详细信息
ISBN:
(纸本)9781665431293
The traditional methods to solve the computer games problem are to use various search algorithms on the game search tree and to combine the situation evaluation to generate the corresponding *** paper introduces the innovative genetic algorithms to the computer games based on the traditional *** the operations for the search tree such as selection,crossover and mutation,the better search tree can be gotten from the better *** the same time,the application of the evaluation functions can produce the best steps in the current *** advanced and modified genetic algorithms are proved to be practical and applicative by experimentations and tests of computer games.
Indexing of factors is a widely used and useful technique in stringology and can be seen as a tool in solving diverse text algorithmic problems. A gapped-factor is a concatenation of a factor of length k, a gap of len...
详细信息
current recommendation systems recommend goods by considering users' historical behaviors, social relations, ratings, and other multi-modals. Although outdated user information presents the trends of a user's ...
详细信息
ISBN:
(纸本)9798400704369
current recommendation systems recommend goods by considering users' historical behaviors, social relations, ratings, and other multi-modals. Although outdated user information presents the trends of a user's interests, no recommendation system can know the users' real-time thoughts indeed. With the development of brain-computer interfaces, it is time to explore next-generation recommenders that show users' real-time thoughts without delay. Electroencephalography (EEG) is a promising method of collecting brain signals because of its convenience and mobility. currently, there is only few research on EEG-based recommendations due to the complexity of learning human brain activity. To explore the utility of EEG-based recommendation, we propose a novel neural network model, QUARK, combining Quantum Cognition theory and Graph Convolutional Networks for accurate item recommendations. Compared with the state-of-the-art recommendation models, the superiority of QUARK is confirmed via extensive experiments.
We deal with the issue of realizability and computability of interactive interface behaviors as described in [1]. We treat the following aspects of interactive behaviors that are represented by relations between commu...
详细信息
The Manipulator is widely used in the current industrial field,and its teaching has a strong theoretical and practical ***,traditional theoretical teaching is often out of touch with practice,resulting in poor teachin...
详细信息
ISBN:
(纸本)9781665431293
The Manipulator is widely used in the current industrial field,and its teaching has a strong theoretical and practical ***,traditional theoretical teaching is often out of touch with practice,resulting in poor teaching *** paper develops a teaching software system for Manipulator simulation control,provides an interactive and visual learning platform for Manipulator principles,and deepens its understanding of teaching content through PBL teaching,reduces the difficulty of course learning,and improves students Interest in learning.
Fault-tolerance has gained renewed importance with the proliferation of high-performance clusters. However, fault-tolerant systems have not yet been widely adopted commercially because they are either hard to deploy, ...
详细信息
ISBN:
(纸本)9783540695066
Fault-tolerance has gained renewed importance with the proliferation of high-performance clusters. However, fault-tolerant systems have not yet been widely adopted commercially because they are either hard to deploy, hard to use, hard to manage, hard to maintain, or hard to justify. We have developed M-3, a practical and easily-deployable multiple fault-tolerant MPI system for Myrinet, to satisfy the demand for a fault-tolerant system. In this paper, we run rigorous tests using real-world applications to validate that M-3 can be used in commercial clusters. We also describe improvements made to our system to solve various problems that arose when deploying it on a commercial cluster. This paper models our system's checkpoint overhead and presents the results of a series of tests using computation- and communication-intensive MPI applications used commercially in various fields of science. The experimental results show that not only does our system conform to various types of running environment well, but that it can also be practically deployed in commercial clusters.
This paper introduces the main algorithms used in Amazon game system,and mainly studies the number of threads in parallel PVS algorithm based on *** view of the low utilization of computer hardware by the current algo...
详细信息
ISBN:
(纸本)9781665431293
This paper introduces the main algorithms used in Amazon game system,and mainly studies the number of threads in parallel PVS algorithm based on *** view of the low utilization of computer hardware by the current algorithm,this paper improves the efficiency of the algorithm by changing the number of parallel algorithm threads to be equal to the number of CPU cores,and draws a conclusion that the multi-core resources can be maximized when the number of parallel algorithm threads is equal to the number of CPU *** paper studies the design of the opening Library of Amazon chess,puts forward the design idea of the opening Library of Amazon chess and the necessity of the opening library system.
An important problem in complexity theory is to find polynomial time constructible hitting sets for Boolean functions in different standard models. This would have consequences for the relationship between determinist...
详细信息
暂无评论