Search

The Max-Cut problem is a classical NP-hard problem where the objective is to partition the nodes of an edge-weighted graph in a way that maximizes the sum of edges between the parts. We present a greedy heuristic for solving Max-Cut that combines an Edge-Contraction heuristic with the Differencing Method. We compare the heuristic’s performance to other greedy heuristics using a large and diverse set of problem instances.

This paper aims to synchronize timetables in a transit network so as to minimize the total passenger transfer waiting time. Assuming a fixed headway for each line, we first formulate the problem as an optimization problem with congruence constraints. We show that the problem is NP-hard, and investigate several special cases of the problem that are solvable in polynomial time. Furthermore, we show that the local search for the general problem is equivalent to the well-studied maximum directed cut problem. As such, we use an approximation algorithm for the maximum directed cut problem to solve the timetable synchronization problem. We assess the quality of the algorithm on a real-world case study, and show that our algorithm significantly outperforms the state-of-the-art in the literature. Lastly, we relax the fixed headway assumption, and propose an efficient recursive quasi-linear time algorithm to minimize the total transfer waiting time in this general setting.

In VLSI physical design, many algorithms require the solution of difficult combinatorial optimization problems such as max/min-cut, max-flow problems etc. Due to the vast number of elements typically found in this problem domain, these problems are computationally intractable leading to the use of approximate solutions. In this work, we explore the Ising spin glass model as a solution methodology for hard combinatorial optimization problems using the general purpose GPU (GPGPU). The Ising model is a mathematical model of ferromagnetism in statistical mechanics. Ising computing finds a minimum energy state for the Ising model which essentially corresponds to the expected optimal solution of the original problem. Many combinatorial optimization problems can be mapped into the Ising model. In our work, we focus on the max-cut problem as it is relevant to many VLSI design automation problems. Our method is inspired by the observation that Ising annealing process is very amenable to fine-grain massive parallel GPU computing. We will illustrate how the natural randomness of GPU thread scheduling can be exploited during the annealing process to create random update patterns and allow better GPU resource utilization. Furthermore, the proposed GPU-based Ising computing can handle any general Ising graph with arbitrary connections, which was shown to be difficult for existing FPGA and other hardware based implementation methods. Numerical results show that the proposed GPU Ising max-cut solver can deliver more than 2000X speedup over the CPU version of the algorithm on some large examples, which shows huge performance improvement for addressing many hard optimization algorithms for solving practical VLSI design automation problems.

International audience; Given an undirected graph, a minimum cut cover is a collection of cuts covering the whole set of edges and having minimum cardinality. This paper is dedicated to the fractional version of this problem where a fractional weight is computed for each cut such that, for each edge, the sum of the weights of all cuts containing it is no less than 1, while the sum of all weights is minimized. The fractional cover is computed for different graph classes among which are the weakly bipartite graphs. Efficient algorithms are described to compute lower and upper bounds with worst-case performance guarantees. A general randomized approach is also presented giving new insights into Goemans and Williamson's algorithm for the maximum cut problem. Some numerical experiments are included to assess the quality of bounds

The max-cut problem is one of well-known NP-complete problems and has applications in various fields such as the design process for VLSI (Very-Large-Scale Integration) chips and spin glass theory in statistical physics. In this paper, a harmony search algorithm for the max-cut problem is proposed. Compared to genetic algorithm, harmony search algorithm has advantages of generating a new vector after considering all of the existing vectors and requiring only a few number of parameters to be determined before the run of the algorithm. For 31 benchmark graphs of various types, the proposed harmony search algorithm is compared with a newly developed genetic algorithm and another genetic algorithm taken from the recent literature are presented. The proposed harmony search algorithm produced significantly better results than the two genetic algorithms.

We consider the max-cut and max- k -cut problems under graph-based constraints. Our approach can handle any constraint specified using monadic second-order (MSO) logic on graphs of constant treewidth. We give a 1 2 -approximation algorithm for this class of problems.

The max-cut problem is a much-studied N P -hard combinatorial optimisation problem. Poljak and Turzik found some facet-defining inequalities for this problem, which we call 2-circulant inequalities. Two polynomial-time separation algorithms have been found for these inequalities, but one is very slow and the other is very complicated. We present a third algorithm, which is as fast as the faster of the existing two, but much simpler.

