Search

Dealing with large-scale graphs requires an efficient graph partitioner that produces balanced partitions with fewer cut edges/vertices in a reasonable amount of time. Despite several algorithms that have been proposed, it is still insufficient. Even with the continuous growth of graph volume, they do not consider the graph volume during graph partitioning. Therefore, these algorithms generate an imbalanced workload. We propose a graph partitioner algorithm VSCT based essentially on four key metrics: Volume, Size, Cuts, and Time to maintain high-quality graph partitioning. Using real-world datasets, we show that VSCT performs an efficient partitioning quality against the existing graph partitioning algorithms. [ABSTRACT FROM AUTHOR]

The preprocessing of data is an important task in rough set theory as well as in Entropy. The discretization of data as part of the preprocessing of data is a very influential process. Is there a connection between the segmentation of the data histogram and data discretization? The authors propose a novel data segmentation technique based on a histogram with regard to the quality of a data discretization. The significance of a cut's position has been researched on several groups of histograms. A data set reduct was observed with respect to the histogram type. Connections between the data histograms and cuts, reduct and the classification rules have been researched. The result is that the reduct attributes have a more irregular histogram than attributes out of the reduct. The following discretization algorithms were used: the entropy algorithm and the Maximal Discernibility algorithm developed in rough set theory. This article presents the Cuts Selection Method based on histogram segmentation, reduct of data and MD algorithm of discretization. An application on the selected database shows that the benefits of a selection of cuts relies on histogram segmentation. The results of the classification were compared with the results of the Naïve Bayes algorithm. [ABSTRACT FROM AUTHOR]

To improve the value of the objective function, two algorithms for transforming the current base into a new one are proposed. It is shown that the maximum cut problem on an undirected graph can be reduced to finding the base of the extended polynomial, for which the value of the minimum cut that separates the source and the sink is maximum. The necessary and sufficient conditions for optimality of the solution of the maximum cut problem on undirected graphs in terms of flow theory are formulated. [ABSTRACT FROM AUTHOR]

By the ordered tree inclusion we will check whether a pattern tree P can be included in a target tree T, where the order of siblings in both P and T matters. This problem has many applications in practice, such as retrieval of documents, data mining, and RNA structure matching. In this paper, we propose an efficient algorithm for this problem. Its time complexity is bounded by ${\text{O}(\vert }T\vert \cdot \;min\{h_{P}{,\;\vert \text{leaves(}}P)\vert \})$O(|T|·min{hP,|leaves(P)|}), with ${\text{O}(\vert }T\vert + \vert P\vert)$O(|T|+|P|) space being used, where hP (hT) represents the height of P (resp., T) and leaves (P) stands for the set of the leaves of P. Up to now the best algorithm for this problem needs $\Theta (\vert T\vert \cdot \vert leaves(P)\vert)$Θ(|T|·|leaves(P)|) time and ${\text{O}(\vert }P\vert + \vert T\vert)$O(|P|+|T|) space. Extensive experiments have been done, which show that the new algorithm can perform much better than the existing ones in practice. [ABSTRACT FROM AUTHOR]

Discretization of continuous attributes is an important task in rough sets and many discretization algorithms have been proposed. However, most of the current discretization algorithms are univariate, which may reduce the classification ability of a given decision table. To solve this problem, we propose a supervised and multivariate discretization algorithm — SMDNS in rough sets, which is derived from the traditional algorithm naive scaler (called Naive). Given a decision table DT = ( U , C , D , V , f ) , since SMDNS uses both class information and the interdependence among various condition attributes in C to determine the discretization scheme, the cuts obtained by SMDNS are much less than those obtained by Naive, while the classification ability of DT remains unchanged after discretization. Experimental results show that SMDNS is efficient in terms of the classification accuracy and the number of generated cuts. In particular, our algorithm can obtain a satisfactory compromise between the number of cuts and the classification accuracy. [ABSTRACT FROM AUTHOR]

