An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
From MaRDI portal
Publication:3790963
DOI10.1287/OPRE.36.3.493zbMath0646.90084OpenAlexW2159739530MaRDI QIDQ3790963
Francisco Barahona, Martin Grötschel, Michael Jünger, Gerhard Reinelt
Publication date: 1988
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/2a618975e68a2a669f03c8757fc163b5f05f1d85
cutting plane algorithmcircuit designsolid-state physicsprinted circuit board designground states of spin glassesmax-cut problem in graphs
Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Applications of mathematical programming (90C90) Combinatorial optimization (90C27)
Related Items (only showing first 100 items - show all)
Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems ⋮ \(f\)-flip strategies for unconstrained binary quadratic programming ⋮ Two-edge connected spanning subgraphs and polyhedra ⋮ An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions ⋮ Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\) ⋮ Decomposition and optimization over cycles in binary matroids ⋮ Building an iterative heuristic solver for a quantum annealer ⋮ Application of cut polyhedra. I ⋮ Applications of cut polyhedra. II ⋮ The expected relative error of the polyhedral approximation of the max- cut problem ⋮ An approximate max-flow min-cut relation for undirected multicommodity flow, with applications ⋮ On computational capabilities of Ising machines based on nonlinear oscillators ⋮ The equipartition polytope. I: Formulations, dimension and basic facets ⋮ Solving the max-cut problem using eigenvalues ⋮ An effective iterated tabu search for the maximum bisection problem ⋮ Computational study of valid inequalities for the maximum \(k\)-cut problem ⋮ Via Minimization with Pin Preassignments and Layer Preference ⋮ A branch-and-cut algorithm for the equicut problem ⋮ Facets of the balanced (acyclic) induced subgraph polytope ⋮ A cutting plane algorithm for a clustering problem ⋮ Experiments in quadratic 0-1 programming ⋮ Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ A class of spectral bounds for max \(k\)-cut ⋮ Computational study of a branching algorithm for the maximum \(k\)-cut problem ⋮ Lifting and separation procedures for the cut polytope ⋮ The unconstrained binary quadratic programming problem: a survey ⋮ Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel ⋮ New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph ⋮ Minimizing breaks by maximizing cuts. ⋮ The maximum cardinality cut problem in co-bipartite chain graphs ⋮ Intractability of min- and max-cut in streaming graphs ⋮ Probabilistic nonunitary gate in imaginary time evolution ⋮ Exact ground states of two-dimensional \(\pm J\) Ising spin glasses ⋮ Solving VLSI design and DNA sequencing problems using bipartization of graphs ⋮ Partitioning planar graphs: a fast combinatorial approach for max-cut ⋮ A new discrete filled function method for solving large scale max-cut problems ⋮ Bounds for Random Binary Quadratic Programs ⋮ A semidefinite relaxation based global algorithm for two-level graph partition problem ⋮ A VNS metaheuristic with stochastic steps for Max 3-cut and Max 3-section ⋮ A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems ⋮ Finding the maximum cut by the greedy algorithm ⋮ A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem ⋮ Cuts in undirected graphs. I ⋮ Cardinality constrained minimum cut problems: complexity and algorithms. ⋮ Solving the maxcut problem by the global equilibrium search ⋮ Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs ⋮ NP-hardness of the Euclidean Max-Cut problem ⋮ A successive quadratic programming algorithm for SDP relaxation of Max-Bisection ⋮ The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds ⋮ A branch-and-bound algorithm for solving max-\(k\)-cut problem ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ A discrete filled function algorithm for approximate global solutions of max-cut problems ⋮ Approximation algorithms ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs ⋮ Ising formulations of some graph-theoretic problems in psychological research: models and methods ⋮ A multiple search operator heuristic for the max-k-cut problem ⋮ A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs ⋮ Compositions in the bipartite subgraph polytope ⋮ Facets for the cut cone. I ⋮ Facets for the cut cone. II: Clique-web inequalities ⋮ Round robin scheduling -- a survey ⋮ The inequicut cone ⋮ Canonical dual approach to solving the maximum cut problem ⋮ Maximum cut in fuzzy nature: models and algorithms ⋮ A discrete dynamic convexized method for the max-cut problem ⋮ Pseudo-Boolean optimization ⋮ A projected gradient algorithm for solving the maxcut SDP relaxation ⋮ A tight lower bound for a special case of quadratic 0-1 programming ⋮ Randomized heuristics for the Max-Cut problem ⋮ Approximation algorithms for the bi-criteria weighted MAX-CUT problem ⋮ Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm ⋮ Application of semi definite relaxation and variable neighborhood search for multiuser detection in synchronous CDMA ⋮ A new branch and bound method with pretreatment for the binary quadratic programming ⋮ A semidefinite programming based polyhedral cut and price approach for the maxcut problem ⋮ Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems ⋮ A novel formulation of the max-cut problem and related algorithm ⋮ Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints ⋮ Approximating graph-constrained max-cut ⋮ Approximating max-cut under graph-MSO constraints ⋮ Computational Methods for Solving Nonconvex Block-Separable Constrained Quadratic Problems ⋮ A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems ⋮ Spectral bounds for the maximum cut problem ⋮ From Graph Orientation to the Unweighted Maximum Cut ⋮ Solution of Boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation ⋮ Greedy differencing edge-contraction heuristic for the max-cut problem ⋮ A linearization framework for unconstrained quadratic (0-1) problems ⋮ Maximization of submodular functions: theory and enumeration algorithms ⋮ The node capacitated graph partitioning problem: A computational study ⋮ Engineering Branch-and-Cut Algorithms for the Equicut Problem ⋮ A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem ⋮ New approaches for optimizing over the semimetric polytope ⋮ Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut ⋮ A \(2^{|E|/4}\)-time algorithm for MAX-CUT ⋮ A technique for speeding up the solution of the Lagrangean dual ⋮ Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem ⋮ Laplacian eigenvalues and the maximum cut problem ⋮ Node and edge relaxations of the max-cut problem ⋮ Speeding up a memetic algorithm for the max-bisection problem ⋮ Solution of large weighted equicut problems ⋮ An unconstrained quadratic binary programming approach to the vertex coloring problem
This page was built for publication: An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
