Cублінійний оптимальний наближений алгоритм реоптимізації для задачі про мінімальне вершинне покриття графа
With the approximate solution of discrete optimization problems such idea arises: is it possible, taking into account the information about the optimal solution of an instance (or close to it), use this information to find the optimal (or close to it) solution of instance problem obtained as a resul...
Gespeichert in:
| Datum: | 2013 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2013
|
| Online Zugang: | http://journal.iasa.kpi.ua/article/view/57494 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
Institution
System research and information technologies| Zusammenfassung: | With the approximate solution of discrete optimization problems such idea arises: is it possible, taking into account the information about the optimal solution of an instance (or close to it), use this information to find the optimal (or close to it) solution of instance problem obtained as a result of minor local modifications of the initial instance. This approach, called reoptimization, allows, for example, in some cases, getting the best quality of approximation (which is defined as the ratio between the value of an approximate solution to the exact ratio and called approximation ratio) in locally modified instances than at initials. If for some tasks approximation ratio can not be improved (e.g. in class of all approximation algorithms with polynomial complexity), the ratio is called the threshold or optimal (algorithm which achieved this ratio is also called the threshold or optimal). The complexity of the algorithms is estimated by the number of hits (queries) to a special oracle. For reoptimization of minimum vertex cover problem (with addition of one vertex and some set of edges) (3/2)-approximation algorithm with additive error and sublinear (constant) complexity is received. It is shown that the approximation ratio of 3/2 is the threshold in the class of algorithms with constant complexity. |
|---|