# Maximum Weight Independent Set (MWIS) on AVR

Source: [Maximum Weight Independent Set (MWIS) on AVR](<https://www.sota2.com/research/sota/maximum-weight-independent-set-mwis-on-avr>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-05-08T07:27:02.359Z

Evaluation of algorithms solving the Maximum Weight Independent Set (MWIS) problem on the AVR dataset, reporting execution time and the best optimality gap achieved.

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

| Scope | Recorded value |
| --- | --- |
| Task | Maximum Weight Independent Set (MWIS) |
| Dataset (including any stated split) | AVR |
| Metric | Time (s) |
| Unit | TIME |
| Direction | Lower is better |
| Results loaded | 28 of 28 |
| Coverage | All results currently returned for this benchmark |

Evaluation settings may differ between results. The original papers and recorded configurations are needed to establish comparability. A shared metric name alone does not establish an identical protocol.

## Metrics

- [Time (s)](<https://www.sota2.com/research/sota/maximum-weight-independent-set-mwis-on-avr.md?metric=Time%20(s)>): Lower is better; unit: TIME.

- [Best Optimality Gap (%)](<https://www.sota2.com/research/sota/maximum-weight-independent-set-mwis-on-avr.md?metric=Best%20Optimality%20Gap%20(%25)>): Lower is better; unit: PERCENT.

## Recorded results

| Method | Time (s) | Result date | Report paper |
| --- | --- | --- | --- |
| Graph Normalization (GN) | 0.1 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 0.1 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 0.2 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 0.2 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 0.4 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 0.4 | Not recorded | 69fd6de25497b3b670c8925a |
| BS | 1 | Not recorded | 69fd6de25497b3b670c8925a |
| BS | 1 | Not recorded | 69fd6de25497b3b670c8925a |
| BS | 1 | Not recorded | 69fd6de25497b3b670c8925a |
| BS | 1 | Not recorded | 69fd6de25497b3b670c8925a |
| BS | 1 | Not recorded | 69fd6de25497b3b670c8925a |
| BS | 1 | Not recorded | 69fd6de25497b3b670c8925a |
| BS | 1 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 1.4 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 1.4 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 4.6 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 4.6 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 5 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 5 | Not recorded | 69fd6de25497b3b670c8925a |
| BS | 10 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 12.7 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 12.7 | Not recorded | 69fd6de25497b3b670c8925a |
| BS | 18 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 27 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 27 | Not recorded | 69fd6de25497b3b670c8925a |
| BS | 297 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 801 | Not recorded | 69fd6de25497b3b670c8925a |
| Graph Normalization (GN) | 3751 | Not recorded | 69fd6de25497b3b670c8925a |

### Graph Normalization (GN)

Time (s): 0.1. Result ID: 69fd8fc747f34ce924e02d61.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_034","Edges":"23K","Start Type":"Random Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 0.1. Result ID: 69fd8fc747f34ce924e02d62.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_034","Edges":"23K","Start Type":"Warm Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 0.2. Result ID: 69fd8fc747f34ce924e02d67.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_027","Edges":"2K","Start Type":"Random Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 0.2. Result ID: 69fd8fc747f34ce924e02d68.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_027","Edges":"2K","Start Type":"Warm Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 0.4. Result ID: 69fd8fc747f34ce924e02d5e.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_024","Edges":"3K","Start Type":"Random Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 0.4. Result ID: 69fd8fc747f34ce924e02d5f.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_024","Edges":"3K","Start Type":"Warm Start"}. This record does not assert independent reproduction.

### BS

Time (s): 1. Result ID: 69fd8fc747f34ce924e02d5d.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5d2e1e209131ce9d7d7f.md>)

Recorded evaluation configuration: {"Instance":"AVR\_024","Edges":"3K"}. This record does not assert independent reproduction.

### BS

Time (s): 1. Result ID: 69fd8fc747f34ce924e02d60.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5d2e1e209131ce9d7d7f.md>)

Recorded evaluation configuration: {"Instance":"AVR\_034","Edges":"23K"}. This record does not assert independent reproduction.

### BS

Time (s): 1. Result ID: 69fd8fc747f34ce924e02d63.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5d2e1e209131ce9d7d7f.md>)