In an instance of the (directed) Max Leaf Tree ( MLT ) problem we are given a vertex-weighted (di)graph G ( V , E , w ) and the goal is to compute a subtree with maximum weight on the leaves. The weighted Connected Max Cut ( CMC ) problem takes in an undirected edge-weighted graph G ( V , E , w ) and seeks a subset S ⊆ V such that the induced graph G [ S ] is connected and ∑ e ∈ δ ( S ) w ( e ) is maximized. We obtain a constant approximation algorithm for MLT when the weights are chosen from { 0 , 1 } , which in turn implies a Ω ( 1 / log ⁡ n ) approximation for the general case. We show that the MLT and CMC problems are related and use the algorithm for MLT to improve the factor for CMC from Ω ( 1 / log 2 ⁡ n ) (Hajiaghayi et al., ESA 2015) to Ω ( 1 / log ⁡ n ) .

A cut tree is a combinatorial structure that represents the edge-connectivity between all pairs of vertices of an undirected graph. Cut trees solve the all pairs minimum s – t -cut problem efficiently. Cut trees have a large number of applications including the solution of important combinatorial problems in fields such as graph clustering and graph connectivity. They have also been applied to scheduling problems, social network analysis, biological data analysis, among others. Two sequential algorithms to compute a cut tree of a capacitated undirected graph are well known: the Gomory–Hu algorithm and the Gusfield algorithm. In this work three parallel cut tree algorithms are presented, including parallel versions of Gusfield and Gomory–Hu algorithms. A hybrid algorithm that combines techniques from both algorithms is proposed which provides a more robust performance for arbitrary instances. Experimental results show that the three algorithms achieve significant speedups on real and synthetic graphs. We discuss the trade-offs between the alternatives, each of which presents better results given the characteristics of the input graph. On several instances the hybrid algorithm outperformed both other algorithms, being faster than the parallel Gomory–Hu algorithm on most instances.

Assuming P ≠ N P , we show that if there is a constant-factor polynomial c-approximation algorithm for Crossing Number, then c ≥ 2 − 16 17 ≈ 1.058824 . Adding the Unique Games Conjecture to the hypotheses, then c ≥ 2 − α ≈ 1.121433 , where α is the approximation ratio of the algorithm for Maximum Cut by Goemans and Williamson.

It is known that the maximum cardinality cut problem is NP -hard even in chordal graphs. On the positive side, the problem is known to be polynomial time solvable in some subclasses of proper interval graphs which is in turn a subclass of chordal graphs. In this paper, we consider the time complexity of the problem in proper interval graphs, and propose a polynomial-time dynamic programming algorithm.

In 2004 Newman 43 suggested a semidefinite programming relaxation for the Linear Ordering Problem (LOP) that is related to the semidefinite program used in the Goemans-Williamson algorithm to approximate the Max Cut problem (Goemans and Williamson, 1995). Her model is based on the observation that linear orderings can be fully described by a series of cuts. Newman (2004) 43 shows that her relaxation seems better suited for designing polynomial-time approximation algorithms for the (LOP) than the widely-studied standard polyhedral linear relaxations.In this paper we strengthen the relaxation proposed by Newman (2004) 43 and conduct a polyhedral study of the corresponding polytope. Furthermore we relate the relaxation to other linear and semidefinite relaxations for the (LOP) and for the Traveling Salesman Problem and elaborate on its connection to the Max Cut problem.

Most traditional weighted graph clustering algorithms are solved by spectral method, which is only suitable for small scale datasets because of the high space and time complexity. How to reduce the computational complexity of graph cut clustering to process the massive complex data has become a challenging problem. To overcome this problem, we design an approximate normalized cuts algorithm without eigen-decomposition for large scale clustering. On the one hand, the space requirement of normalized cut is decreased by sampling a few data points to infer the global features of dataset instead of using the whole affinity matrix; on the other hand, the graph cut clustering procedure is accelerated in an iterative way that using the approximate weighted kernel k-means to optimize the objective function of normalized cut, which avoids the direct eigen-decomposition of Laplacian matrix. We also analyze the approximation error of the proposed algorithm and compare it with other state-of-the-arts clustering algorithms on several benchmark datasets. The experimental results demonstrate that our method can efficiently do the clustering when the number of data objects exceeds tens of thousands.

