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/

Zendy Plus

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

Zendy Tools

Zendy Open

The first nontrivial lower bound of the worst-case approximation ratio forthe maxcut problem was achieved via the dual Cheeger problem, whose optimalvalue is referred to the dual Cheeger constant $h^+$, and later improvedthrough its modification $\widehat{h}^+$. However, the dual Cheeger problem andits modification themselves are relatively unexplored, especially lack ofeffective approximate algorithms. To this end, we first derive equivalentspectral formulations of $h^+$ and $\widehat{h}^+$ within the framework of thenonlinear spectral theory of signless 1-Laplacian, present their interactionswith the Laplacian matrix and 1-Laplacian, and then use them to develop aninverse power algorithm that leverages the local linearity of the objectivefunctions involved. We prove that the inverse power algorithm monotonicallyconverges to a ternary-valued eigenvector, and provide the approximate valuesof $h^+$ and $\widehat{h}^+$ on G-set for the first time. The recursivespectral cut algorithm for the maxcut problem can be enhanced by integratinginto the inverse power algorithms, leading to significantly improvedapproximate values on G-set. Finally, we show that the lower bound of theworst-case approximation ratio for the maxcut problem within the recursivespectral cut framework can not be improved beyond $0.769$.

Dual Cheeger Constants, Signless 1-Laplacians and Maxcut