The biggest challenge when disclosing private data is to share information contained in databases while protecting people from being individually identified. Microaggregation is a family of methods for statistical disclosure control. The principle of microaggregation is that confidentiality rules permit the publication of individual records if they are partitioned into groups of size larger or equal to a fixed threshold value, where none is more representative than the others in the same group. The application of such rules leads to replacing individual values by those computed from small groups (microaggregates), before data publication. This work proposes a column generation algorithm for numerical microaggregation in which its pricing problem is solved by a specialized branch-and-bound. The algorithm is able to find, for the first time, lower bounds for instances of three real-world datasets commonly used in the literature. Furthermore, new best known solutions are obtained for these instances by means of a simple heuristic method with the columns generated. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider the checkpoint problem. The input consists of an undirected graph , a set of source–destination pairs , and a collection of paths connecting the pairs. A feasible solution is a multicut , namely, a set of edges whose removal disconnects every source–destination pair. For each we define . In the sum checkpoint (SCP) problem the goal is to minimize , while in the maximum checkpoint (MCP) problem the goal is to minimize . These problems have several natural applications, e.g., in urban transportation and network security. In a sense, they combine the multicut problem and the minimum membership set cover problem. For the sum objective we show that weighted SCP is equivalent, with respect to approximability, to undirected multicut. Thus there exists an approximation for SCP in general graphs. Our current approximability results for the max objective have a wide gap: we provide an approximation factor of for MCP and a hardness of 2 under the assumption . The hardness holds for trees. This solves an open problem of Nelson (2009) . We complement the lower bound by an almost matching upper bound with an asymptotic approximation factor of 2. On trees with all having an ancestor–descendant relation, we give a combinatorial exact algorithm. Besides the algorithm being combinatorial, its running time improves by many orders of magnitude the LP algorithm that follows from total unimodularity. Finally, we show strong hardness for the well-known problem of finding a path with minimum forbidden pairs, which in a sense can be considered the dual to the checkpoint problem. Despite various works on this problem, hardness of approximation was not known prior to this work. We show that the problem cannot be approximated within for some constant , unless . This is the strongest type of hardness possible. It carries over to directed acyclic graphs and is a huge improvement over the plain -hardness of Gabow [H.N. Gabow, Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput. 36 (6) (2007) 1648–1671]. [Copyright &y& Elsevier]

Abstract: Let be a directed graph with non-negative arc weights. We study the problem of computing certain special co-cycle bases of , in particular, a minimum weight weakly fundamental co-cycle basis. A co-cycle in corresponds to a cut in the underlying undirected graph and a arc incidence vector is associated with each co-cycle, where the coordinates are used for the arcs crossing the cut. The weight of a co-cycle is the sum of the weights of those arcs such that . The vector space over generated by the arc incidence vectors of the co-cycles is the co-cycle space of . The co-cycle space of can also be defined as the orthogonal complement of the cycle space of . A set of linearly independent co-cycles that span the co-cycle space is a co-cycle basis of . The problem of computing a co-cycle basis such that the sum of weights of the co-cycles in the basis is the least possible is the minimum co-cycle basis problem. A co-cycle basis is weakly fundamental if for every there is an arc such that while for . The minimum cycle basis problem in directed and undirected graphs is a well-studied problem and while polynomial time algorithms are known for these problems, the problem of computing a minimum weight weakly fundamental cycle basis has recently been shown to be APX-hard. We show that the co-cycle basis corresponding to the cuts of a Gomory–Hu tree of the underlying undirected graph of is a minimum weight weakly fundamental co-cycle basis of . This is, in fact, a minimum co-cycle basis of and it is also totally unimodular. Thus this is a special co-cycle basis that simultaneously answers several questions in the domain of co-cycle bases. It is known that there is no such special cycle basis for general graphs. [Copyright &y& Elsevier]

Logical relations occur frequently in integer programming problems and are modelled by introducing binary variables in association with linear expressions. Applications requiring constraints involving precedence, exclusion, implication and other conditions give rise to the logical relations OR and IMPLIES in the models. These relations will be considered in this paper from a modelling point of view and formulations investigated for situations where the logical variables link sets of integer variables. Valid inequalities (cuts) that can be added to a model will be developed for a number of the formulations and the computational benefits of these cuts will be considered from an experimental point of view by considering the performance of sets of problem instances. New formulations and combinations of older established formulations will be considered. It will be contended that tight formulations may not always be the most successful. [ABSTRACT FROM AUTHOR]

We review the Lawler-Murty [24,20] procedure for finding the JC best solutions to combinatorial optimization problems. Then we introduce an alternative algorithm which is based on a binary search tree procedure. We apply both algorithms to the problems of finding the K best bases in a matroid, perfect matchings, and best cuts in a network. [ABSTRACT FROM AUTHOR]