Nos tutelles

CNRS Dauphine PSL *

Rechercher





Accueil > PERSONNES

Membres

publié le , mis à jour le

retour a la liste des membres

Vangelis Paschos

Email : vangelis.paschos@lamsade.dauphine.fr

Tel : +33144054582
Bureau : P643
Site Personnel: http://www.lamsade.dauphine.fr/~paschos
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 Dblp


    Publications DFIS


    Publications HAL


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

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

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

    123 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]

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

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

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

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

    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, . [bibtex] [pdf] [doi]

    117 On Subexponential and FPT-Time Inapproximability (, , and ), In Algorithmica, Springer Verlag, volume 71, . [bibtex] [pdf] [doi]

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

    115 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]

    114 When polynomial approximation meets exact computation (), In 4OR, volume 13, . [bibtex] [pdf] [doi]

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

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

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

    110 On the MAX MIN VERTEX COVER problem (, and ), . [bibtex] [pdf]

    109 Playing with Parameters: Cross-parameterization in Graphs (, , and ), . [bibtex] [pdf]

    108 On Subexponential and FPT-time Inapproximability (, , and ), In 8th International Symposium, IPEC 2013, . [bibtex] [pdf] [doi]

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

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

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

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

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

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

    101 Moderate exponential time approximation and branching algorithms (, and ), . [bibtex] [pdf]

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

    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, . [bibtex] [pdf] [doi]

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

    97 Exact and approximation algorithms for densest k-subgraph (, , , and ), . [bibtex] [pdf]

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

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

    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, . [bibtex] [pdf] [doi]

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

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

    91 Fast Algorithms for max independent set (, , and ), In Algorithmica, Springer Verlag, volume 62, . [bibtex] [pdf] [doi]

    90 Algorithms for dominating clique problems (, , and ), In Theoretical Computer Science, volume 459, . [bibtex] [pdf] [doi]

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

    88 Optimization in dynamic environments ( and ), . [bibtex] [pdf]

    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), . [bibtex] [pdf]

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

    85 Approximating MAX SAT by moderately exponential algorithms (, and ), . [bibtex] [pdf]

    84 Exponential approximation schemata for some network design problems (, , and ), . [bibtex] [pdf]

    83 On the PROBABILISTIC MIN SPANNING TREE problem (, and ), . [bibtex] [pdf]

    82 On the MAX k-VERTEX COVER problem ( and ), . [bibtex] [pdf]

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

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

    79 Online maximum k-coverage (, , , and ), . [bibtex] [pdf]

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

    77 The max quasi-independent set problem (, , , , and ), . [bibtex] [pdf]

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

    75 Fast algorithms for max independent set (, , and ), . [bibtex] [pdf]

    74 Exact algorithms for dominating clique problems (, , and ), . [bibtex] [pdf]

    73 Approximating the max edge-coloring problem (, , and ), . [bibtex] [pdf]

    72 Fast reoptimization for the minimum spanning tree problem ( and ), . [bibtex] [pdf]

    71 Efficient approximation of MIN COLORING by moderately exponential algorithms (, and ), . [bibtex] [pdf]

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

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

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

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

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

    65 Effcient approximation by "low-complexity" exponential algorithms (, and ), . [bibtex] [pdf]

    64 Efficient approximation by "low-complexity" exponential algorithms (, and ), . [bibtex] [pdf]

    63 An overview on polynomial approximation of NP-hard problems (), . [bibtex] [pdf]

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

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

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

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

    58 Probabilistic models for the STEINER TREE problem (, and ), . [bibtex] [pdf]

    57 An axiomatic analysis of concordance-discordance relations (), . [bibtex] [pdf]

    56 On the max-weight edge coloring problem (, and ), . [bibtex] [pdf]

    55 Simple and fast reoptimizations for the Steiner tree problem (, and ), . [bibtex] [pdf]

    54 Probabilistic graph-coloring in bipartite and split graphs (, , , and ), . [bibtex] [pdf]

    53 A survey on the structure of approximation classes ( and ), . [bibtex] [pdf]

    52 Probabilistic models for the STEINER TREE problem (, and ), . [bibtex] [pdf]

    51 On the max-weight edge coloring problem (, and ), . [bibtex] [pdf]

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

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

    48 Simple and fast reoptimizations for the Steiner tree problem (, and ), . [bibtex] [pdf]

    47 Greedy algorithms for on-line set-covering (, and ), . [bibtex] [pdf]

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

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

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

    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 ), . [bibtex] [pdf]

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

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

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

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

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

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

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

    35 Approximability preserving reductions (septembre 2005) ( and ), . [bibtex] [pdf]

    34 Completeness in approximation classes beyong APX (septembre 2005) ( and ), . [bibtex] [pdf]

    33 Differential approximation(septembre 2005) ( and ), . [bibtex] [pdf]

    32 Completeness in approximation classes beyond APX ( and ), . [bibtex] [pdf]

    31 Differential approximation ( and ), . [bibtex] [pdf]

    30 Approximability preserving reduction ( and ), . [bibtex] [pdf]

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

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

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

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

    25 Completeness in differential approximation classes (, , and ), . [bibtex] [pdf]

    24 Probabilistic coloring of bipartite and split graphs (, , and ), . [bibtex] [pdf]

    23 Differential approximation of MIN SAT, MAX SAT and related problems ( and ), . [bibtex] [pdf]

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

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

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

    19 Differential approximation of MIN SAT, MAX SAT and related problems ( and ), . [bibtex] [pdf]

    18 Differential approximation of MIN SAT, MAX SAT and related problems ( and ), . [bibtex] [pdf]

    17 On-line models and algorithms for MAX INDEPENDENT SET ( and ), . [bibtex] [pdf]

    16 An Alternative proof of SAT NP-Completeness ( and ), . [bibtex] [pdf]

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

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

    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), . [bibtex] [pdf]

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

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

    10 Differential approximation results for the Steiner tree problem (, and ), In Applied Mathematics Letters, Elsevier, volume 16, . [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 Approximation algorithms for the traveling salesman problem (, and ), In Mathematical Models of Operations Research, volume 56, . [bibtex] [pdf]

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

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

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

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

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

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