| Tartalom: |
http://eprints.sztaki.hu/9072/ |
| Archívum: |
SZTAKI Repozitórium |
| Gyűjtemény: |
Status = Published
Type = Article
|
| Cím: |
A 0.821-ratio purely combinatorial algorithm for maximum k-vertex cover in bipartite graphs
|
| Létrehozó: |
Bonnet, Édouard
Escoffier, B
Paschos, V T
Stamoulis, G
|
| Kiadó: |
Springer-Verlag
|
| Dátum: |
2016
|
| Téma: |
QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
|
| Tartalmi leírás: |
We study the polynomial time approximation of the max k-vertex cover problem in bipartite graphs and propose a purely combinatorial algorithm that beats the only such known algorithm, namely the greedy approach. We present a computer-assisted analysis of our algorithm, establishing that the worst case approximation guarantee is bounded below by 0.821. © Springer-Verlag Berlin Heidelberg 2016.
|
| Nyelv: |
angol
|
| Típus: |
Article
PeerReviewed
|
| Formátum: |
text
|
| Azonosító: |
|
| Kapcsolat: |
10.1007/978-3-662-49529-2_18
|
