## Membres

publié le , mis à jour le

retour a la liste des membres

## Vangelis Paschos

Tel : +33144054582
Bureau : P643
Pole : Optimisation combinatoire algorithmique
Status : Professeur

• Membre du conseil de departement MIDO
• Membre du conseil scientifique
• Expert IUF senior

• ### Encadrement de these de doctorat :

voir toutes les theses

### Publications HAL

126 Average-case complexity of a branch-and-bound algorithm for max independent set under the G(n,p) random model (, , and ), .

125 Exact and superpolynomial approximation algorithms for the densest $k$-subgraph problem (, , , and ), In European Journal of Operational Research, Elsevier, volume 262, .

124 Upper Domination: Complexity and Approximation (, , , , , , , , and ), In 27th International Workshop on Combinatorial Algorithms (IWOCA), volume 9843, .

123 Algorithmic Aspects of Upper Domination: A Parameterised Perspective (, , , , , , , , and ), In 11th International Conference Algorithmic Aspects in Information and Management (AAIM), volume 9778, .

122 Time-Approximation Trade-offs for Inapproximable Problems (, and ), In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), .

121 Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse (, and ), In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), .

120 Super-polynomial approximation branching algorithms (, and ), In RAIRO - Operations Research, EDP Sciences, volume 50, .

119 Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems (, and ), In RAIRO - Theoretical Informatics and Applications, volume 50, .

118 A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs (, , and ), In LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Springer, volume 9644, .

117 On Subexponential and FPT-Time Inapproximability (, , and ), In Algorithmica, Springer Verlag, volume 71, .

116 Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization (, , and ), In Algorithmica, Springer Verlag, volume 71, .

115 New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set (, , and ), In Theory of Computing Systems, Springer Verlag, volume 56, .

114 When polynomial approximation meets exact computation (), In 4OR, volume 13, .

113 Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the $\mathcal{G}(n,p)$ random model (, , and ), .

112 Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms (, and ), In Theoretical Computer Science, Elsevier, volume 560, .

111 Efficient algorithms for the Max k-Vertex Cover problem ( and ), In Journal of Combinatorial Optimization, Springer Verlag, volume 28, .

110 On the MAX MIN VERTEX COVER problem (, and ), .

109 Playing with Parameters: Cross-parameterization in Graphs (, , and ), .

108 On Subexponential and FPT-time Inapproximability (, , and ), In 8th International Symposium, IPEC 2013, .

107 Parameterized algorithms for the max k-set cover and related satisfiability problems (, and ), .

106 On the MAX MIN VERTEX COVER problem (, and ), In 11th International Workshop on Approximation and Online Algorithms, WAOA 2013, .

105 Fast algorithms for min independent dominating set (, , and ), In Discrete Applied Mathematics, Elsevier, volume 161, .

104 Weighted completion time minimization on a single-machine with a fixed non-availability interval: Differential approximability ( and ), In Discrete Optimization, Elsevier, volume 10, .

103 Exponential approximation schemata for some network design problems (, , and ), In Journal of Discrete Algorithms, volume 22, .

102 Reoptimization under Vertex Insertion: Max Pk-Free Subgraph and Max Planar Subgraph (, and ), In Discrete Mathematics, Algorithms and Applications, volume 05, .

101 Moderate exponential time approximation and branching algorithms (, and ), .

100 Using greediness for parameterization: the case of max and min (k, n – k)-cut (, , and ), .

99 Efficient Algorithms for the max k -vertex cover Problem ( and ), In 7th International Conference on Theoretical Computer Science (TCS) (Jos C. M. Baeten, Tom Ball, Frank S. Boer, eds.), Springer, volume LNCS-7604, .

98 An emergency management model for a wireless sensor network problem (, and ), .

97 Exact and approximation algorithms for densest k-subgraph (, , , and ), .