The Cyclic Cutwidth Minimization Problem (CCMP) is a Graph Layout Problem that consists of finding an embedding of the vertices of a candidate graph in a host graph, in order to minimize the maximum cut of a host edge. In this case, the host graph is restricted to be a cycle. In this paper, we identify a new lower bound for the problem, and also a property which allows search procedures to drastically reduce the neighborhood size during the search. Additionally, we propose the use of an alternative objective function for min–max optimization problems, never used before in the context of the CCMP. These strategies have been combined within a multistart search procedure for this problem. The obtained method is compared with the state of the art for the CCMP using sets of problem instances previously published. Statistical tests indicate the merit of our proposal.

We adapt a result by Masuda et al. [IEEE Transactions on Computers 39 (1990), 124–127] on FIXED LINEAR CROSSING NUMBER to show that SIMPLE MAX-CUT is NP-hard on comparability graphs.

Given a graph with labels defined on edges and a source-sink pair ( s , t ) , the Label s - t Cut problem asks for a minimum number of labels such that the removal of edges with these labels disconnects s and t. Similarly, the Global Label Cut problem asks for a minimum number of labels to disconnect G itself. For these two problems, we identify two useful parameters, i.e., l max , the maximum length of any s - t path (only applies to Label s - t Cut), and f max , the maximum number of appearances of any label in the graph (applies to the two problems). We show that l max = 2 and f max = 2 are two complexity thresholds for Label s - t Cut. Furthermore, we give (i) an O * ( c k ) time parameterized algorithm for Label s - t Cut with l max bounded from above, where parameter k is the number of labels in a solution, and c is a constant with l max - 1 < c < l max , (ii) a combinatorial l max -approximation algorithm for Label s - t Cut, and (iii) a polynomial time exact algorithm for Global Label Cut with f max bounded from above. We give an FPT algorithm for Label s - t Cut in a special case.We give a pure combinatorial approximation algorithm for Label s - t Cut.We give a polynomial time exact algorithm for Global Label Cut in a special case.

We investigate the role of the 1- and ∞-norms of eigenvectors in spectral graph theory. In particular, we produce several randomized algorithms which show that various graph-theoretic parameters can be tightly bounded by the eigenvalues as well as norms of the corresponding eigenvectors. Further, in some cases, these inequalities can determine the parameters exactly. Our results include: a spectral bound for the densest subgraph problem, an adapted “converse” to the Expander Mixing Lemma, and an adapted spectral approach to the maximum cut problem.

We give a new approximation algorithm for the Min k-Size s-t Cut problem.The algorithm is very simple and has only three lines to state.We analyze the integrality gap of a natural LP for the problem. Being the unbalanced version of the famous Min s-t Cut problem, the Min k-Size s-t Cut problem asks to find a k-size s-t cut with the minimum capacity, where a k-size s-t cut means an s-t cut with its s-side having size at most k. This problem is fundamental and has extensive applications, especially in community identification in social and information networks. It is known that the Min k-Size s-t Cut problem is NP-hard and can be approximated within O ( log ? n ) , where n is the number of vertices in the input graph. In this paper, we give a new approximation algorithm for the Min k-Size s-t Cut problem based on the parametric flow technique. The algorithm is very simple and has only three lines to state. Its approximation ratio is k + 1 k + 1 - k * , where k * is the size of the s-side of an optimal solution.

In some application cases, the solutions of combinatorial optimization problems on graphs should satisfy an additional vertex size constraint. In this paper, we consider size-constrained minimum s-t cut problems and size-constrained dense subgraph problems. We introduce the minimum s-t cut with at-least-k vertices problem, the minimum s-t cut with at-most-k vertices problem, and the minimum s-t cut with exactly k vertices problem. We prove that they are NP-complete. Thus, they are not polynomially solvable unless P = NP .On the other hand, we also study the densest at-least-k-subgraph problem (DalkS) and the densest at-most-k-subgraph problem (DamkS) introduced by Andersen and Chellapilla 1. We present a polynomial time algorithm for DalkS when k is bounded by some constant c. We also present two approximation algorithms for DamkS. The first approximation algorithm for DamkS has an approximation ratio of n - 1 k - 1 , where n is the number of vertices in the input graph. The second approximation algorithm for DamkS has an approximation ratio of O ( n ? ) , for some ? < 1 / 3 .

In this paper, a new formulation of the max-cut problem is proposed. Several semidefinite programming(SDP) relaxations of the max-cut problem are given and some relationships between them are put forward. Based on a new SDP relaxation, an algorithm is presented for finding a better approximate solution of the max-cut problem and we show the advantages of our model and algorithm with several examples.

Graphical abstractDisplay Omitted HighlightsWe design a hybrid evolutionary algorithm (TSHEA) for the max-cut problem.Results disclose TSHEA discovers new best solutions for 15 out of 91 instances.Analysis indicates the effectiveness of the designed key components. This paper presents a tabu search based hybrid evolutionary algorithm (TSHEA) for solving the max-cut problem. The proposed algorithm integrates a distance-and-quality based solution combination operator and a tabu search procedure based on neighborhood combination of one-flip and constrained exchange moves. Comparisons with leading reference algorithms from the literature disclose that the proposed algorithm discovers new best solutions for 15 out of 91 instances, while matching the best known solutions on all but 4 instances. Analysis indicates that the neighborhood combination and the solution combination operator play key roles to the effectiveness of the proposed algorithm.

The maximum common subgraph isomorphism problem is a difficult graph problem, and the problem of finding the maximum common subgraph isomorphism problem is NP-hard. This means there is likely no algorithm that will be able to find the maximal isomorphic common subgraph in polynomial time because as the size of the graphs grows the search space for the solution will grow exponentially. This research provides a method that will approximate the maximum common subgraph isomorphism problem by producing a weighted graph, where the weights will give an indication of the probability that the associated link will be in the maximum common subgraph of the two input graphs. The experimental results show that the method can effectively generate a weighted graph containing most of the expected links that would exist in the maximum common subgraph of some given graphs with similar structures.

Judicious Partition Problem is to partition the vertex set of a graph such that certain quantities are optimized simultaneously. Let k be a positive integer and G a graph with m edges. It is proved in this paper that the vertex set of G can be partitioned into k parts V 1 , ? , V k such that e ( V i ) ? m k 2 + k - 1 2 k 2 ( 2 m + 1 4 - 1 2 ) + 2 3 for each i ? { 1 , 2 , ? , k } and e ( V 1 , ? , V k ) ? k - 1 k m + k - 1 2 k ( 2 m + 1 4 - 1 2 ) - ( k - 2 ) 2 8 k , where e ( V i ) is the number of edges with both ends in V i and e ( V 1 , ? , V k ) = m - ? i = 1 k e ( V i ) . This partially solves a problem proposed by Bollobas and Scott, and, for some values of m , solves the problem affirmatively.

The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs. There are only two unpublished works (technical reports) where heuristic approaches are tested on BQP instances. Our goal is to combine straightforward search elements to balance diversification and intensification in both exact (branch and bound) and heuristic (iterated local search) frameworks. We perform a number of experiments to test individual search components and also to create new benchmarks when comparing against the state of the art, which the proposed procedure outperforms.

A separation algorithm is a procedure for generating cutting planes. Up to now, only a few polynomial-time separation algorithms were known for the Boolean quadric and cut polytopes. These polytopes arise in connection with zero–one quadratic programming and the max-cut problem, respectively. We present a new algorithm, which separates over a class of valid inequalities that includes all odd bicycle wheel inequalities and (2p+1,2)(2p+1,2)-circulant inequalities. It exploits, in a non-trivial way, three known results in the literature: one on the separation of View the MathML source{0,12}-cuts, one on the symmetries of the polytopes in question, and one on an affine mapping between the polytopes.

