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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Motivated by a real-world vehicle routing application, we consider themaximum-weight independent set problem: Given a node-weighted graph, find a setof independent (mutually nonadjacent) nodes whose node-weight sum is maximum.Some of the graphs airsing in this application are large, having hundreds ofthousands of nodes and hundreds of millions of edges. To solve instances ofthis size, we develop a new local search algorithm, which is a metaheuristic inthe greedy randomized adaptive search (GRASP) framework. This algorithm, whichwe call METAMIS, uses a wider range of simple local search operations thanpreviously described in the literature. We introduce data structures that makethese operations efficient. A new variant of path-relinking is introduced toescape local optima and so is a new alternating augmenting-path local searchmove that improves algorithm performance. We compare an implementation of ouralgorithm with a state-of-the-art openly available code on public benchmarksets, including some large instances with hundreds of millions of vertices. Ouralgorithm is, in general, competitive and outperforms this openly availablecode on large vehicle routing instances. We hope that our results will lead toeven better MWIS algorithms.

A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems