Multi-Agent submodular optimization: Variations and generalizations
Notice bibliographique
Résumé
Given a finite ground set V and its power set 2 V , submodular optimization is the class of problems where we either minimize or maximize a submodular set function f : 2 V → R over a family F ⊆ 2 V of feasible sets.These problems have been extensively studied for both minimization and maximization under very general types of constraints F. The last ten years, in particular, have seen a great amount of progress on this area.Along with these algorithmic advances, many interesting applications of these problems have been found in areas of computer science such as machine learning, robotics, and algorithmic game theory.This thesis extends the submodular optimization class of problems to frameworks where we have different agents competing for subsets of items.Different variants of these multi-agent frameworks are introduced and studied.Specifically this thesis studies 1) the extent to which the approximability of these more general problems is linked to the submodular optimization (i.e., single-agent) versions; and 2) the extent to which the approximability for the different multi-agent frameworks relate to each other.We believe that the results in this thesis substantially expand the family of tractable models for submodular optimization problems, especially for maximization.and support during these years have been a great source of professional and personal growth.I have learned so much from him.His sense of humor and unending optimism made my PhD journey incredibly pleasant and smooth, even during the tougher times.I am very grateful to him for numerous interesting and inspiring conversations over dinners and lunch.Also, for providing generous financial support that allowed me to do several academic travels during my PhD.My studies were partially financially supported by the Computer Science department at McGill; I am very grateful to them.I would also like to thank the Mathematics and Statistics department's administrative staff for all their help in terms of paperwork, especially Jackie and Raffaella.I am grateful to the examiners of this thesis: Roy Schwartz and Adrian Vetta, for taking the time to read it and providing valuable comments and suggestions
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 machine sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Le volet Gemma est une étiquette directe du modèle pour chaque travail de la base, lue sur la notice réduite au titre. Le volet Codex est un classifieur appris des 10 348 étiquettes directes de Codex et calibré sur les taux pondérés de l'échantillon; les champs sans appui suffisant ne portent aucun appel Codex. Le mode candidate est l'union des deux volets; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont pas des étiquettes humaines.
Scores du classifieur distillé par catégorie (deux têtes)
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,002 | 0,009 |
| Méta-épidémiologie (sens strict) | 0,001 | 0,001 |
| Méta-épidémiologie (sens large) | 0,002 | 0,001 |
| Bibliométrie | 0,001 | 0,002 |
| Études des sciences et des technologies | 0,001 | 0,001 |
| Communication savante | 0,001 | 0,002 |
| Science ouverte | 0,002 | 0,002 |
| Intégrité de la recherche | 0,001 | 0,003 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,003 | 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 source (Gemma direct ou Codex distillé), 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 ».