Recognizing nondominated coteries and wr-coteries by availability

Coterie is a widely accepted concept for solving the mutual exclusion problem. Nondominated coteries are an important class of coteries which have better performance than dominated coteries. The performance of a coterie is usually measured by availability. Higher availability of a coterie exhibits greater ability to tolerate node or communication link failures. In this paper, we demonstrate a way to recognize nondominated coteries using availability. By evaluating the availability of a coterie instead of using a formal proof, the coterie can be recognized as a nondominated coterie or not. Moreover, with regard to wr-coterie, a concept for solving the replica control problem, we also present a similar result for recognizing nondominated wr-coteries. Finally, we apply our results to some well-known coteries and wr-coteries     

Nondominated coteries on graphs

Let C and D be two distinct coteries under the vertex set V of a graph G=(V,E) that models a distributed system. Coterie C is said to G-dominate D (with respect to G) if the following condition holds: For any connected subgraph H of G that contains a quorum in D (as a subset of its vertex set), there exists a connected subgraph H' of H that contains a quorum in C. A coterie C on a graph G is said to be G-nondominated (G-ND) (with respect to G) if no coterie D(≠C) on G G-dominates C. Intuitively, a G-ND coterie consists of irreducible quorums. This paper characterizes G-ND coteries in graph theoretical terms, and presents a procedure for deciding whether or not a given coterie C is G-ND with respect to a given graph G, based on this characterization. We then improve the time complexity of the decision procedure, provided that the given coterie C is nondominated in the sense of Garcia-Molina and Barbara (1985). Finally, we characterize the class of graphs G on which the majority coterie is G-ND     

Delay optimal coteries on regular symmetric networks

Coteries, introduced by Garcia-Molina and Barbara [Journal for the Association for Computing Machinery, 32 (4) (1985) 841], are an important and effective tool for enforcing mutual exclusion in distributed systems. Communication delay is an important performance measure for a coterie. Fu et al. [IEEE Transactions on Parallel and Distributed Systems, 8 (1) (1997) 59] emphasize that while calculating communication delay, the actual distances between different sites in a network must be taken into account and using this idea, obtain delay optimal coteries for trees, rings and hypercubes. Also, topology of an interconnection network plays an important role in the performance of a distributed system. For certain applications, it is desirable that the degree of each node in the interconnection network is the same. Constant Degree Four Cayley Graphs introduced by Vadapalli and Srimani [IEEE Transactions on Parallel and Distributed Systems 7(2) (1996) 26] provide an ideal topology for such applications. They are regular, have a logarithmic diameter and a node connectivity of four. In this paper, we prove that no coterie on an arbitrary network can have a delay of less than half the diameter of the network and use this result to obtain delay optimal coteries on regular symmetric networks with special reference to constant degree four Cayley interconnection-network.     

Optimal coteries for rings and related networks

Summary Let a distributed system be represented by a graphG=(V, E), whereV is the set of nodes andE is the set of communication links. A coterie is defined as a family,C, of subsets ofV such that any pair of subsets inC has at least one node in common and no subset inC contains any other subset inC. Assuming that each nodev _i V (resp. linke _j E) is operational with probabilityp _i (resp.r _j ), the availability of a coterie is defined as the probability that the operational nodes and links ofG connect all nodes in at least one subset in the coterie. Although it is computationally intractable to find an optimal coterie that maximizes availability for general graphG, we show in this paper that, ifG is a ring, either a singleton coterie or a 3-majority coterie is optimal. Therefore, for any ring, an optimal coterie can be computed in polynomial time. This result is extended to the more general graphs, in which each biconnected component is either an edge or a ring. Toshihide Ibaraki received the B.E., M.E., and Dr. E. degrees from Kyoto University, in 1963, 1965 and 1970, respectively. Since 1969, he has been with the Department of Applied Mathematics and Physics, Kyoto University, except for two and a half years from 1983 to 1985, during which time he was with Department of Computer and Information Sciences, Toyohashi University of Technology. Currently, he is a professor of Kyoto University. He has held a number of visiting appointments with University of Illinois, University of Waterloo, Simon Fraser University, Rutgers University, and others. He is the author of Enumerative Approaches to Combinatorial Optimization, Baltzer AG., a coauthor of Resource Allocation Problems: Algorithmic Approaches, MIT Press, and the author of several books in Japanese, including Algorithms and Data Structures, Shoukohdou. His interest includes algorithms, optimization, computational complexity and their applications. Hiroshi Nagamochi was born in Tokyo, on January 1, 1960. He received the B.A., M.E. and D.E. degrees from Kyoto University, in 1983, in 1985 and in 1988, respectively. From 1988 to 1990, he was with Department of Computer and Information Sciences, Toyohashi University of Technology. Currently, he is an Associate Professor in the Department of Applied Mathematics and Physics at Kyoto University. His research interests include network flow problems and graph connectivity problems. Dr. Nagamochi is a member of the Operations Research Society of Japan and the Information Processing Society. Tsunehiko Kameda received the B.E. and M.E. degrees from the University of Tokyo in 1961 and 1963, respectively, and the Ph.D. degree from Princeton University in 1968. From 1967 to 1980, he was with the Department of Electrical Engineering, University of Waterloo. Since 1981, he has been with Simon Fraser University, Burnaby, British Columbia, Canada, where he is a Professor of Computing Science and is the Director of Computer and Communications Research Laboratory. He has held a number of visiting appointments with Universities of Erlangen-Nürnberg, Bonn, Frankfurt, and Braunschweig, and Gesellschaft für Mathematik und Datenverarbeitung, all in Germany, and also with Kyoto University, Japan. Dr. Kameda is a member of the ACM. He has co-authored three books: Einführung in die Codierungstheorie, Bibliographisches Institut, Distributed Algorithms, Kindai Kagaku-Sha, and A Probabilistic Analysis of Test Response Compaction, IEEE Press. His current research interests include database systems, combinatorial algorithms, distributed computing, ATM networks, and random testing of VLSI circuits.This work was supported in part by Grant-in-Aid from the Ministry of Education, Science and Culture of Japan, and in part by grants from the Natural Sciences and Engineering Research Council of Canada, and the Advanced Systems Institute of British Columbia.     

