Randomized heuristics for the Max-Cut problem

DOI10.1080/1055678021000090033zbMath1032.90073OpenAlexW1991068820MaRDI QIDQ4405937

Panos M. Pardalos, Mauricio G. C. Resende, Celso Carneiro Ribeiro, Paola Festa

Publication date: 22 March 2004

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/1055678021000090033

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Routing and wavelength assignment by partition colouring, Multiple phase tabu search for bipartite Boolean quadratic programming with partitioned variables, Solution approaches for the vehicle routing problem with occasional drivers and time windows, Bistable latch Ising machines, Probabilistic GRASP-tabu search algorithms for the UBQP problem, An effective iterated tabu search for the maximum bisection problem, Memetic search for the max-bisection problem, A nonmonotone GRASP, Computational study of a branching algorithm for the maximum \(k\)-cut problem, Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel, Solving combinatorial optimisation problems using oscillator based Ising machines, A new global algorithm for max-cut problem with chordal sparsity, Exponential extrapolation memory for tabu search, Impact of graph structures for QAOA on maxcut, Local Search Based on Genetic Algorithms, Solving MaxCut with quantum imaginary time evolution, Mathematical formulations and solution methods for the uncapacitated \(r\)-allocation \(p\)-hub maximal covering problem, A new discrete filled function method for solving large scale max-cut problems, Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, Solving the maxcut problem by the global equilibrium search, Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem, A modified VNS metaheuristic for max-bisection problems, A discrete filled function algorithm for approximate global solutions of max-cut problems, Two level minimization in multidimensional scaling, TTT plots: a perl program to create time-to-target plots, Constructing test functions for global optimization using continuous formulations of graph problems, A multiple search operator heuristic for the max-k-cut problem, Hybridizing the cross-entropy method: An application to the max-cut problem, A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure, Restart strategies for GRASP with path-relinking heuristics, Path relinking for unconstrained binary quadratic programming, Solving a bus driver scheduling problem with randomized multistart heuristics, A discrete dynamic convexized method for the max-cut problem, Variable neighbourhood search: methods and applications, An efficient Lagrangian smoothing heuristic for max-cut, Lagrangian smoothing heuristics for Max-cut, Black box scatter search for general classes of binary optimization problems, Discrete Optimization with Decision Diagrams, Hybridizations of GRASP with path relinking for the far from most string problem, A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems, From Graph Orientation to the Unweighted Maximum Cut, Solution of Boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation, Randomized heuristics for the family traveling salesperson problem, A bus driver scheduling problem: A new mathematical model and a GRASP approximate solution, Variable neighbourhood search: Methods and applications, Hybrid algorithms for placement of virtual machines across geo-separated data centers, Scatter search --- wellsprings and challenges

Uses Software

Cites Work