首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 140 毫秒
1.
Determining the “weakest” failure detectors is a central topic in solving many agreement problems such as Consensus, Non-Blocking Atomic Commit and Election in asynchronous distributed systems. So far, this has been studied extensively for several such fundamental problems. It is stated that Perfect Failure Detector P is the weakest failure detector to solve the Election problem with any number of faulty processes. In this paper, we introduce Modal failure detector M and show that to solve Election, M is the weakest failure detector to solve election when the number of faulty processes is less than ⌈n/2⌉. We also show that it is strictly weaker than P.
Sung Hoon ParkEmail:
  相似文献   

2.
We study the problem of matching applicants to jobs under one-sided preferences; that is, each applicant ranks a non-empty subset of jobs under an order of preference, possibly involving ties. A matching M is said to be more popular than T if the applicants that prefer M to T outnumber those that prefer T to M. A matching is said to be popular if there is no matching more popular than it. Equivalently, a matching M is popular if ?(M,T)≥?(T,M) for all matchings T, where ?(X,Y) is the number of applicants that prefer X to Y.Previously studied solution concepts based on the popularity criterion are either not guaranteed to exist for every instance (e.g., popular matchings) or are NP-hard to compute (e.g., least unpopular matchings). This paper addresses this issue by considering mixed matchings. A mixed matching is simply a probability distribution over matchings in the input graph. The function ? that compares two matchings generalizes in a natural manner to mixed matchings by taking expectation. A mixed matching P is popular if ?(P,Q)≥?(Q,P) for all mixed matchings Q.We show that popular mixed matchings always exist and we design polynomial time algorithms for finding them. Then we study their efficiency and give tight bounds on the price of anarchy and price of stability of the popular matching problem.  相似文献   

3.
Given two compact convex sets P and Q in the plane, we consider the problem of finding a placement ? P of P that minimizes the convex hull of ? PQ. We study eight versions of the problem: we consider minimizing either the area or the perimeter of the convex hull; we either allow ? P and Q to intersect or we restrict their interiors to remain disjoint; and we either allow reorienting P or require its orientation to be fixed. In the case without reorientations, we achieve exact near-linear time algorithms for all versions of the problem. In the case with reorientations, we compute a (1+ε)-approximation in time?O(ε ?1/2log?n+ε ?3/2log? a (1/ε)) if the two sets are convex polygons with n vertices in total, where a∈{0,1,2} depending on the version of the problem.  相似文献   

4.
A classical measure of similarity between strings is the length of the longest common subsequence (LCS) between the two given strings. The search for efficient algorithms for finding the LCS has been going on for more than three decades. To date, all known algorithms may take quadratic time (shaved by logarithmic factors) to find large LCS. In this paper, the problem of approximating LCS is studied, while focusing on the hard inputs for this problem, namely, approximating LCS of near-linear size in strings over a relatively large alphabet (of size at least n? for some constant ?>0, where n is the length of the string). We show that, any given string over a relatively large alphabet can be embedded into a locally non-repetitive string. This embedding has a negligible additive distortion for strings that are not too dissimilar in terms of the edit distance. We also show that LCS can be efficiently approximated in locally-non-repetitive strings. Our new method (the embedding together with the approximation algorithm) gives a strictly sub-quadratic time algorithm (i.e., of complexity O(n2-?) for some constant ?) which can find common subsequences of linear (and near linear) size that cannot be detected efficiently by the existing tools.  相似文献   

5.
The recently introduced interconnection network, the Möbius cube, is an important variant of the hypercube. This network has several attractive properties compared with the hypercube. In this paper, we show that the n-dimensional Möbius cube Mn is Hamilton-connected when n?3. Then, by using the Hamilton-connectivity of Mn, we also show that any cycle of length l (4?l?2n) can be embedded into Mn with dilation 1 (n?2). It is a fact that the n-dimensional hypercube Qn does not possess these two properties.  相似文献   