A geometric approach for constructing coteries and k-coteries

Quorum-based mutual exclusion algorithms are resilient to node and communication line failures. Recently, some mutual exclusion algorithms successfully use logical structures to construct coteries with small quorums sizes. In this paper, we introduce a geometric approach on dealing with the logical structures and present some useful geometric properties for constructing coteries and k-coteries. Based on those geometric properties, a logical structure named three-sided graph is proposed to provide a new scheme for constructing coteries with small quorums: The smallest quorum size is O(√N) in a homogeneous system with N nodes and O(1) in a heterogeneous system. In addition, we also extend the three-sided graph to the O-sided graph for constructing k-coteries     

Obtaining coteries that optimize the availability of replicateddatabases

Techniques for implementing the coterie scheme and for obtaining optimal coteries for a system are presented. Central to the techniques is the notion of an acceptance set, which is an alternative representation of the information contained in a coterie. Using this concept, the coterie scheme can be implemented efficiently, and an optimal coterie for a system can be obtained more directly. The problem of determining an optimal acceptance set is formulated as a sparse zero-one linear programming problem. Hence, the optimization problem can be handled using the very rich class of existing techniques for solving such problems. Experimental results indicate that the optimization approach is feasible for up to eight nodes at least. The ways in which the scheme and the optimization approach can be used for systems that distinguish between read and write operations are indicated     

Nondominated local coteries for resource allocation in grids and clouds

The resource allocation problem is a fundamental problem in Grid and Cloud computing environments. This paper focuses on constructing nondominated (ND) local coteries to solve the problem in a distributed way. Distributed algorithms using coteries usually incur low communication overheads and have high degrees of fault-tolerance, and ND coteries are candidates for the algorithms to achieve the highest degree of fault-tolerance. A new type of coteries, called p-coteries, is defined to aid the construction of local coteries. Theorems about the nondomination of p-coteries are then developed, and an operation, called pairwise-union (p-union), is proposed to help generate ND p-coteries, which in turn can be used to generate ND local coteries for solving the resource allocation problem.     

Multiobjective immune algorithm with nondominated neighbor-based selection

Abstract Nondominated Neighbor Immune Algorithm (NNIA) is proposed for multiobjective optimization by using a novel nondominated neighbor-based selection technique, an immune inspired operator, two heuristic search operators, and elitism. The unique selection technique of NNIA only selects minority isolated nondominated individuals in the population. The selected individuals are then cloned proportionally to their crowding-distance values before heuristic search. By using the nondominated neighbor-based selection and proportional cloning, NNIA pays more attention to the less-crowded regions of the current trade-off front. We compare NNIA with NSGA-II, SPEA2, PESA-II, and MISA in solving five DTLZ problems, five ZDT problems, and three low-dimensional problems. The statistical analysis based on three performance metrics including the coverage of two sets, the convergence metric, and the spacing, show that the unique selection method is effective, and NNIA is an effective algorithm for solving multiobjective optimization problems. The empirical study on NNIA's scalability with respect to the number of objectives shows that the new algorithm scales well along the number of objectives.     