International audience; A uniform cut polytope is defined as the convex hull of the incidence vectors of all cuts in an undirected graph G for which the cardinalities of the shores are fixed. In this paper, we study linear descriptions of such polytopes. Complete formulations are presented for the cases when the cardinality k of one side of the cut is equal to 1 or 2. For larger values of k, investigations with relation to the shape of these polytopes are reported. We namely determine their diameter and also provide new families of facet-defining inequalities

In this paper, we study a generalization of the classical minimum cut prob- lem, called Connectivity Preserving Minimum Cut (CPMC) problem, which seeks a minimum cut to separate a pair (or pairs) of source and destination nodes and meanwhile ensure the connectivity between the source and its partner node(s). The CPMC problem is a rather powerful formulation for a set of problems and finds applications in many other areas, such as network security, image processing, data mining, pattern recognition, and machine learning. For this important problem, we consider two variants, connectiv- ity preserving minimum node cut (CPMNC) and connectivity preserving minimum edge cut (CPMEC). For CPMNC, we show that it cannot be ap- proximated within {\alpha}logn for some constant {\alpha} unless P=NP, and cannot be approximated within any poly(logn) unless NP has quasi-polynomial time algorithms. The hardness results hold even for graphs with unit weight and bipartite graphs. Particularly, we show that polynomial time solutions exist for CPMEC in planar graphs and for CPMNC in some special planar graphs. The hardness of CPMEC in general graphs remains open, but the polynomial time algorithm in planar graphs still has important practical applications.

In this paper we introduce survivable network design problems under a two-stage stochastic model with fixed recourse and finitely many scenarios. We propose a new cut-based formulation based on orientation properties which is stronger than the undirected cut-based model. We use a two-stage branch&cut algorithm for solving the decomposed model to provable optimality. In order to accelerate the computations, we suggest a new cut strengthening technique for the decomposed L-shaped optimality cuts that is computationally fast and easy to implement.

We study the solution quality for min-cut problems on graphs when restricting the shapes of the allowed cuts. In particular we are interested in min-cut problems with additional size constraints on the parts being cut out from the graph. Such problems include the bisection problem, the separator problem, or the sparsest cut problem. We therefore aim at cutting out a given number m of vertices from a graph using as few edges as possible. We consider this problem on solid grid graphs, which are finite, connected subgraphs of the infinite two-dimensional grid that do not have holes. Our interest is in the tradeoff between the simplicity of the cut shapes and their solution quality: we study corner cuts in which each cut has at most one right-angled bend. We prove that optimum corner cuts get us arbitrarily close to a cut-out part of size m, and that this limitation makes us lose only a constant factor in the quality of the solution. We obtain our result by a thorough study of cuts in polygons and the effect of limiting these to corner cuts.

The image segmentation problem is to delineate, or segment, a salient feature in an image. As such, this is a bipartition problem with the goal of separating the foreground from the background. An NP-hard optimization problem, the Normalized Cut problem, is often used as a model for image segmentation. The common approach for solving the normalized cut problem is the spectral method which generates heuristic solutions based upon finding the Fiedler eigenvector. Recently, Hochbaum (IEEE Trans Pattern Anal Mach Intell 32(5):889–898, 2010) presented a new relaxation of the normalized cut problem, called normalized cut $$^\prime $$ problem, which is solvable in polynomial time by a combinatorial algorithm. We compare this new algorithm with the spectral method and present experimental evidence that the combinatorial algorithm provides solutions which better approximate the optimal normalized cut solution. In addition, the subjective visual quality of the segmentations provided by the combinatorial algorithm greatly improves upon those provided by the spectral method. Our study establishes an interesting observation about the normalized cut criterion that the segmentation which provides the subjectively best visual bipartition rarely corresponds to the segmentation which minimizes the objective function value of the normalized cut problem. We conclude that modeling the image segmentation problem as normalized cut criterion might not be appropriate. Instead, normalized cut $$^\prime $$ not only provides better visual segmentations but is also solvable in polynomial time. Therefore, normalized cut $$^\prime $$ should be the preferred segmentation criterion for both complexity and good segmentation quality reasons.