Recorded evaluation configuration: {"Instance":"AVR\_023","Edges":"127K"}. This record does not assert independent reproduction.

### BS

Time (s): 1. Result ID: 69fd8fc747f34ce924e02d66.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5d2e1e209131ce9d7d7f.md>)

Recorded evaluation configuration: {"Instance":"AVR\_027","Edges":"2K"}. This record does not assert independent reproduction.

### BS

Time (s): 1. Result ID: 69fd8fc747f34ce924e02d69.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5d2e1e209131ce9d7d7f.md>)

Recorded evaluation configuration: {"Instance":"AVR\_026","Edges":"604K"}. This record does not assert independent reproduction.

### BS

Time (s): 1. Result ID: 69fd8fc747f34ce924e02d6c.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5d2e1e209131ce9d7d7f.md>)

Recorded evaluation configuration: {"Instance":"AVR\_028","Edges":"516K"}. This record does not assert independent reproduction.

### BS

Time (s): 1. Result ID: 69fd8fc747f34ce924e02d72.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5d2e1e209131ce9d7d7f.md>)

Recorded evaluation configuration: {"Instance":"AVR\_033","Edges":"4M"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 1.4. Result ID: 69fd8fc747f34ce924e02d64.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_023","Edges":"127K","Start Type":"Random Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 1.4. Result ID: 69fd8fc747f34ce924e02d65.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_023","Edges":"127K","Start Type":"Warm Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 4.6. Result ID: 69fd8fc747f34ce924e02d6d.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_028","Edges":"516K","Start Type":"Random Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 4.6. Result ID: 69fd8fc747f34ce924e02d6e.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_028","Edges":"516K","Start Type":"Warm Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 5. Result ID: 69fd8fc747f34ce924e02d6a.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_026","Edges":"604K","Start Type":"Random Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 5. Result ID: 69fd8fc747f34ce924e02d6b.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_026","Edges":"604K","Start Type":"Warm Start"}. This record does not assert independent reproduction.

### BS

Time (s): 10. Result ID: 69fd8fc747f34ce924e02d75.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5d2e1e209131ce9d7d7f.md>)

Recorded evaluation configuration: {"Instance":"AVR\_009","Edges":"43M"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 12.7. Result ID: 69fd8fc747f34ce924e02d70.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_036","Edges":"1.5M","Start Type":"Random Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 12.7. Result ID: 69fd8fc747f34ce924e02d71.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_036","Edges":"1.5M","Start Type":"Warm Start"}. This record does not assert independent reproduction.

### BS

Time (s): 18. Result ID: 69fd8fc747f34ce924e02d6f.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5d2e1e209131ce9d7d7f.md>)

Recorded evaluation configuration: {"Instance":"AVR\_036","Edges":"1.5M"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 27. Result ID: 69fd8fc747f34ce924e02d73.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_033","Edges":"4M","Start Type":"Random Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 27. Result ID: 69fd8fc747f34ce924e02d74.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_033","Edges":"4M","Start Type":"Warm Start"}. This record does not assert independent reproduction.

### BS

Time (s): 297. Result ID: 69fd8fc747f34ce924e02d77.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/68fa5d2e1e209131ce9d7d7f.md>)

Recorded evaluation configuration: {"Instance":"AVR\_002","Edges":"344M"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 801. Result ID: 69fd8fc747f34ce924e02d76.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_009","Edges":"43M","Start Type":"Warm Start"}. This record does not assert independent reproduction.

### Graph Normalization (GN)

Time (s): 3751. Result ID: 69fd8fc747f34ce924e02d78.

[Reporting paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

[Method origin paper](<https://www.sota2.com/research/paper/69fd6de25497b3b670c8925a.md>)

Recorded evaluation configuration: {"Instance":"AVR\_002","Edges":"344M","Start Type":"Warm Start"}. This record does not assert independent reproduction.

Page 1 of 1. This is an index page, not the full collection.