A multidimensional maximum bisection problem

2015/06/25 by Zoran Lj. Maksimović, Maksimovic, Zoran
Engineering · Mathematics · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.1.6 #Mathematical Approximation and Integration #Point processes and geometric inequalities #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1506.07731

openalex publication_date 2015/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This work introduces a multidimensional generalization of the maximum bisection problem. A mixed integer linear programming formulation is proposed with the proof of its correctness. The numerical tests, made on the randomly generated graphs, indicates that the multidimensional generalization is more difficult to solve than the original problem.

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Related

• A connected multidimensional maximum bisection problem
• MAX BISECTION might be harder to approximate than MAX CUT
• Graph bisection revisited
• Minimum Bisection is NP-hard on Unit Disk Graphs
• Max-Cut and Max-Bisection are NP-hard on unit disk graphs