Optimistic Competitive Analysis: Stochastic Models, Predictions, and Revocable Decisions
Notice bibliographique
Résumé
In conventional online competitive analysis, it is assumed that online algorithms are dealing with anadversary who controls the input items and their arrival sequence, while the algorithms are making irrevocable decisions along the way. This approach is often pessimistic and results in worst-case performance guarantees that are rarely reflected in practice. In order to measure performance in more realistic settings, we consider various “relaxations” of the online model that assist the algorithm in three general ways: 1. Allowing the algorithm to alter some earlier decisions that seem to not be good in hindsight. 2. Restricting the adversary’s power to control the arrival sequence. 3. Removing some of the uncertainty of the input by having some information about the offline instance. We focus on two classical online problems: bipartite matching and interval selection. In the case ofbipartite matching, we introduce a new input model and analyze the performance of a natural greedy algorithm [27]. We also conduct an experimental analysis comparing state-of-the-art algorithms in the known i.i.d. setting and show that simple greedy algorithms might be very competitive in practice [32]. We consider the problem of interval selection with revocable acceptances in the adversarial model [30], the random-order model [31], as well as in a predictions setting [83]. We give improved bounds on the performance of some existing algorithms, and introduce new algorithms tailored to these specialized models. Moreover, most of the algorithms we study are conceptually simple, a desirable characteristic that often correlates with inherent efficiency and ease of implementation.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction distillée sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Apprise à partir de 10 348 étiquettes directes de Codex et de 10 348 étiquettes directes de Gemma. Le mode candidate est l'union des têtes enseignantes seuillées; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont ni des étiquettes humaines ni des étiquettes directes de modèles de pointe.
Scores Codex et Gemma par catégorie
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,001 | 0,001 |
| Méta-épidémiologie (sens strict) | 0,001 | 0,001 |
| Méta-épidémiologie (sens large) | 0,001 | 0,000 |
| Bibliométrie | 0,002 | 0,005 |
| Études des sciences et des technologies | 0,001 | 0,000 |
| Communication savante | 0,001 | 0,001 |
| Science ouverte | 0,001 | 0,000 |
| Intégrité de la recherche | 0,000 | 0,001 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,000 | 0,000 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validéePrédiction automatique; un appel candidat d’une seule tête enseignante, pas un consensus.
Le détail, modèle par modèle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».