6.
It has been shown that for every perfect matching M of the d-dimensional n-vertex hypercube, d?2, n=d2, there exists a second perfect matching M such that the union of M and M forms a Hamiltonian circuit of the d-dimensional hypercube. We prove a generalization of a special case of this result when there are two dimensions that do not get used by M. It is known that the number Md of perfect matchings of the d-dimensional hypercube satisfies and, in particular, (2d/n)n/2(n/2)!?Md?(d!)n/(2d). It has also been shown that the number Hd of Hamiltonian circuits of the hypercube satisfies 1?limd→∞(logHd)/(logMd)?2. We finally strengthen this result to a nearly tight bound ((dlog2/(eloglogd))(1−on(1)))?Hd?(d!)n/(2d)((d−1)!)n/(2(d−1))/2 proving that limd→∞(logHd)/(logMd)=2. This means that the bound Hd?Md is improved to a nearly tight , so the number of Hamiltonian circuits in the hypercube is nearly quadratic in the number of perfect matchings. The proofs are based on a result for graphs that are the Cartesian product of squares and arbitrary bipartite regular graphs that have a Hamiltonian cycle. We also study a labeling scheme related to matchings.  相似文献   

7.
We present here a general framework to design algorithms that compute H-join. For a given bipartite graph H, we say that a graph G admits a H-join decomposition or simply a H-join, if the vertices of G can be partitioned in |H| parts connected as in H. This graph H is a kind of pattern, that we want to discover in G. This framework allows us to present fastest known algorithms for the computation of P 4-join (aka N-join), P 5-join (aka W-join), C 6-join (aka 6-join). We also generalize this method to find a homogeneous pair (also known as 2-module), a pair {M 1,M 2} such that for every vertex x?(M 1M 2) and i∈{1,2}, x is either adjacent to all vertices in M i or to none of them. First used in the context of perfect graphs (Chvátal and Sbihi in Graphs Comb. 3:127–139, 1987), it is a generalization of splits (a.k.a. 1-joins) and of modules. The algorithmics to compute them appears quite involved. In this paper, we describe an O(mn 2)-time algorithm computing all maximal homogeneous pairs of a graph, which not only improves a previous bound of O(mn 3) for finding only one pair (Everett et al. in Discrete Appl. Math. 72:209–218, 1997), but also uses a nice structural property of homogenous pairs, allowing to compute a canonical decomposition tree for sesquiprime graphs (i.e., graphs G having no module and such that for every vertex vG, G?v also has no module).  相似文献   

8.
Reliable dissipative control for stochastic impulsive systems   总被引:2,自引:0,他引:2  
This paper deals with the problem of reliable dissipative control for a class of stochastic hybrid systems. The systems under study are subject to Markovian jump, parameter uncertainties, possible actuator failure and impulsive effects, which are often encountered in practice and the sources of instability. Our attention is focused on the design of linear state feedback controllers and impulsive controllers such that, for all admissible uncertainties as well as actuator failure occurring among a prespecified subset of actuators, the stochastic hybrid system is stochastically robustly stable and strictly (Q,S,R)-dissipative. The sufficient conditions are obtained by using linear matrix inequality (LMI) techniques. The main results of this paper extend the existing results on H control.  相似文献   

9.
10.
Virtually all previous classifier models take vectors as inputs, performing directly based on the vector patterns. But it is highly necessary to consider images as matrices in real applications. In this paper, we represent images as second order tensors or matrices. We then propose two novel tensor algorithms, which are referred to as Maximum Margin Multisurface Proximal Support Tensor Machine (M3PSTM) and Maximum Margin Multi-weight Vector Projection Support Tensor Machine (M3VSTM), for classifying and segmenting the images. M3PSTM and M3VSTM operate in tensor space and aim at computing two proximal tensor planes for multisurface learning. To avoid the singularity problem, maximum margin criterion is used for formulating the optimization problems. Thus the proposed tensor classifiers have an analytic form of projection axes and can achieve the maximum margin representations for classification. With tensor representation, the number of estimated parameters is significantly reduced, which makes M3PSTM and M3VSTM more computationally efficient when handing the high-dimensional datasets than applying the vector representations based methods. Thorough image classification and segmentation simulations on the benchmark UCI and real datasets verify the efficiency and validity of our approaches. The visual and numerical results show M3PSTM and M3VSTM deliver comparable or even better performance than some state-of-the-art classification algorithms.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号