共查询到20条相似文献,搜索用时 15 毫秒
1.
Number partitioning is a classical NP-hard combinatorial optimization problem, whose solution is challenging for both exact and approximative methods. This work presents a new algorithm for number partitioning, based on ideas drawn from tree search, breadth first search, and beam search. A new set of benchmark instances for this problem is also proposed. The behavior of the new method on this and other testbeds is analyzed and compared to other well known heuristics and exact algorithms. 相似文献
2.
We show how simple and effective metaheuristics can be developed for the number partitioning problem using the problem space approach [1]. In a previous application of local search to number partitioning [2], it was found that the performance of simulated annealing used in conjunction with swap neighborhoods was disappointing relative to the differencing heuristic of Karmarkar and Karp [3]. Using problem space neighborhoods as an alternative to swapping, we empirically demonstrate several orders of magnitude improvement over the differencing algorithm, albeit with greater computation time. This improvement in performance comes as little surprise since a modified version of the differencing heuristic is explicitly embedded in the problem space algorithm. 相似文献
3.
4.
Let G be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that G admits a bipartition such that each vertex class meets edges of total weight at least (w 1?Δ1)/2+2w 2/3, where wi is the total weight of edges of size i and Δ1 is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph G (i.e., multi-hypergraph), we show that there exists a bipartition of G such that each vertex class meets edges of total weight at least (w 0?1)/6+(w 1?Δ1)/3+2w 2/3, where w 0 is the number of edges of size 1. This generalizes a result of Haslegrave. Based on this result, we show that every graph with m edges, except for K 2 and K 1,3, admits a tripartition such that each vertex class meets at least [2m/5] edges, which establishes a special case of a more general conjecture of Bollobás and Scott. 相似文献
5.
Given two strings s and t, a difference encoding is a third string that contains sufficient information to derivet t from s. An algorithm is presented which derives a difference encoding that can be represented in the fewest number of bits relative to the string edit operators insert, delete, replace, and skip. This algorithm has practical significance for distributed text processing applications. 相似文献
6.
In this paper, we describe a generalization of the multidimensional two-way number partitioning problem (MDTWNPP) where a set of vectors has to be partitioned into p sets (parts) such that the sums per every coordinate should be exactly or approximately equal. We will call this generalization the multidimensional multi-way number partitioning problem (MDMWNPP). Also, an efficient memetic algorithm (MA) heuristic is developed to solve the multidimensional multi-way number partitioning problem obtained by combining a genetic algorithm (GA) with a powerful local search (LS) procedure. The performances of our memetic algorithm have been compared with the existing numerical results obtained by CPLEX based on an integer linear programming formulation of the problem. The solution reveals that our proposed methodology performs very well in terms of both quality of the solutions obtained and the computational time compared with the previous method of solving the multidimensional two-way number partitioning problem. 相似文献
7.
Glenn H. Hurlbert 《Discrete Applied Mathematics》2007,155(18):2594-2600
Deo and Micikevicius recently gave a new bijection for spanning trees of complete bipartite graphs. In this paper we devise a generalization of Deo and Micikevicius's method, which is also a modification of Olah's method for encoding the spanning trees of any complete multipartite graph K(n1,…,nr). We also give a bijection between the spanning trees of a planar graph and those of any of its planar duals. Finally we discuss the possibility of bijections for spanning trees of DeBriujn graphs, cubes, and regular graphs such as the Petersen graph that have integer eigenvalues. 相似文献
8.
S. R. Bedzhanova 《Moscow University Mathematics Bulletin》2011,66(4):176-177
It is shown that a linear Boolean function of n variables can be realized over the basis {&,V,−} by an irredundant circuit admitting a unit diagnostic test of the length ] log(n−1)[ +2 for inverse output errors of elements. 相似文献
9.
10.
Jie Zhang Jie Chen Junqing Gong Aijun Ge Chuangui Ma 《Designs, Codes and Cryptography》2018,86(6):1339-1366
Recently, leakage-resilient cryptography has become a hot research topic. It seeks to build more robust models of adversarial access to cryptographic algorithms. The main goal is to design a scheme that remains secure even when arbitrary, yet bounded, information about secret key is leaked. In this paper, we present a modular framework for designing leakage-resilient attribute-based encryption (ABE) schemes based on extended predicate encoding. We first extend the predicate encoding to the leakage-resilient predicate encoding; and then, design several leakage-resilient predicate encodings, and finally give a generic construction of leakage-resilient ABE based on the newly proposed encodings. Moreover, we can instantiate our framework in prime order bilinear groups to obtain concrete constructions, and prove their full security under the standard k-Lin assumption in the continual memory leakage model. 相似文献
11.
In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements. 相似文献
12.
Anna Varvak 《Discrete Mathematics》2008,308(23):5834-5840
We specify procedures by which ?ukasiewicz paths can encode combinatorial objects, such as involutions, partitions, and permutations. As application, we use these encoding procedures to give a combinatorial proof of the differential operator identity
13.
An exact algorithm is presented for solving edge weighted graph partitioning problems. The algorithm is based on a branch and bound method applied to a continuous quadratic programming formulation of the problem. Lower bounds are obtained by decomposing the objective function into convex and concave parts and replacing the concave part by an affine underestimate. It is shown that the best affine underestimate can be expressed in terms of the center and the radius of the smallest sphere containing the feasible set. The concave term is obtained either by a constant diagonal shift associated with the smallest eigenvalue of the objective function Hessian, or by a diagonal shift obtained by solving a semidefinite programming problem. Numerical results show that the proposed algorithm is competitive with state-of-the-art graph partitioning codes. 相似文献
14.
We prove polynomial-time solvability of a large class of clustering problems where a weighted set of items has to be partitioned into clusters with respect to some balancing constraints. The data points are weighted with respect to different features and the clusters adhere to given lower and upper bounds on the total weight of their points with respect to each of these features. Further the weight-contribution of a vector to a cluster can depend on the cluster it is assigned to. Our interest in these types of clustering problems is motivated by an application in land consolidation where the ability to perform this kind of balancing is crucial.Our framework maximizes an objective function that is convex in the summed-up utility of the items in each cluster. Despite hardness of convex maximization and many related problems, for fixed dimension and number of clusters, we are able to show that our clustering model is solvable in time polynomial in the number of items if the weight-balancing restrictions are defined using vectors from a fixed, finite domain. We conclude our discussion with a new, efficient model and algorithm for land consolidation. 相似文献
15.
This paper presents a new heuristic for graph partitioning called Path Optimization (PO), and the results of an extensive set of empirical comparisons of the new algorithm with two very well-known algorithms for partitioning: the Kernighan-Lin algorithm and simulated annealing. Our experiments are described in detail, and the results are presented in such a way as to reveal performance trends based on several variables. Sufficient trials are run to obtain 99% confidence intervals small enough to lead to a statistical ranking of the implementations for various circumstances. The results for geometric graphs, which have become a frequently used benchmark in the evaluation of partitioning algorithms, show that PO holds an advantage over the others.
In addition to the main test suite described above, comparisons of PO to more recent partitioning approaches are also given. We present the results of comparisons of PO with a parallelized implementation of Goemans' and Williamson's 0.878 approximation algorithm, a flow-based heuristic due to Lang and Rao, and the multilevel algorithm of Hendrickson and Leland. 相似文献
16.
David Avis 《Discrete and Computational Geometry》1986,1(1):265-276
We discuss the problem of partitioning a set of points into two subsets with certain conditions on the diameters of the subsets and on their cardinalities. For example, we give anO(n
2 logn) algorithm to find the smallestt such that the set can be split into two equal cardinality subsets each of which has diameter at mostt. We also give an algorithm that takes two pairs of points (x, y) and (s, t) and decides whether the set can be partitioned into two subsets with the respective pairs of points as diameters. 相似文献
17.
Noising methods for a clique partitioning problem 总被引:1,自引:0,他引:1
Irène Charon 《Discrete Applied Mathematics》2006,154(5):754-769
This paper deals with the application of noising methods to a clique partitioning problem for a weighted graph. The aim is to study different ways to add noise to the data, and to show that the choice of the noise-adding-scheme may have some impact on the performance of these methods. Among the noise-adding-schemes described here, two of them are totally new, leading to the “forgotten vertices” and to the “forgotten edges” methods. We also experimentally study a generic noising method that automatically tunes its parameters. For each noise-adding-scheme, we compare a variant which inserts descents and a variant which does not. 相似文献
18.
Stig Skelboe 《BIT Numerical Mathematics》2006,46(3):617-629
Many stiff systems of ordinary differential equations (ODEs) modeling practical problems can be partitioned into loosely coupled subsystems. In this paper the objective of the partitioning is to permit the numerical integration of one time step to be performed as the solution of a sequence of small subproblems. This reduces the computational complexity compared to solving one large system and permits efficient parallel execution under appropriate conditions. The subsystems are integrated using methods based on low order backward differentiation formulas.This paper presents an adaptive partitioning algorithm based on a classical graph algorithm and techniques for the efficient evaluation of the error introduced by the partitioning.The power of the adaptive partitioning algorithm is demonstrated by a real world example, a variable step-size integration algorithm which solves a system of ODEs originating from chemical reaction kinetics. The computational savings are substantial. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65L06, 65Y05 相似文献
19.
A stable vector algorithm for the solution of block diagonallinear systems is obtained by a permutation of the unknownscalled wrap-around partitioning combined with standard QR factorization.Wrap-around partitioning uses blocking and selects the unknownsin the blocks in turns. After a suitable orthogonal eliminationstep one ends up with a reduced system which is again blockbidiagonal and so wrap-around partitioning can be applied again.Using a simple model for vectorization overhead it is shownthat small block sizes give best performance. The minimal blocksize 2, which corresponds to cyclic reduction, is suboptimaldue to memory bank conflicts. 相似文献
20.
Stig Skelboe 《BIT Numerical Mathematics》2010,50(2):405-423
Many implicit differential equations (IDEs) modelling practical problems can be partitioned into loosely coupled subsystems. In this paper the objective of the partitioning is to permit the numerical integration of one time step to be performed as the solution of a sequence of small subproblems. This reduces the computational complexity compared to solving one large system and permits efficient parallel execution under appropriate conditions. The subsystems are integrated using methods based on low order backward differentiation formulas. 相似文献