Nos tutelles

CNRS Dauphine PSL *

Rechercher





Accueil > PERSONNES

Membres

publié le , mis à jour le

retour a la liste des membres

Jerome Monnot

Email : Jerome.Monnot@dauphine.fr

Tel : 01 44 05 41 62
Bureau : P614
Site Personnel: http://www.lamsade.dauphine.fr/~monnot/
Pole : Optimisation combinatoire algorithmique
Status : Directeur de Recherche
Domaines de Recherche : Algorithmic Game Theory; Computational Complexity; Computational Social choice; Approximation


Encadrement de these de doctorat :


  • Mehdi Khosravian : La recherche de solutions max-min pour des problèmes algotithmiques ( Début : 2016-03-01)
voir toutes les theses

Publications Dblp


Publications DFIS


Publications HAL


100 The Price of Optimum: Complexity and Approximation for a Matching Game (, and ), In Algorithmica, Springer Verlag, volume 77, . [bibtex] [pdf] [doi]

99 Bi-objective matchings with the triangle inequality (, , and ), In Theoretical Computer Science, Elsevier, volume 670, . [bibtex] [pdf] [doi]

98 Conference Program Design with Single-Peaked and Single-Crossing Preferences (, and ), In 12th International Conference, WINE 2016, . [bibtex] [pdf] [doi]

97 A Boundary Property for Upper Domination (, , , , and ), In 27th International Workshop on Combinatorial Algorithms, IWOCA 2016, . [bibtex] [pdf] [doi]

96 Upper Domination: Complexity and Approximation (, , , , , , , , and ), In 27th International Workshop on Combinatorial Algorithms (IWOCA), volume 9843, . [bibtex] [pdf] [doi]

95 Achieving Proportional Representation in Conference Programs (, and ), In Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, . [bibtex] [pdf]

94 How Hard Is It for a Party to Nominate an Election Winner? (, , , and ), In Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, . [bibtex] [pdf]

93 Algorithmic Aspects of Upper Domination: A Parameterised Perspective (, , , , , , , , and ), In 11th International Conference Algorithmic Aspects in Information and Management (AAIM), volume 9778, . [bibtex] [pdf] [doi]

92 Computing Pareto Optimal Committees (, and ), In Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, . [bibtex] [pdf]

91 Optimal Reallocation under Additive and Ordinal Preferences (, , , and ), In 2016 International Conference on Autonomous Agents And Multiagent Systems, . [bibtex] [pdf]

90 Congestion Games with Capacitated Resources (, , and ), In Theory of Computing Systems, Springer Verlag, volume 57, . [bibtex] [pdf] [doi]

89 New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set (, , and ), In Theory of Computing Systems, Springer Verlag, volume 56, . [bibtex] [pdf] [doi]

88 On the maximum independent set problem in subclasses of subcubic graphs (, and ), In Journal of Discrete Algorithms, volume 31, . [bibtex] [pdf] [doi]

87 The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles (, , and ), In Theoretical Computer Science, volume 602, . [bibtex] [pdf] [doi]

86 Approximate tradeoffs on weighted labeled matroids (, and ), In Discrete Applied Mathematics, Elsevier, volume 184, . [bibtex] [pdf] [doi]

85 Worst case compromises in matroids with applications to the allocation of indivisible goods (, and ), In Theoretical Computer Science, volume 589, . [bibtex] [pdf] [doi]

84 A Dichotomy for Upper Domination in Monogenic Classes (, , , and ), In 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2014), Springer, volume 8881, . [bibtex] [pdf] [doi]

83 The Lazy Matroid Problem (, and ), In 8th IFIP International Conference on Theoretical Computer Science (TCS) (Josep Diaz, Ivan Lanese, Davide Sangiorgi, eds.), Springer, volume LNCS-8705, . [bibtex] [pdf] [doi]

82 Near Fairness in Matroids (, and ), In 21st European Conference on Artificial Intelligence (ECAI 2014), volume 263, . [bibtex] [pdf]