Multiobjective particle swarm optimization with nondominated local and global sets

In multiobjective particle swarm optimization (MOPSO) methods, selecting the local best and the global best for each particle of the population has a great impact on the convergence and diversity of solutions, especially when optimizing problems with high number of objectives. This paper presents an approach using two sets of nondominated solutions. The ability of the proposed approach to detect the true Pareto optimal solutions and capture the shape of the Pareto front is evaluated through experiments on well-known non-trivial multiobjective test problems as well as the real-life electric power dispatch problem. The diversity of the nondominated solutions obtained is demonstrated through different measures. The proposed approach has been assessed through a comparative study with the reported results in the literature.     

Some algorithms for approximating convolutions

This paper presents some algorithms for approximating two-dimensional convolution operators of size n × n, n odd, by a product, or sum of products, of 3 × 3 convolutions. Inaccuracies resulting from the approximation as well as from fixed point computation are discussed and examples are given.     

Properties of an adaptive archiving algorithm for storing nondominated vectors

Search algorithms for Pareto optimization are designed to obtain multiple solutions, each offering a different trade-off of the problem objectives. To make the different solutions available at the end of an algorithm run, procedures are needed for storing them, one by one, as they are found. In a simple case, this may be achieved by placing each point that is found into an "archive" which maintains only nondominated points and discards all others. However, even a set of mutually nondominated points is potentially very large, necessitating a bound on the archive's capacity. But with such a bound in place, it is no longer obvious which points should be maintained and which discarded; we would like the archive to maintain a representative and well-distributed subset of the points generated by the search algorithm, and also that this set converges. To achieve these objectives, we propose an adaptive archiving algorithm, suitable for use with any Pareto optimization algorithm, which has various useful properties as follows. It maintains an archive of bounded size, encourages an even distribution of points across the Pareto front, is computationally efficient, and we are able to prove a form of convergence. The method proposed here maintains evenness, efficiency, and cardinality, and provably converges under certain conditions but not all. Finally, the notions underlying our convergence proofs support a new way to rigorously define what is meant by "good spread of points" across a Pareto front, in the context of grid-based archiving schemes. This leads to proofs and conjectures applicable to archive sizing and grid sizing in any Pareto optimization algorithm maintaining a grid-based archive.     

On approximating four covering and packing problems

In this paper, we consider approximability issues of the following four problems: triangle packing, full sibling reconstruction, maximum profit coverage and 2-coverage. All of them are generalized or specialized versions of set-cover and have applications in biology ranging from full-sibling reconstructions in wild populations to biomolecular clusterings; however, as this paper shows, their approximability properties differ considerably. Our inapproximability constant for the triangle packing problem improves upon the previous results in [A. Caprara, R. Rizzi, Packing triangles in bounded degree graphs, Inform. Process. Lett. 84 (4) (2002) 175–180; J. Chlebíková, M. Chlebík, Complexity of approximating bounded variants of optimization problems, Theoret. Comput. Sci. 354 (3) (2006) 320–338]; this is done by directly transforming the inapproximability gap of Håstad for the problem of maximizing the number of satisfied equations for a set of equations over GF(2) [J. Håstad, Some optimal inapproximability results, in: Proc. of the 29th Annual ACM Symp. on Theory of Computing, 1997, pp. 1–10] and is interesting in its own right. Our approximability results on the full siblings reconstruction problems answers questions originally posed by Berger-Wolf et al. [T.Y. Berger-Wolf, B. DasGupta, W. Chaovalitwongse, M.V. Ashley, Combinatorial reconstruction of sibling relationships, in: Proc. of the 6th International Symposium on Computational Biology and Genome Informatics, 2005, pp. 1252–1255; T.Y. Berger-Wolf, S. Sheikh, B. DasGupta, M.V. Ashley, I. Caballero, W. Chaovalitwongse, S.L. Putrevu, Reconstructing sibling relationships in wild populations, Bioinformatics 23 (13) (2007) i49–i56] and our results on the maximum profit coverage problem provides almost matching upper and lower bounds on the approximation ratio, answering a question posed by Hassin and Or [R. Hassin, E. Or, A maximum profit coverage algorithm with application to small molecules cluster identification, in: 5th International Workshop Experimental Algorithms, in: Lecture Notes in Comput. Sci., vol. 4007, Springer-Verlag, 2006, pp. 265–276].     