Highlights► BLS is an effective Max-Cut algorithm based on iterated local search. ► BLS alternates between a descent phase and a dedicated diversification phase. ► Diversification is adapative and combines guided and random perturbations. ► BLS finds new record-breaking solutions for 33 out of 71 benchmark instances. ► The source code and the results of BLS is available online.; International audience; Given an undirected graph G=(V,E)G=(V,E) where each edge of E is weighted with an integer number, the maximum cut problem (Max-Cut) is to partition the vertices of V into two disjoint subsets so as to maximize the total weight of the edges between the two subsets. As one of Karp's 21 NP-complete problems, Max-Cut has attracted considerable attention over the last decades. In this paper, we present Breakout Local Search (BLS) for Max-Cut. BLS explores the search space by a joint use of local search and adaptive perturbation strategies. The proposed algorithm shows excellent performance on the set of well-known maximum cut benchmark instances in terms of both solution quality and computational time. Out of the 71 benchmark instances, BLS is capable of finding new improved results in 34 cases and attaining the previous best-known result for 35 instances, within computing times ranging from less than 1s to 5.6h for the largest instance with 20,000 vertices.

We study online packing and covering problems, stated as zero-one linear programs. This class of problems includes maximum cut, bipartite matching, and set cover. In the packing problem, variables arrive in an online fashion. Upon arrival of v, the weight of v in the objective function and in any constraints involving v is revealed and the algorithm may update its solution. In the covering problem, constraints arrive in an online fashion. We allow the relaxation that the algorithm may change the value of each variable a constant number of times, k. We give an algorithm for OnlinePacking(k) and prove that for any @e>0, there exists some k equal to [email protected]?(1/@e) such that the algorithm gives a ([email protected]) approximation for OnlinePacking(k). We then show near-tightness for several cases. We also prove that no deterministic algorithm exists for OnlineCovering(k) that achieves a competitive ratio less than 3/2.

Given an undirected graph G = ( V , E ) with weights on the edges, the max-bisection problem (MBP) is to find a partition of the vertex set V into two subsets V1 and V2 of equal cardinality such that the sum of the weights of the edges crossing V1 and V2 is maximized. Relaxing the equal cardinality, constraint leads to the max-cut problem (MCP). In this work, we present a memetic algorithm for MBP which integrates a grouping crossover operator and a tabu search optimization procedure. The proposed crossover operator preserves the largest common vertex groupings with respect to the parent solutions while controlling the distance between the offspring solution and its parents. Extensive experimental studies on 71 well-known G-set benchmark instances demonstrate that our memetic algorithm improves, in many cases, the current best known solutions for both MBP and MCP.

In the Maximum Common Edge Subgraph Problem (MCES), given two graphs G and H with the same number of vertices, one has to find a common subgraph of G and H (not necessarily induced) with the maximum number of edges. This problem arises in parallel programming environments, and was first defined in Bokhari (1981) [2]. This paper presents a new integer programming formulation for the MCES and a polyhedral study of this model. Several classes of valid inequalities are identified, most of which are shown to define facets. These findings were incorporated into a branch&cut algorithm we implemented. Experimental results with this algorithm are reported.

We prove several complexity results about the gap inequalities for the max-cut problem, including (i) the gap- 1 inequalities do not imply the other gap inequalities, unless NP = Co NP ; (ii) there must exist non-redundant gap inequalities with exponentially large coefficients, unless NP = Co NP ; (iii) the associated separation problem can be solved in finite (doubly exponential) time.

This paper describes a graph clustering algorithm that aims to minimize the normalized cut criterion and has a model order selection procedure. The performance of the proposed algorithm is comparable to spectral approaches in terms of minimizing normalized cut. However unlike spectral approaches, the proposed algorithm scales to graphs with millions of nodes and edges. The algorithm consists of three components that are processed sequentially: a greedy agglomerative hierarchical clustering procedure, model order selection, and a local refinement. For a graph of n nodes and O(n) edges, the computational complexity of the algorithm is O(nlog^2n), a major improvement over the O(n^3) complexity of spectral methods. Experiments are performed on real and synthetic networks to demonstrate the scalability of the proposed approach, the effectiveness of the model order selection procedure, and the performance of the proposed algorithm in terms of minimizing the normalized cut metric.

