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


    82 Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse (, and ), In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) (Nicolas Ollinger, Heribert Vollmer, ed.), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, . [bibtex]

    81 Time-Approximation Trade-offs for Inapproximable Problems (, and ), In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) (Nicolas Ollinger, Heribert Vollmer, ed.), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, . [bibtex]

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

    79 Upper Domination : Complexity and Approximation (, , , , , , , , and ), In Combinatorial Algorithms. 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings (Veli Mäkinen, Simon J. Puglisi, Leena Salmela, ed.), Springer, . [bibtex]

    78 Algorithmic Aspects of Upper Domination: A Parameterized Perspective (, , , , , , , , and ), In Algorithmic Aspects in Information and Management. 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings (Riccardo Dondi, Guillaume Fertin, Giancarlo Mauri, ed.), Springer, . [bibtex]

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

    76 On Subexponential and FPT-Time Inapproximability (, , and ), In Algorithmica, volume 71, . [bibtex] [doi]

    75 New Results on Polynomial Inapproximability and Fixed Parameter Approximability of Edge Dominating Set (, , and ), In Theory of Computing Systems, volume 56, . [bibtex] [doi]

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

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

    72 On the MAX MIN VERTEX COVER problem (, and ), In Approximation and Online Algorithms 11th International Workshop, WAOA 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers (Pruhs, Kirk, ed.), Springer, . [bibtex]

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

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

    69 On Subexponential and FPT-time Inapproximability (, , and ), In Parameterized and Exact Computation 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers (Szeider, Stefan, ed.), Springer, . [bibtex]

    68 Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation (), In Optimization Theory, Decision Making, and Operations Research Applications (Stiakakis, Emmanuil, ed.), Springer, . [bibtex]

    67 Playing with Parameters: Cross-parameterization in Graphs (, , and ), Technical report, Cahiers du Lamsade, . [bibtex]

    66 Fast algorithms for min independent dominating set (, , and ), In Seventh International Conference on Graphs and Optimization 2010, Discrete Applied Mathematics, . [bibtex]

    65 Exact and approximation algorithms for densest k-subgraph (, , , and ), In WALCOM: Algorithms and Computation 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings (Tokuyama, Takeshi, ed.), Springer, . [bibtex]

    64 Reoptimization of maximum weight induced hereditary subgraph problems (, and ), In Theoretical Computer Science, volume 514, . [bibtex] [doi]

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

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

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

    60 Moderate exponential time approximation and branching algorithms (, and ), Technical report, Cahiers du Lamsade, . [bibtex]

    59 Approximating MAX SAT by moderately exponential algorithms (, and ), In Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings (Li, Angsheng, ed.), Springer, . [bibtex]

    58 Efficient Algorithms for the max k -vertex cover Problem ( and ), In Theoretical Computer Science 7th IFIP TC1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012, Proceedings (De Boer, Frank S., ed.), Springer, . [bibtex]

    57 The max quasi-independent set problem (, , , , and ), In Journal of Combinatorial Optimization, volume 23, . [bibtex] [doi]

    56 Fast Algorithms for max independent set (, , and ), In Algorithmica, volume 62, . [bibtex] [doi]

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

    54 Reoptimization of the Maximum Weighted Pk-Free Subgraph Problem under Vertex Insertion (, and ), In WALCOM: Algorithms and Computation 6th International Workshop (Rahman, Md. Saidur, ed.), Springer, . [bibtex]

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

    52 An emergency management model for a wireless sensor network problem (, and ), Technical report, Cahier du LAMSADE, . [bibtex]

    51 Using greediness for parameterization: the case of max and min (k, n − k)-cut (, , and ), Technical report, Cahiers du Lamsade, . [bibtex]

    50 Online maximum k-coverage (, , , and ), In Discrete Applied Mathematics, volume 160, . [bibtex] [doi]

    49 Online Maximum k-Coverage (, , , and ), In Fundamentals of Computation Theory, FCT 2011 (Steffen, Martin, ed.), Springer, . [bibtex]

    48 Approximation by Moderately Exponential Algorithms (), In ISCO International Symposium on Combinatorial Optimization (Mahjoub, Ali Ridha, ed.), Wiley, . [bibtex]

    47 A survey on combinatorial optimization in dynamic environments ( and ), In RAIRO, volume 45, . [bibtex] [doi]

    46 Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms (, and ), In Discrete Applied Mathematics, volume 159, . [bibtex] [doi]

    45 An Introduction to Exponential Time Exact Algorithms for Solving NP-hard Problems (, and ), Chapter in (Mahjoub, Ridha, ed.), Wiley-ISTE, . [bibtex]

    44 Optimization in dynamic environments ( and ), Technical report, Cahier du LAMSADE, . [bibtex]

    43 On the probabilistic min spanning tree problem (, and ), In Proceedings of the 2010 International Multiconference on Computer Science and Information Technology (IMCSIT), IEEE, . [bibtex]

    42 Probabilistic models for the Steiner Tree problem (, and ), In Networks, volume 56, . [bibtex] [doi]

    41 Well solved cases of probabilistic traveling salesman problem (, and ), . [bibtex]

    40 Polynomial approximation ( and ), Chapter in (Vangelis, Paschos, T., ed.), ISTE-Wiley, . [bibtex]

    39 Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537^n) (, , and ), In Theory and Applications of Models of Computation 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings (Li, Angsheng, ed.), Springer, . [bibtex]

    38 Combinatorial Optimization Volume 3, Applications of Combinatorial Optimization (), ISTE-Wiley, . [bibtex]

    37 Combinatorial optimization Volume 2, Paradigms of combinatorial optimization : problems and new approaches (), ISTE-Wiley, . [bibtex]

    36 Combinatorial optimization Volume 2, Paradigms of Combinatorial Optimization: problems and new approaches (), Wiley-VCH, . [bibtex]

    35 Combinatorial Optimization Volume 1, Concepts of Combinatorial Optimization (), Wiley-VCH, . [bibtex]

    34 Combinatorial Optimization Volume 3, Applications of Combinatorial Optimization (), Wiley-VCH, . [bibtex]

    33 Basic concepts in algorithms and complexity theory (), Chapter in (Vangelis, Paschos, T., ed.), ISTE-Wiley, . [bibtex]

    32 Approximation preserving reductions ( and ), Chapter in (Paschos, Vangelis, ed.), ISTE-Wiley, . [bibtex]

    31 Approximating the Metric 2-Peripatetic Salesman Problem (, and ), In Algorithmic Operations Research, volume 5, . [bibtex]

    30 A model for the design of a minimum-cost telecommunications network (, , and ), Chapter in (Paschos, Vangelis T., ed.), ISTE-Wiley, . [bibtex]

    29 A Survey on the Structure of Approximation Classes ( and ), In Computer Science Review, volume 4, . [bibtex] [doi]

    28 Probabilistic combinatorial optimization ( and ), Chapter in (Vangelis, Paschos, T., ed.), ISTE-Wiley, . [bibtex]

    27 Probabilistic optimization in graph-problems ( and ), In Algorithmic Operations Research, volume 15, . [bibtex]

    26 On the max-weight edge coloring problem (, and ), In Journal of Combinatorial Optimization, volume 20, . [bibtex] [doi]

    25 Approximating the max edge-coloring problem (, , and ), In Theoretical Computer Science, volume 411, . [bibtex] [doi]

    24 The Max Quasi-Independent Set Problem (, , , , and ), In Computer Science – Theory and Applications 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedings (Mayr, Ernst W., ed.), Springer, . [bibtex]

    23 Fast Algorithms for min independent dominating set (, and ), In Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings. (Patt-Shamir, Boaz, ed.), Springer, . [bibtex]

    22 A Bottom-Up Method and Fast Algorithms for max independent set (, and ), In 12th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings (Kaplan, Haim, ed.), Springer, . [bibtex]

    21 Fast Reoptimization for the Minimum Spanning Tree Problem ( and ), In Journal of Discrete Algorithms, volume 8, . [bibtex] [doi]

    20 Probabilistic graph-coloring in bipartite and split graphs (, , , and ), In Journal of Combinatorial Optimization, volume 17, . [bibtex] [doi]

    19 On the Maximum Edge Coloring Problem (Extended Abstract) (, and ), In Approximation and Online Algorithms 6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers (Skutella, Martin, ed.), Springer, . [bibtex]

    18 Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms (, and ), In Algorithms and Data Structures 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings (Toth, Csaba D., ed.), Springer, . [bibtex]

    17 Approximation of MIN COLORING by moderately exponential algorithms (, and ), In Information Processing Letters, volume 109, . [bibtex] [doi]

    16 Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 (, , , and ), In Discrete Applied Mathematics, volume 157, . [bibtex] [doi]

    15 An overview on polynomial approximation of NP-hard problems (), In Yugoslav Journal of Operations Research, volume 19, . [bibtex]

    14 Simple and fast reoptimizations for the Steiner tree problem (, and ), In Algorithmic Operations Research, volume 4, . [bibtex]

    13 Weighted coloring on planar, bipartite and split graphs: complexity and approximation (, , , and ), In Discrete Applied Mathematics, volume 157, . [bibtex] [doi]

    12 Exact Algorithms for Dominating Clique Problems (, , and ), In ISAAC 2009 20th International Symposium on Algorithms and Computation (Ibarra, Oscar H., ed.), Springer, . [bibtex]

    11 Greedy algorithms for on-line set-covering (, , and ), In Algorithmic Operations Research, volume 4, . [bibtex]

    10 Efficient approximation of MIN SET COVER by moderately exponential algorithms (, and ), In Theoretical Computer Science, volume 410, . [bibtex] [doi]

    9 Approximating the max edge-coloring problem (, , and ), In Combinatorial Algorithms 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28–July 2, 2009, Revised Selected Papers (Miller, Mirka, ed.), Springer, . [bibtex]

    8 Reoptimization of minimum and maximum traveling salesman's tours (, , and ), In Journal of Discrete Algorithms, volume 7, . [bibtex] [doi]

    7 Studying graph-stability to apprehend relative hardness of constructive -non constructive approximation (), In Bulletin of the Greek Mathematical Society, volume 43, . [bibtex]

    6 Approximation polynomiale : notions de difficulté et leur impact pour étudier la structure de NP ( and ), Technical report, Cahier du LAMSADE, . [bibtex]

    5 A neural network for the minimum set covering problem (, and ), In Chaos, Solitons and Fractals, volume 11, . [bibtex] [doi]

    4 On-line maximum-order induced hereditary subgraph problems (, and ), In SOFSEM 2000: Theory and Practice of Informatics SOFSEM 2000: Theory and Practice of Informatics 27th Conference on Current Trends in Theory and Practice of Informatics Milovy, Czech Republic, November 25 - December 2, 2000 Proceedings (Wiedermann, Jiri, ed.), Springer, . [bibtex]

    3 Un nouveau modèle pour la construction de réseau de télécommunication à coût minimum (, , and ), Technical report, Cahier du LAMSADE, . [bibtex]

    2 Sur la convergence d'un système différentiel de premier ordre, vectoriel, ordinaire, linéaire non-homogene et non-autonome ( and ), Technical report, Note de recherche du LAMSADE, . [bibtex]

    1 Master-slave strategies and polynomial approximation ( and ), In Computational Optimization and Applications, volume 16, . [bibtex]

    Publications HAL