Verified Approximation Algorithms

Robin Eßmann; Tobias Nipkow; Simon Robillard

doi:10.1007/978-3-030-51054-1_17

Verified Approximation Algorithms

Robin Eßmann, Tobias Nipkow, Simon Robillard

Default

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

We present the first formal verification of approximation algorithms for NP-complete optimization problems: vertex cover, independent set, load balancing, and bin packing. We uncover incompletenesses in existing proofs and improve the approximation ratio in one case.

Original language	English
Title of host publication	Automated Reasoning - 10th International Joint Conference, IJCAR 2020, Proceedings
Editors	Nicolas Peltier, Viorica Sofronie-Stokkermans
Publisher	Springer
Pages	291-306
Number of pages	16
ISBN (Print)	9783030510534
DOIs	https://doi.org/10.1007/978-3-030-51054-1_17
State	Published - 2020
Event	10th International Joint Conference on Automated Reasoning, IJCAR 2020 - Virtual, Online Duration: 1 Jul 2020 → 4 Jul 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12167 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Joint Conference on Automated Reasoning, IJCAR 2020
City	Virtual, Online
Period	1/07/20 → 4/07/20

Access to Document

10.1007/978-3-030-51054-1_17

Cite this

Eßmann, R., Nipkow, T., & Robillard, S. (2020). Verified Approximation Algorithms. In N. Peltier, & V. Sofronie-Stokkermans (Eds.), Automated Reasoning - 10th International Joint Conference, IJCAR 2020, Proceedings (pp. 291-306). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12167 LNAI). Springer. https://doi.org/10.1007/978-3-030-51054-1_17

Eßmann, Robin ; Nipkow, Tobias ; Robillard, Simon. / Verified Approximation Algorithms. Automated Reasoning - 10th International Joint Conference, IJCAR 2020, Proceedings. editor / Nicolas Peltier ; Viorica Sofronie-Stokkermans. Springer, 2020. pp. 291-306 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{31dfdc1eae9f429c988c06a7dc2b8c08,

title = "Verified Approximation Algorithms",

abstract = "We present the first formal verification of approximation algorithms for NP-complete optimization problems: vertex cover, independent set, load balancing, and bin packing. We uncover incompletenesses in existing proofs and improve the approximation ratio in one case.",

author = "Robin E{\ss}mann and Tobias Nipkow and Simon Robillard",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 10th International Joint Conference on Automated Reasoning, IJCAR 2020 ; Conference date: 01-07-2020 Through 04-07-2020",

year = "2020",

doi = "10.1007/978-3-030-51054-1_17",

language = "English",

isbn = "9783030510534",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "291--306",

editor = "Nicolas Peltier and Viorica Sofronie-Stokkermans",

booktitle = "Automated Reasoning - 10th International Joint Conference, IJCAR 2020, Proceedings",

}

Eßmann, R, Nipkow, T & Robillard, S 2020, Verified Approximation Algorithms. in N Peltier & V Sofronie-Stokkermans (eds), Automated Reasoning - 10th International Joint Conference, IJCAR 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12167 LNAI, Springer, pp. 291-306, 10th International Joint Conference on Automated Reasoning, IJCAR 2020, Virtual, Online, 1/07/20. https://doi.org/10.1007/978-3-030-51054-1_17

Verified Approximation Algorithms. / Eßmann, Robin; Nipkow, Tobias; Robillard, Simon.
Automated Reasoning - 10th International Joint Conference, IJCAR 2020, Proceedings. ed. / Nicolas Peltier; Viorica Sofronie-Stokkermans. Springer, 2020. p. 291-306 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12167 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Verified Approximation Algorithms

AU - Eßmann, Robin

AU - Nipkow, Tobias

AU - Robillard, Simon

PY - 2020

Y1 - 2020

N2 - We present the first formal verification of approximation algorithms for NP-complete optimization problems: vertex cover, independent set, load balancing, and bin packing. We uncover incompletenesses in existing proofs and improve the approximation ratio in one case.

AB - We present the first formal verification of approximation algorithms for NP-complete optimization problems: vertex cover, independent set, load balancing, and bin packing. We uncover incompletenesses in existing proofs and improve the approximation ratio in one case.

UR - http://www.scopus.com/inward/record.url?scp=85088260755&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-51054-1_17

DO - 10.1007/978-3-030-51054-1_17

M3 - Conference contribution

AN - SCOPUS:85088260755

SN - 9783030510534

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 291

EP - 306

BT - Automated Reasoning - 10th International Joint Conference, IJCAR 2020, Proceedings

A2 - Peltier, Nicolas

A2 - Sofronie-Stokkermans, Viorica

PB - Springer

T2 - 10th International Joint Conference on Automated Reasoning, IJCAR 2020

Y2 - 1 July 2020 through 4 July 2020

ER -

Eßmann R, Nipkow T, Robillard S. Verified Approximation Algorithms. In Peltier N, Sofronie-Stokkermans V, editors, Automated Reasoning - 10th International Joint Conference, IJCAR 2020, Proceedings. Springer. 2020. p. 291-306. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-51054-1_17

Verified Approximation Algorithms

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this