Approximating the nondominated front using the Pareto Archived Evolution Strategy

We introduce a simple evolution scheme for multiobjective optimization problems, called the Pareto Archived Evolution Strategy (PAES). We argue that PAES may represent the simplest possible nontrivial algorithm capable of generating diverse solutions in the Pareto optimal set. The algorithm, in its simplest form, is a (1 + 1) evolution strategy employing local search but using a reference archive of previously found solutions in order to identify the approximate dominance ranking of the current and candidate solution vectors. (1 + 1)-PAES is intended to be a baseline approach against which more involved methods may be compared. It may also serve well in some real-world applications when local search seems superior to or competitive with population-based methods. We introduce (1 + lambda) and (mu + lambda) variants of PAES as extensions to the basic algorithm. Six variants of PAES are compared to variants of the Niched Pareto Genetic Algorithm and the Nondominated Sorting Genetic Algorithm over a diverse suite of six test functions. Results are analyzed and presented using techniques that reduce the attainment surfaces generated from several optimization runs into a set of univariate distributions. This allows standard statistical analysis to be carried out for comparative purposes. Our results provide strong evidence that PAES performs consistently well on a range of multiobjective optimization tasks.     

An approximating non-stationary subdivision scheme

We present a 3-point C² approximating non-stationary subdivision scheme for designing curves. The weights of the masks of the scheme are defined in terms of some values of trigonometric B-spline basis functions. The scheme has some interesting properties and it is compared with the 2-point and 3-point schemes generating uniform trigonometric spline curves of order 3 and 5. The comparison and the performance of the scheme are demonstrated by examples.     

On the hardness of approximating label-cover

The Label-Cover problem, defined by S. Arora, L. Babai, J. Stern, Z. Sweedyk [Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 724-733], serves as a starting point for numerous hardness of approximation reductions. It is one of six ‘canonical’ approximation problems in the survey of Arora and Lund [Hardness of Approximations, in: Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1996, Chapter 10]. In this paper we present a direct combinatorial reduction from low error-probability PCP [Proceedings of 31st ACM Symposium on Theory of Computing, 1999, pp. 29-40] to Label-Cover showing it NP-hard to approximate to within 2^{(logn)1−o(1)}. This improves upon the best previous hardness of approximation results known for this problem.We also consider the Minimum-Monotone-Satisfying-Assignment (MMSA) problem of finding a satisfying assignment to a monotone formula with the least number of 1's, introduced by M. Alekhnovich, S. Buss, S. Moran, T. Pitassi [Minimum propositional proof length is NP-hard to linearly approximate, 1998]. We define a hierarchy of approximation problems obtained by restricting the number of alternations of the monotone formula. This hierarchy turns out to be equivalent to an AND/OR scheduling hierarchy suggested by M.H. Goldwasser, R. Motwani [Lecture Notes in Comput. Sci., Vol. 1272, Springer-Verlag, 1997, pp. 307-320]. We show some hardness results for certain levels in this hierarchy, and place Label-Cover between levels 3 and 4. This partially answers an open problem from M.H. Goldwasser, R. Motwani regarding the precise complexity of each level in the hierarchy, and the place of Label-Cover in it.     

On the hardness of approximating Max-Satisfy

Max-Satisfy is the problem of finding an assignment that satisfies the maximum number of equations in a system of linear equations over Q. We prove that unless NP⊂BPP Max-Satisfy cannot be efficiently approximated within an approximation ratio of 1/n1−?, if we consider systems of n linear equations with at most n variables and ?>0 is an arbitrarily small constant. Previously, it was known that the problem is NP-hard to approximate within a ratio of 1/nα, but 0<α<1 was some specific constant that could not be taken to be arbitrarily close to 1.     

两种近似EMD的图像检索方法

相似度量是图像检索的关键,EMD是一种有效的度量距离,但其计算比较复杂,而且赖于基本距离的选择。采用Lloyd聚类算法对图像进行高斯混合建模,并以聚类失真作为基本距离提出了两种近似EMD的方法计算相似度。实验结果验证了该方法的有效性,其检索效率与EMD方接近,而且计算复杂度比EMD方法低,基本距离的选择不敏感。     

On the complexity of approximating k-set packing

Given a k-uniform hypergraph, the Maximum k -Set Packing problem is to find the maximum disjoint set of edges. We prove that this problem cannot be efficiently approximated to within a factor of unless P = NP. This improves the previous hardness of approximation factor of by Trevisan. This result extends to the problem of k-Dimensional-Matching.