Motivated by a fundamental geometrical object, the cut locus, we introduce and study a new combinatorial structure on graphs., Comment: 16 pages, 15 figures. First in a series of four articles

Unconstrained binary quadratic programming problem (UBQP) consists in maximizing a quadratic 0-1 function. It is a well known NP-hard problem and is considered as a unified model for a variety of combinatorial optimization problems. This paper combines a tabu Hopfield neural network (HNN) (THNN) with estimation of distribution algorithm (EDA), and thus a THNN-EDA is proposed for the UBQP. In the THNN, the tabu rule, instead of the original updating rule of the HNN, is used to govern the state transition or updating of neurons to search for the global minimum of the energy function. A probability vector in EDA model is built to characterize the distribution of promising solutions in the search space, and then the THNN is guided by the global search information in EDA model to search better solution in the promising region. Thus, the short term memory of the tabu mechanism in the THNN cooperates with the long term memory mechanism in the EDA to help the network escape from local minima. The THNN-EDA is tested on 21 UBQP benchmark problems with the size ranging from 3000 to 7000, and 48 maximum cut benchmark problems, a special case of the UBQP, with the size ranging from 512 to 3375. Simulation results show that the THNN-EDA is better than the other HNN based algorithms, and is better than or competitive with metaheuristic algorithms and state-of-the-art algorithms.

We consider a hierarchical relaxation, called Handelman hierarchy, for a class of polynomial optimization problems. We prove that the rank of Handelman hierarchy, if applied to a standard quadratic formulation of Max-Cut, is exactly the same as the number of nodes of the underlying graph. Also we give an error bound for Handelman hierarchy, in terms of its level, applied to the Max-Cut formulation.

We studied the minimum cut cover problem that consists in finding a minimum cardinality family of cuts C of a graph G such that each edge of G belongs to at least one cut C ∈ C . This problem is NP -hard and arises in fault testing and diagnosis, pattern recognition, and biological identification. We propose here a new integer programming formulation and a new exact algorithm for the problem. We also proposed a simple heuristic and made empirical experiments to compare it with those reported in the literature. It is an ongoing work. The preliminary results show that the dual bounds provided by the new formulation are tighter than those obtained using the earlier one and the primal bounds given by our heuristic are near optimal for the small instances and tighter than other reported in the literature.

Branch cut method is a powerful noise-immune algorithm for correct phase unwrapping of noisy phase maps. The shortest branch cut length promises the optimal unwrapping result of the wrapped phase maps. A new algorithm is proposed to search for the shortest branch cut length by simple exchange operation. Although the algorithm is on the basis of stochastic search techniques, it has a high probability of finding the shortest branch cut length or an approximation of it. Compared with the traditional algorithms, the algorithm is fast and competitive.

