English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

There has recently been much progress on exact algorithms for the(un)weighted graph (bi)partitioning problem using branch-and-bound and relatedmethods. In this note we present and improve an easily computable, purelycombinatorial lower bound for the weighted bipartitioning problem. The bound iscomputable in $O(n\log n+m)$ time steps for weighted graphs with $n$ verticesand $m$ edges. In the branch-and-bound setting, the bound for each newsubproblem can be updated in $O(n+(m/n)\log n)$ time steps amortized over aseries of $n$ branching steps; a rarely triggered tightening of the boundrequires search on the graph of unassigned vertices and can take from $O(n+m)$to $O(nm+n^2\log n)$ steps depending on implementation and possible boundquality. Representing a subproblem uses $O(n)$ space. Although the bound isweak, we believe that it can be advantageous in a parallel setting to be ableto generate many subproblems fast, possibly out-weighting the advantages oftighter, but much more expensive (algebraic, spectral, flow) lower bounds.  We use a recent priority task-scheduling framework for giving a parallelimplementation, and show the relative improvements in bound quality andsolution speed by the different contributions of the lower bound. A detailedcomparison with standardized input graphs to other lower bounds and frameworksis pending. Detailed investigations of branching and subproblem selection rulesare likewise not the focus here, but various options are discussed.

An improved, easily computable combinatorial lower bound for weighted graph bipartitioning