The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Aug. 05, 2025
Filed:
Aug. 20, 2024
Neo4j Sweden Ab, San Mateo, CA (US);
Adam Schill-Collberg, Malmö, SE;
Jacob Sznajdman, Gothenburg, SE;
Neo4j Sweden AB, San Mateo, CA (US);
Abstract
A method and high-performance apparatus for creating an approximate maximum k-cut of a graph. In various embodiments, nodes and weighted edges in a graph are used to compute a partitioning of a graph such that the edge weight between partitions is maximized. In various embodiments, the method and apparatus use a greedy random construction of cuts for its first approximation, whose solutions are then subject to local search for better solutions, and local path-relinking for the final level of refinement. In various embodiments, one or more of the greedy random construction, local search, and path relinking are parallelized. A novel parallel algorithm is disclosed for perturbing the state of a cut to see if a better one is cheaply available.