We place our focus on the gap between treewidth’s success in producing fixed-parameter polynomial algorithms for hard graph problems, and specifically Hamiltonian Circuit and Max Cut, and the failure of its directed variants (directed treewidth (Johnson et al., 2001 [13]), DAG-width (Obdrzálek, 2006 [14]) and Kelly-width (Hunter and Kreutzer, 2007 [15]) to replicate it in the realm of digraphs. We answer the question of why this gap exists by giving two hardness results: we show that Directed Hamiltonian Circuit is W[2]-hard when the parameter is the width of the input graph, for any of these widths, and that Max Di Cut remains NP-hard even when restricted to DAGs, which have the minimum possible width under all these definitions. Along the way, we extend our reduction for Directed Hamiltonian Circuit to show that the related Minimum Leaf Outbranching problem is also W[2]-hard when naturally parameterized by the number of leaves of the solution, even if the input graph has constant width. All our results also apply to directed pathwidth and cycle rank.

We show that the exact computation of a minimum or a maximum cut of a given graph G is out of reach for any one-pass streaming algorithm, that is, for any algorithm that runs over the input stream of G's edges only once and has a working memory of o(n2) bits. This holds even if randomization is allowed. Research highlights? A minimum/maximum cut cannot be computed exactly by a one-pass streaming algorithm. ? This holds for deterministic and randomized algorithms. ? Tools of communication complexity are utilized.

We prove a strong version of the Max-Flow Min-Cut theorem for countable networks, namely that in every such network there exist a flow and a cut that are "orthogonal" to each other, in the sense that the flow saturates the cut and is zero on the reverse cut. If the network does not contain infinite trails then this flow can be chosen to be mundane, i.e. to be a sum of flows along finite paths. We show that in the presence of infinite trails there may be no orthogonal pair of a cut and a mundane flow. We finally show that for locally finite networks there is an orthogonal pair of a cut and a flow that satisfies Kirchhoff's first law also for ends., 19 pages, to be published in Journal of Combinatorial Theory, Series B

The angular synchronization problem is to obtain an accurate estimation (up to a constant additive phase) for a set of unknown angles $\theta_1,...,\theta_n$ from $m$ noisy measurements of their offsets $\theta_i-\theta_j \mod 2\pi$. Of particular interest is angle recovery in the presence of many outlier measurements that are uniformly distributed in $[0,2\pi)$ and carry no information on the true offsets. We introduce an efficient recovery algorithm for the unknown angles from the top eigenvector of a specially designed Hermitian matrix. The eigenvector method is extremely stable and succeeds even when the number of outliers is exceedingly large. For example, we successfully estimate $n=400$ angles from a full set of $m={400 \choose 2}$ offset measurements of which 90% are outliers in less than a second on a commercial laptop. The performance of the method is analyzed using random matrix theory and information theory. We discuss the relation of the synchronization problem to the combinatorial optimization problem \textsc{Max-2-Lin mod} $L$ and present a semidefinite relaxation for angle recovery, drawing similarities with the Goemans-Williamson algorithm for finding the maximum cut in a weighted graph. We present extensions of the eigenvector method to other synchronization problems that involve different group structures and their applications, such as the time synchronization problem in distributed networks and the surface reconstruction problems in computer vision and optics., Comment: 25 pages

We compute a complete linear description of the bipartite subgraph polytope, for up to seven nodes, and a conjectured complete description for eight nodes. We then show how these descriptions were used to compute the integrality ratio of various relaxations of the max-cut problem, again for up to eight nodes.

Alon, et al. (2003) [1] proved that every graph with a large cut has a bipartition in which each vertex class contains correspondingly few edges. We prove an analogous result for partitions into k>=3 classes; along the way we prove a result for biased bipartitions.

Many problems in computer vision can be posed in terms of energy minimization, where the relevant energy function models the interactions of many pixels. Finding the global or near-global minimum of such functions tends to be difficult, precisely due to these interactions of large (>3) numbers of pixels. In this paper, we derive a set of sufficient conditions under which energies which are functions of discrete binary variables may be minimized using graph cut techniques. We apply these conditions to the problem of incorporating shape priors in segmentation. Experimental results demonstrate the validity of this approach.

We investigate the Maximum Common Edge Subgraph Problem (MCES) defined as follows. Given two graphs G and H with the same number of vertices, find a common subgraph of G and H (not necessary induced) with the maximum number of edges. This problem arises in parallel programming environments, and was first defined by Bokhari in [S. Bokhari, On the mapping problem, IEEE Trans. Comput., C-30(3), 1981]. We present a new integer programming formulation for the MCES problem and carry out a polyhedral investigation of this model. A number of valid inequalities are identified, most of which are facet-defining. We also report on computational experiments.

In this paper, a discrete filled function algorithm embedded with continuous approximation is proposed to solve max-cut problems. A new discrete filled function is defined for max-cut problems, and properties of the function are studied. In the process of finding an approximation to the global solution of a max-cut problem, a continuation optimization algorithm is employed to find local solutions of a continuous relaxation of the max-cut problem, and then global searches are performed by minimizing the proposed filled function. Unlike general filled function methods, characteristics of max-cut problems are used. The parameters in the proposed filled function need not to be adjusted and are exactly the same for all max-cut problems that greatly increases the efficiency of the filled function method. Numerical results and comparisons on some well known max-cut test problems show that the proposed algorithm is efficient to get approximate global solutions of max-cut problems.