96 Approximating MAX SAT by moderately exponential algorithms (, and ), In 9th Annual Conference on Theory and Applications of Models of Computation , TAMC 2012, .

95 Subexponential and FPT-time Inapproximability of Independent Set and Related Problems (, and ), .

94 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, .

93 Reoptimization of the minimum spanning tree ( and ), In Wiley Interdisciplinary Reviews: Computational Statistics, volume 4, .

92 Combinatorial Optimization Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers (, , and ), Springer, .

91 Fast Algorithms for max independent set (, , and ), In Algorithmica, Springer Verlag, volume 62, .

90 Algorithms for dominating clique problems (, , and ), In Theoretical Computer Science, volume 459, .

89 On the probabilistic min spanning tree Problem (, and ), In Journal of Mathematical Modelling and Algorithms, Springer Verlag, volume 11, .

88 Optimization in dynamic environments ( and ), .

87 Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation (), In 1st International Symposium and 10th Balkan Conference on Operational Research (BALCOR 2011), .

86 Reoptimization of maximum weight induced hereditary subgraph problems (, and ), .

85 Approximating MAX SAT by moderately exponential algorithms (, and ), .

84 Exponential approximation schemata for some network design problems (, , and ), .

83 On the PROBABILISTIC MIN SPANNING TREE problem (, and ), .

82 On the MAX k-VERTEX COVER problem ( and ), .

81 Weighted completion time minimization on a single-machine with a fixed non-availability interval: differential approximability ( and ), .

80 Ressources informatiques : encore une histoire de temps ! (, , , and ), Chapter in Les Ressources (unknown editor, ed.), Institut Universitaire de France, .

79 Online maximum k-coverage (, , , and ), .

78 Fast algorithms for min independent dominating set (, , and ), In Seventh International Conference on Graphs and Optimization 2010, volume 161, .

77 The max quasi-independent set problem (, , , , and ), .

76 well solved cases of probabilistic traveling salesman problem (, and ), In 42èmes Journées de Statistique, .

75 Fast algorithms for max independent set (, , and ), .

74 Exact algorithms for dominating clique problems (, , and ), .

73 Approximating the max edge-coloring problem (, , and ), .

72 Fast reoptimization for the minimum spanning tree problem ( and ), .

71 Efficient approximation of MIN COLORING by moderately exponential algorithms (, and ), .

70 Efficient approximation of MIN SET COVER by "low-complexity" exponential algorithms (, and ), .

69 Fast algorithms for max independent set in graphs of small average degree (, , and ), .

68 Fast algorithms for MAX INDEPENDENT SET in graphs of small average degree (, , and ), .

67 An improved exact algorithm for maximum independent set in sparse graphs (, and ), .

66 An improved exact algorithm for maximum independent set in sparse graphs (, and ), .

65 Effcient approximation by "low-complexity" exponential algorithms (, and ), .

64 Efficient approximation by "low-complexity" exponential algorithms (, and ), .

63 An overview on polynomial approximation of NP-hard problems (), .

62 A robust 2-stage version for the STEINER TREE problem (, and ), .

61 Structures des classes d'approximation : un état de l'art ( and ), .

60 Probabilistic graph-coloring in bipartite and split graphs (Exented version of cahier du LAMSADE 218) (, , , and ), .

59 On the performance of congestion games for optimum satistiability problems (, , and ), .

58 Probabilistic models for the STEINER TREE problem (, and ), .

57 An axiomatic analysis of concordance-discordance relations (), .

56 On the max-weight edge coloring problem (, and ), .

55 Simple and fast reoptimizations for the Steiner tree problem (, and ), .

54 Probabilistic graph-coloring in bipartite and split graphs (, , , and ), .

53 A survey on the structure of approximation classes ( and ), .

52 Probabilistic models for the STEINER TREE problem (, and ), .

51 On the max-weight edge coloring problem (, and ), .

50 Un tour d'horizon sur quelques classes de jeux combinatoires (juin 2006) ( and ), .