81 On regular and approximately fair allocations of indivisible goods (, and ), In 2014 international conference on Autonomous agents and multi-agent systems (AAMAS '14 ), . [bibtex] [pdf]

80 Un algorithme décentralisé pour construire une base d'un matroïde commune à un ensemble d'agents (, and ), In ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, . [bibtex] [pdf]

79 On the complexity of the selective graph coloring problem in some special classes of graphs (, , and ), In Theoretical Computer Science, volume 540-541, . [bibtex] [pdf] [doi]

78 A note on the Clustered Set Covering Problem ( and ), In Discrete Applied Mathematics, Elsevier, volume 164, Part 1, . [bibtex] [pdf] [doi]

77 A Protocol for Cutting Matroids Like Cakes (, and ), In 9th International Conference on Web and Internet Economics , WINE 2013, . [bibtex] [pdf] [doi]

76 Possible Winners in Approval Voting (, , and ), In Third International Conference, ADT 2013, . [bibtex] [pdf] [doi]

75 The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design (, and ), In 19th International Symposium, FCT 2013, . [bibtex] [pdf] [doi]

74 A matroid approach to the worst case allocation of indivisible goods (, and ), In 23rd international joint conference on Artificial Intelligence (IJCAI 2013), . [bibtex] [pdf]

73 On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs (, and ), In 24th International Workshop, IWOCA 2013, . [bibtex] [pdf] [doi]

72 Truthful many-to-many assignment with private weights (, , and ), In 8th International Conference on Algorithms and Complexity (CIAC 2013), Springer, volume 7878, . [bibtex] [pdf] [doi]

71 Approximation du point idéal dans des matroïdes: bornes et algorithmes (, and ), In 14e conférence de la société Française de Recherche Opérationnelle et Aide à la Décision (ROADEF 2013), . [bibtex] [pdf]

70 Resilience and optimization of identifiable bipartite graphs (, , and ), In Discrete Applied Mathematics, Elsevier, volume 161, . [bibtex] [pdf] [doi]

69 Complexity of trails, paths and circuits in arc-colored digraphs (, , and ), In Discrete Applied Mathematics, Elsevier, volume 161, . [bibtex] [pdf] [doi]

68 Fair solutions for some multiagent optimization problems (, and ), In Autonomous Agents and Multi-Agent Systems, volume 26, . [bibtex] [pdf] [doi]

67 Reoptimization under Vertex Insertion: Max Pk-Free Subgraph and Max Planar Subgraph (, and ), In Discrete Mathematics, Algorithms and Applications, volume 05, . [bibtex] [pdf] [doi]

66 Approximation with a fixed number of solutions of some multiobjective maximization problems (, and ), In Journal of Discrete Algorithms, volume 22, . [bibtex] [pdf] [doi]

65 Congestion games with capacitated resources (, , and ), In 5th International Symposium on Algorithmic Game Theory (SAGT 2012), volume 7615, . [bibtex] [pdf] [doi]

64 Cost allocation protocols for network formation on connection situations (, , and ), In 6th International Conference on Performance Evaluation Methodologies and Tools, . [bibtex] [pdf]

63 On paths, trails and closed trails in edge-colored graphs (, , and ), In Discrete Mathematics and Theoretical Computer Science, DMTCS, volume Vol. 14 no. 2, . [bibtex] [pdf]

62 Approximate Tradeoffs on Matroids (, and ), In 20th European Conference on Artificial Intelligence (ECAI 2012), . [bibtex] [pdf] [doi]

61 Complexity Results for the Empire Problem in Collection of Stars (, and ), In 6th International Conference on Combinatorial Optimization and Applications, COCOA 2012, . [bibtex] [pdf]

60 Selective Graph Coloring in Some Special Classes of Graphs (, , and ), In ISCO 2012, . [bibtex] [pdf] [doi]

59 Reoptimization of the Maximum Weighted Pk-Free Subgraph Problem under Vertex Insertion (, and ), In 6th International Workshop on Algorithm and Computation (WALCOM 2012), volume 7157, . [bibtex] [pdf] [doi]

58 Strategic Scheduling Games: Equilibria and Efficiency (, and ), Chapter in Just-in-Time Systems, . [bibtex] [pdf] [doi]

57 Strategic Coloring of a Graph (, and ), In Internet Mathematics, volume 8, . [bibtex] [pdf] [doi]

56 Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems (, and ), In 9th International Workshop on Approximation and Online Algorithms, WAOA 2011, . [bibtex] [pdf]

55 Reoptimization of maximum weight induced hereditary subgraph problems (, and ), . [bibtex] [pdf]

54 Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation (, , and ), In European Journal of Operational Research, Elsevier, volume 205, . [bibtex] [pdf] [doi]

53 Some tractable instances of interval data minmax regret problems: bounded distance from triviality (short version) (, and ), In 34th International Conference on Current Trends in Theory and Practice of Computer Science, Springer-Verlag, volume 4910, . [bibtex] [pdf] [doi]

52 Better differential approximation for symetric TSP ( and ), . [bibtex] [pdf]

51 A note on the hardness results for the labeled perfect matching problems in bipartite graphs (), . [bibtex] [pdf]

50 Some tractable instances of interval data minmax regret problems: bounded distance from triviality (, and ), . [bibtex] [pdf]

49 Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs (, and ), . [bibtex] [pdf]

48 The Complexity of Bottlemeck Labeled Graph Problems (, and ), . [bibtex] [pdf]

47 On the performance of congestion games for optimum satistiability problems (, , and ), . [bibtex] [pdf]

46 On the complexity of the exact weighted independent set problem ( and ), . [bibtex] [pdf]

45 On the complexity of the exact weighted independent set problem ( and ), . [bibtex] [pdf]

44 A note on the hardness results for the labeled perfect matching problems in bipartite graphs (), . [bibtex] [pdf]

43 Some tractable instances of interval data minmax regret problems: bounded distance from triviality (, and ), . [bibtex] [pdf]

42 Better differential approximation for symmetric TSP ( and ), . [bibtex] [pdf]

41 The complexity of Bottleneck Labeled Graph Problems (, and ), . [bibtex] [pdf]

40 Approximation results for the weighted $P\_{4}$ partition problem ( and ), In Journal of Discrete Algorithms, Elsevier, . [bibtex] [pdf] [doi]

39 Complexity and approximation results for bounded-size paths packing problems ( and ), Chapter in Combinatorial Optimization and Theoretical Computer Science Interfaces and Perspectives 30th anniversary of the LAMSADE (Vangelis Th. Paschos, ed.), ISTE, . [bibtex] [pdf]

38 The path partition problem and related problems in bipartite graphs ( and ), In Operations Research Letters, Elsevier, . [bibtex] [pdf] [doi]

37 Le voyageur de commerce et ses variations : un tour d'horizon de ses résolution ( and ), Chapter in Optimisation Combinatoire volume 5 problèmes paradigmatiques et nouvelles problématiques (Vangelis Th. Paschos, ed.), Hermes Science, . [bibtex] [pdf]

36 The complexity of the Pk partition problem and related problems in bipartite graphs ( and ), In Theory and Practice of Computer Science, LNCS 4362, . [bibtex] [pdf]

35 Weighted coloring on planar, bipartite and split graphs: complexity and approximation (, , , and ), . [bibtex] [pdf]

34 The labeled perfect matching in bipartite graphs (), . [bibtex] [pdf]

33 Weighted coloring: further complexity and approximability results (, and ), . [bibtex] [pdf]

32 (Non) -Approximability for the multi-criteria TSP (1,2) (, , and ), . [bibtex] [pdf]

31 Reoptimization of minimum and maximum traveling salesman's tours (février 2006) (, , and ), . [bibtex] [pdf]

30 Reoptimization of minimum and maximum travelling salesman's tours (, , and ), . [bibtex] [pdf]

29 A hypocoloring model for batch scheduling (, , and ), In Discrete Applied Mathematics, Elsevier, volume 146, . [bibtex] [pdf] [doi]

28 On the differential approximation of MIN SET COVER (juin 2004) (, , and ), . [bibtex] [pdf]

27 Approximation results for the weighted P4 partition problem ( and ), In FCT' 2005 The symposia on Fundamentals of Computation Theory (LNCS 3623, ed.), Springer Verlag, . [bibtex] [pdf] [doi]

26 The complexity of the Pk partition problem and related problems in bipartite graphs ( and ), In , Imperial College Press, . [bibtex] [pdf]

25 A simple approximation algorithm for WIS based on the approximability in $k$-partite graphs (), In European Journal of Operational Research, Elsevier, volume to appear, . [bibtex] [pdf]

24 The Labeled perfect matching in bipartite graphs (), In Information Processing Letters, Elsevier, volume to appear, . [bibtex] [pdf]

23 Approximation algorithms for the maximum Hamiltonian Path Problem with specified endpoint(s) (), In European Journal of Operational Research, Elsevier, volume 161, . [bibtex] [pdf]

22 The maximum saving partition problem ( and ), In Operation Research Letters, volume 33, . [bibtex] [pdf]

21 Differential approximations for min set cover (, , and ), In Theoretical Computer Science, Elsevier, volume 332, . [bibtex] [pdf]

20 Approximation algorithms for some vehicle routing problems (, and ), In Discrete Applied Mathematics, Elsevier, volume 146, . [bibtex] [pdf]

19 Algorithmes approchés pour le problème du voyageur de commerce multicritère (, , and ), In Proceedings of Roadef, . [bibtex] [pdf]

18 (Non)-approximability for the multi-criteria TSP(1,2) (, , and ), In Proceedings of Fundamentals of Computation Theory (FCT 2005), volume 3623, . [bibtex] [pdf] [doi]

17 Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation (, , , and ), In xxx, LNCS 3341-springer verlaag, . [bibtex] [pdf]

16 A simple approximation algorithm for WIS based on the approximability in k-partite graphs (), . [bibtex] [pdf]

15 Bottleneck shortest paths on a partially ordered scale ( and ), In 4OR: A Quarterly Journal of Operations Research, Springer Verlag, volume 1, . [bibtex] [pdf]

14 Differential approximation results for the traveling salesman problem with distances 1 and 2 (, and ), In European Journal of Operational Research, Elsevier, volume 145(3), . [bibtex] [pdf]

13 Optima locaux garantis pour l'approximation différentielle (, and ), In Techniques et Sciences Informatiquess, Editions Hermès, volume 22(3), . [bibtex] [pdf]

12 Local approximation for maximum H0-free partial subgraph problems (, and ), In Operations Research Letter, volume 31(3), . [bibtex] [pdf]

11 Differential approximation results for the Steiner tree problem (, and ), In Applied Mathematics Letters, Elsevier, volume 16, . [bibtex] [pdf]

10 Local search for the minimum label spanning tree problem with bounded color classes (, and ), In Operations Research Letters, Elsevier, volume 31, . [bibtex] [pdf]

9 Approximation polynomiale des problèmes NP-difficiles - Optima locaux et rapport différentiel (, and ), . [bibtex] [pdf]

8 Approximation algorithms for the traveling salesman problem (, and ), In Mathematical Models of Operations Research, volume 145/3, . [bibtex] [pdf]

7 Differential approximation of NP-hard problems with equal size feasible solutions (), In RAIRO - Operations Research, EDP Sciences, volume 36, . [bibtex] [pdf]

6 approximation results for the Traveling Salesman and related Problems (), In Information Processing Letters, Elsevier, volume 82, . [bibtex] [pdf]

5 Approximation results toward Nearest Neighbor heuristic (), In Yugoslav Journal of Operations Research, University of Belgrade, volume 12, . [bibtex] [pdf]

4 Approximation algorithms for the traveling salesman problem (, and ), In Mathematical Models of Operations Research, volume 56, . [bibtex] [pdf]

3 The maximum f-depth Spanning tree problem (), In Information Processing Letters, Elsevier, volume 80, . [bibtex] [pdf]

2 Maximizing the number of unused bins (, and ), In Foundations of Computing and Decision Sciences, volume 26, . [bibtex] [pdf]

1 Bridging gap between standard and differential polynomial approxiamtion: the case of bin-packing (, and ), In Applied Mathematics Letters, Elsevier, volume 12, . [bibtex] [pdf]