49 Structures des classes d'approximation : un état de l'art ( and ), .

48 Simple and fast reoptimizations for the Steiner tree problem (, and ), .

47 Greedy algorithms for on-line set-covering (, and ), .

46 Weighted coloring on planar, bipartite and split graphs: complexity and approximation (, , , and ), .

45 Weighted coloring: further complexity and approximability results (, and ), .

44 An exact algorithm for MAX-CUT in sparse graphs (, and ), .

43 Exploiting dominance conditions for computing worst-case time upper bounds in bounded combinatorial optimization problems:application to MIN SET COVERING and MAX CUT ( and ), .

42 Un tour d'horizon sur quelques classes de jeux combinatoires ( and ), .

41 What about future? Robustness under vertex-uncertainty in graph-problems ( and ), .

40 Reoptimization of minimum and maximum traveling salesman's tours (février 2006) (, , and ), .

39 What about future? Robustness under vertex-uncertainty in graph-problems ( and ), .

38 On-line models for set-covering: the power of greediness (, and ), .

37 Improved worst-case complexity for the MIN 3-SET COVERING problem (janvier 2006) (, and ), .

36 Improved worst-case complexity for the MIN 3-SET COVERING problem (, and ), .

35 Approximability preserving reductions (septembre 2005) ( and ), .

34 Completeness in approximation classes beyong APX (septembre 2005) ( and ), .

33 Differential approximation(septembre 2005) ( and ), .

32 Completeness in approximation classes beyond APX ( and ), .

31 Differential approximation ( and ), .

30 Approximability preserving reduction ( and ), .

29 Reoptimization of minimum and maximum travelling salesman's tours (, , and ), .

28 A hypocoloring model for batch scheduling (, , and ), In Discrete Applied Mathematics, Elsevier, volume 146, .

27 Thoughts about new notions for the analysis of approximation algorithms ( and ), .

26 Lower bounds on the approximation ratios of leading heuristics for the single machine total tardiness problem (, and ), .

25 Completeness in differential approximation classes (, , and ), .

24 Probabilistic coloring of bipartite and split graphs (, , and ), .

23 Differential approximation of MIN SAT, MAX SAT and related problems ( and ), .

22 Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness (, and ), .

21 On the differential approximation of MIN SET COVER (juin 2004) (, , and ), .

20 Differential approximations for min set cover (, , and ), In Theoretical Computer Science, Elsevier, volume 332, .

19 Differential approximation of MIN SAT, MAX SAT and related problems ( and ), .

18 Differential approximation of MIN SAT, MAX SAT and related problems ( and ), .

17 On-line models and algorithms for MAX INDEPENDENT SET ( and ), .

16 An Alternative proof of SAT NP-Completeness ( and ), .

15 Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation (, , , and ), In xxx, LNCS 3341-springer verlaag, .

14 Algorithms for the On-Line Quota Traveling Salesman Problem (, , and ), .

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

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

11 Local approximation for maximum H0-free partial subgraph problems (, and ), In Operations Research Letter, volume 31(3), .

10 Differential approximation results for the Steiner tree problem (, and ), In Applied Mathematics Letters, Elsevier, volume 16, .

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

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

7 Approximation algorithms for the traveling salesman problem (, and ), In Mathematical Models of Operations Research, volume 56, .

6 Maximizing the number of unused bins (, and ), In Foundations of Computing and Decision Sciences, volume 26, .

5 Master-slave strategy and polynomial approximation ( and ), In Computational Optimization and Applications, Springer Verlag, volume 16, .

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

3 Approximating minimum spanning tree of depth two ( and ), In International Transactions in Operational Research, Wiley, volume 6, .

2 On the approximation of some spanning arborescence problems ( and ), In ISCIS XIII, .

1 Approximating the minimum weighted rooted spanning tree with radius less than two ( and ), In EURO XV, INFORMS XXXIV, .