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


    • Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos
      Exact and superpolynomial approximation algorithms for the densest k-subgraph problem.European Journal of Operational Research262(3) 2017:894-903

    • Édouard Bonnet, Vangelis Th. Paschos
      Dual parameterization and parameterized approximability of subset graph problems.RAIRO - Operations Research51(1) 2017:261-266

    • Dimitris Fotakis, Aris Pagourtzis, Vangelis Th. Paschos
      Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, ProceedingsCIAC 2017:

    • Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos
      Structural Parameters, Tight Bounds, and Approximation for (k, r)-Center.CoRRabs/1704.08868 2017:

    • Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos
      Structurally Parameterized $d$-Scattered Set.CoRRabs/1709.02180 2017:

    • Édouard Bonnet, Vangelis Th. Paschos, Florian Sikora
      Parameterized exact and approximation algorithms for maximum -set cover and related satisfiability problems.RAIRO - Theor. Inf. and Applic.50(3) 2016:227-240

    • Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire
      Super-polynomial approximation branching algorithms.RAIRO - Operations Research50(4-5) 2016:979-994

    • Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos
      Algorithmic Aspects of Upper Domination: A Parameterised Perspective.AAIM 2016:113-124

    • Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos
      Upper Domination: Complexity and Approximation.IWOCA 2016:241-252

    • Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis
      A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs.LATIN 2016:235-248

    • Édouard Bonnet, Michael Lampis, Vangelis Th. Paschos
      Time-Approximation Trade-offs for Inapproximable Problems.STACS 2016:22:1-22:14

    • Dimitris Fotakis, Michael Lampis, Vangelis Th. Paschos
      Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse.STACS 2016:37:1-37:14

    • Vangelis Th. Paschos
      When polynomial approximation meets exact computation.4OR13(3) 2015:227-245

    • Edouard Bonnet, Bruno Escoffier, Eun Jung Kim 0002, Vangelis Th. Paschos
      On Subexponential and FPT-Time Inapproximability.Algorithmica71(3) 2015:541-565

    • Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire
      Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization.Algorithmica71(3) 2015:566-580

    • Nicolas Boria, Federico Della Croce, Vangelis Th. Paschos
      On the max min vertex cover problem.Discrete Applied Mathematics196 2015:62-71

    • Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos, Mingyu Xiao
      New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set.Theory Comput. Syst.56(2) 2015:330-346

    • Vangelis Th. Paschos, Peter Widmayer
      Algorithms and Complexity - 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. ProceedingsCIAC 2015:

    • Edouard Bonnet, Michael Lampis, Vangelis Th. Paschos
      Time-Approximation Trade-offs for Inapproximable Problems.CoRRabs/1502.05828 2015:

    • Vangelis Th. Paschos
      Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio~0.7.CoRRabs/1502.07930 2015:

    • Nicolas Bourgeois, R. Catellier, Tom Denat, Vangelis Th. Paschos
      Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the $\mathcal{G}(n, p)$ random model.CoRRabs/1505.04969 2015:

    • Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos
      Algorithmic Aspects of Upper Domination.CoRRabs/1506.07260 2015:

    • Dimitris Fotakis, Michael Lampis, Vangelis Th. Paschos
      Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse.CoRRabs/1507.04391 2015:

    • Federico Della Croce, Vangelis Th. Paschos
      Efficient algorithms for the max k-vertex cover problem.J. Comb. Optim.28(3) 2014:674-691

    • Edouard Bonnet, Vangelis Th. Paschos
      Parameterized (in)approximability of subset problems.Oper. Res. Lett.42(3) 2014:222-225

    • Vangelis Markakis, Ioannis Milis, Vangelis Th. Paschos
      Special Issue: "Combinatorial Optimization: Theory of Algorithms and Complexity".Theor. Comput. Sci.540 2014:1

    • Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire
      Approximating MAX SAT by moderately exponential and parameterized algorithms.Theor. Comput. Sci.560 2014:147-157

    • Pierre Fouilhoux, Luis Eduardo Neves Gouveia, Ali Ridha Mahjoub, Vangelis Th. Paschos
      Combinatorial Optimization - Third International Symposium, ISCO 2014, Lisbon, Portugal, March 5-7, 2014, Revised Selected PapersISCO 2014:

    • Edouard Bonnet, Vangelis Th. Paschos
      Sparsification and subexponential approximation.CoRRabs/1402.2843 2014:

    • Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis
      On the approximation of maximum $k$-vertex cover in bipartite graphs.CoRRabs/1409.6952 2014:

    • Nicolas Bourgeois, Federico Della Croce, Bruno Escoffier, Vangelis Th. Paschos
      Fast algorithms for min independent dominating set.Discrete Applied Mathematics161(4-5) 2013:558-572

    • Imed Kacem, Vangelis Th. Paschos
      Weighted completion time minimization on a single-machine with a fixed non-availability interval: Differential approximability.Discrete Optimization10(1) 2013:61-68

    • Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos
      Reoptimization under Vertex Insertion: Max P-Free Subgraph and Max Planar Subgraph.Discrete Math., Alg. and Appl.5(2) 2013:

    • Nicolas Boria, Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos
      Exponential approximation schemata for some network design problems.J. Discrete Algorithms22 2013:43-52

    • Vangelis Th. Paschos
      Preface.Theor. Comput. Sci.511 2013:1

    • Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos
      Reoptimization of maximum weight induced hereditary subgraph problems.Theor. Comput. Sci.514 2013:61-74

    • Nicolas Boria, Cécile Murat, Vangelis Th. Paschos
      The Probabilistic Min Dominating Set Problem.CSR 2013:298-309

    • Edouard Bonnet, Bruno Escoffier, Eun Jung Kim 0002, Vangelis Th. Paschos
      On Subexponential and FPT-Time Inapproximability.IPEC 2013:54-65

    • Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire
      Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization.IPEC 2013:66-77

    • Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos
      Exact and Approximation Algorithms for Densest -Subgraph.WALCOM 2013:114-125

    • Nicolas Boria, Federico Della Croce, Vangelis Th. Paschos
      On the max min vertex cover Problem.WAOA 2013:37-48

    • Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire
      Multi-parameter complexity analysis for constrained size graph problems: using greediness for parameterization.CoRRabs/1306.2217 2013:

    • Edouard Bonnet, Vangelis Th. Paschos, Florian Sikora
      Multiparameterizations for max $k$-set cover and related satisfiability problems.CoRRabs/1309.4718 2013:

    • Nicolas Bourgeois, Konrad Dabrowski, Marc Demange, Vangelis Th. Paschos
      Playing with Parameters: Cross-parameterization in Graphs.CoRRabs/1309.6144 2013:

    • Edouard Bonnet, Vangelis Th. Paschos
      Parameterized (in)approximability of subset problems.CoRRabs/1310.5576 2013:

    • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij
      Fast Algorithms for max independent set.Algorithmica62(1-2) 2012:382-415

    • Giorgio Ausiello, Nicolas Boria, Aristotelis Giannakos, Giorgio Lucarelli, Vangelis Th. Paschos
      Online maximum k-coverage.Discrete Applied Mathematics160(13-14) 2012:1901-1913

    • Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos, O. Pottié
      The max quasi-independent set problem.J. Comb. Optim.23(1) 2012:94-117

    • Nicolas Boria, Cécile Murat, Vangelis Th. Paschos
      On the probabilistic min spanning tree Problem.J. Math. Model. Algorithms11(1) 2012:45-76

    • Nicolas Bourgeois, Federico Della Croce, Bruno Escoffier, Vangelis Th. Paschos
      Algorithms for dominating clique problems.Theor. Comput. Sci.459 2012:77-88

    • Federico Della Croce, Vangelis Th. Paschos
      Efficient Algorithms for the max k -vertex cover Problem.IFIP TCS 2012:295-309

    • Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos, Mingyu Xiao
      New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set.IPEC 2012:25-36

    • Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos
      Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems.LATIN 2012:73-84

    • Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire
      Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms.TAMC 2012:202-213

    • Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos
      Reoptimization of the Maximum Weighted P k -Free Subgraph Problem under Vertex Insertion.WALCOM 2012:76-87

    • Ali Ridha Mahjoub, Vangelis Markakis, Ioannis Milis, Vangelis Th. Paschos
      Combinatorial Optimization - Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected PapersISCO 2012:

    • Bruno Escoffier, Eun Jung Kim 0002, Vangelis Th. Paschos
      Subexponential and FPT-time Inapproximability of Independent Set and Related ProblemsCoRRabs/1211.6656 2012:

    • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos
      Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms.Discrete Applied Mathematics159(17) 2011:1954-1970

    • Nicolas Boria, Vangelis Th. Paschos
      A survey on combinatorial optimization in dynamic environments.RAIRO - Operations Research45(3) 2011:241-294

    • Giorgio Ausiello, Nicolas Boria, Aristotelis Giannakos, Giorgio Lucarelli, Vangelis Th. Paschos
      Online Maximum k-Coverage.FCT 2011:181-192

    • Federico Della Croce, Vangelis Th. Paschos, Roberto Wolfler Calvo
      Approximating the metric 2-Peripatetic Salesman Problem.Algorithmic Operations Research5(1) 2010:13-20

    • Cécile Murat, Vangelis Th. Paschos
      Probabilistic optimization in graph-problems.Algorithmic Operations Research5(1) 2010:49-64

    • Bruno Escoffier, Vangelis Th. Paschos
      A survey on the structure of approximation classes.Computer Science Review4(1) 2010:19-40

    • Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos
      On the max-weight edge coloring problem.J. Comb. Optim.20(4) 2010:429-442

    • Nicolas Boria, Vangelis Th. Paschos
      Fast reoptimization for the minimum spanning tree problem.J. Discrete Algorithms8(3) 2010:296-310

    • Vangelis Th. Paschos, Orestis Telelis, Vassilis Zissimopoulos
      Probabilistic models for the Steiner Tree problem.Networks56(1) 2010:39-49

    • Nicolas Bourgeois, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos
      Approximating the max-edge-coloring problem.Theor. Comput. Sci.411(34-36) 2010:3055-3067

    • Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos, O. Pottié
      The max quasi-independent set Problem.CSR 2010:60-71

    • Nicolas Boria, Cécile Murat, Vangelis Th. Paschos
      On the Probabilistic min spanning tree problem.IMCSIT 2010:893-900

    • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos
      Fast Algorithms for min independent dominating set.SIROCCO 2010:247-261

    • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij
      A Bottom-Up Method and Fast Algorithms for max independent set.SWAT 2010:62-73

    • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij
      Maximum Independent Set in Graphs of Average Degree at Most Three in (1.08537){\mathcal O}(1.08537^n).TAMC 2010:373-384

    • Giorgio Ausiello, Nicolas Bourgeois, Telis Giannakos, Vangelis Th. Paschos
      Greedy Algorithms For On-Line Set-Covering.Algorithmic Operations Research4(1) 2009:36-48

    • Bruno Escoffier, Martin Milanic, Vangelis Th. Paschos
      Simple and Fast Reoptimizations for the Steiner Tree Problem.Algorithmic Operations Research4(2) 2009:86-94

    • Dominique de Werra, Marc Demange, Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos
      Weighted coloring on planar, bipartite and split graphs: Complexity and approximation.Discrete Applied Mathematics157(4) 2009:819-832

    • Alexey Baburin, Federico Della Croce, Edward Gimadi, Y. V. Glazkov, Vangelis Th. Paschos
      Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2.Discrete Applied Mathematics157(9) 2009:1988-1992

    • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos
      Approximation of min coloring by moderately exponential algorithms.Inf. Process. Lett.109(16) 2009:950-954

    • Nicolas Bourgeois, Federico Della Croce, Bruno Escoffier, Cécile Murat, Vangelis Th. Paschos
      Probabilistic graph-coloring in bipartite and split graphs.J. Comb. Optim.17(3) 2009:274-311

    • Giorgio Ausiello, Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos
      Reoptimization of minimum and maximum traveling salesman's tours.J. Discrete Algorithms7(4) 2009:453-463

    • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos
      Efficient approximation of min set cover by moderately exponential algorithms.Theor. Comput. Sci.410(21-23) 2009:2184-2195

    • Nicolas Bourgeois, Federico Della Croce, Bruno Escoffier, Vangelis Th. Paschos
      Exact Algorithms for Dominating Clique Problems.ISAAC 2009:4-13

    • Nicolas Bourgeois, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos
      Approximating the Max Edge-Coloring Problem.IWOCA 2009:83-94

    • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos
      Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms.WADS 2009:507-518

    • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij
      Fast Algorithms for Max Independent Set in Graphs of Small Average DegreeCoRRabs/0901.1563 2009:

    • Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos
      Max Edge Coloring of TreesCoRRabs/0901.4002 2009:

    • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos
      Fast algorithms for min independent dominating setCoRRabs/0905.1993 2009:

    • Vangelis Th. Paschos
      Combinatorial Optimization and Theoretical Computer Science - Interfaces and Perspectives: 30th Anniversary of the LAMSADE. 2008:1-515

    • Federico Della Croce, Vangelis Th. Paschos
      Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems.Operational Research8(3) 2008:235-256

    • Cécile Murat, Vangelis Th. Paschos
      Vertex-Uncertainty in Graph-Problems.COCOA 2008:139-148

    • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos
      An O*(1.0977) Exact Algorithm for max independent set in Sparse Graphs.IWPEC 2008:55-65

    • Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos
      On the Maximum Edge Coloring Problem.WAOA 2008:279-292

    • Bruno Escoffier, Vangelis Th. Paschos
      Differential approximation of min sat.European Journal of Operational Research181(2) 2007:620-633

    • Federico Della Croce, Bruno Escoffier, Vangelis Th. Paschos
      Improved worst-case complexity for the MIN 3-SET COVERING problem.Oper. Res. Lett.35(2) 2007:205-210

    • Federico Della Croce, Marcin Jakub Kaminski, Vangelis Th. Paschos
      An exact algorithm for MAX-CUT in sparse graphs.Oper. Res. Lett.35(3) 2007:403-408

    • Marc Demange, Dominique de Werra, Jérôme Monnot, Vangelis Th. Paschos
      Time slot scheduling of compatible jobs.J. Scheduling10(2) 2007:111-127

    • Vangelis Th. Paschos, Orestis Telelis, Vassilis Zissimopoulos
      Steiner Forests on Stochastic Metric Graphs.COCOA 2007:112-123

    • Aristotelis Giannakos, Laurent Gourvès, Jérôme Monnot, Vangelis Th. Paschos
      On the Performance of Congestion Games for Optimum Satisfiability Problems.WINE 2007:220-231

    • Giorgio Ausiello, Vangelis Th. Paschos
      Reductions That Preserve Approximability.Handbook of Approximation Algorithms and Metaheuristics 2007:

    • Giorgio Ausiello, Vangelis Th. Paschos
      Differential Ratio Approximation.Handbook of Approximation Algorithms and Metaheuristics 2007:

    • Cécile Murat, Vangelis Th. Paschos
      On the probabilistic minimum coloring and minimum -coloring.Discrete Applied Mathematics154(3) 2006:564-586

    • Yury Glazkov, Alexey Baburin, Edward Gimadi, Federico Della Croce, Vangelis Th. Paschos
      Approximation algorithms for 2-Peripathetic Salesman Problem with edge weights 1 and 2.Electronic Notes in Discrete Mathematics27 2006:35-36

    • Vangelis Th. Paschos
      Jon Lee, A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics.European Journal of Operational Research168(3) 2006:1042-1044

    • Giorgio Ausiello, Vangelis Th. Paschos
      Reductions, completeness and the hardness of approximability.European Journal of Operational Research172(3) 2006:719-739

    • Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos
      Weighted Coloring: further complexity and approximability results.Inf. Process. Lett.97(3) 2006:98-103

    • Bruno Escoffier, Vangelis Th. Paschos
      On-line models and algorithms for max independent set.RAIRO - Operations Research40(2) 2006:129-142

    • Bruno Escoffier, Vangelis Th. Paschos
      Completeness in approximation classes beyond APX.Theor. Comput. Sci.359(1-3) 2006:369-377

    • Giorgio Ausiello, Aristotelis Giannakos, Vangelis Th. Paschos
      Greedy algorithms for on-line set-covering and related problems.CATS 2006:145-151

    • Giorgio Ausiello, Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos
      Reoptimization of Minimum and Maximum Traveling Salesman's Tours.SWAT 2006:196-207

    • Dominique de Werra, Marc Demange, Jérôme Monnot, Vangelis Th. Paschos
      A hypocoloring model for batch scheduling.Discrete Applied Mathematics146(1) 2005:3-26

    • Marc Demange, Vangelis Th. Paschos
      Polynomial approximation algorithms with performance guarantees: An introduction-by-example.European Journal of Operational Research165(3) 2005:555-568

    • Bruno Escoffier, Vangelis Th. Paschos
      Proving completeness by logic.Int. J. Comput. Math.82(2) 2005:151-161

    • Giorgio Ausiello, Cristina Bazgan, Marc Demange, Vangelis Th. Paschos
      Completeness in differential approximation classes.Int. J. Found. Comput. Sci.16(6) 2005:1267-1295

    • Marc Demange, Vangelis Th. Paschos
      Improved Approximations for Weighted and Unweighted Graph Problems.Theory Comput. Syst.38(6) 2005:763-787

    • Marc Demange, Vangelis Th. Paschos
      On-line vertex-covering.Theor. Comput. Sci.332(1-3) 2005:83-108

    • Cristina Bazgan, Jérôme Monnot, Vangelis Th. Paschos, Fabrice Serrière
      On the differential approximation of MIN SET COVER.Theor. Comput. Sci.332(1-3) 2005:497-513

    • Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos
      Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness.Theor. Comput. Sci.339(2-3) 2005:272-292

    • Bruno Escoffier, Vangelis Th. Paschos
      Differential Approximation of min sat, max sat and Related Problems.ICCSA (4) 2005:192-201

    • Federico Della Croce, Bruno Escoffier, Cécile Murat, Vangelis Th. Paschos
      Probabilistic Coloring of Bipartite and Split Graphs.ICCSA (4) 2005:202-211

    • Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos
      Weighted Coloring: Further Complexity and Approximability Results.ICTCS 2005:205-214

    • Federico Della Croce, Vangelis Th. Paschos
      Computing Optimal Solutions for the min 3-set covering Problem.ISAAC 2005:685-692

    • Cristina Bazgan, Jérôme Monnot, Vangelis Th. Paschos, Fabrice Serrière
      Greedy Differential Approximations for Min Set Cover.SOFSEM 2005:62-71

    • Mhand Hifi, Vangelis Th. Paschos, Vassilis Zissimopoulos
      A simulated annealing approach for the circular cutting problem.European Journal of Operational Research159(2) 2004:430-448

    • Tinaz Ekim, Vangelis Th. Paschos
      Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximation.Int. J. Comput. Math.81(5) 2004:569-582

    • Giorgio Ausiello, Marc Demange, Luigi Laura, Vangelis Th. Paschos
      Algorithms for the On-Line Quota Traveling Salesman Problem.Inf. Process. Lett.92(2) 2004:89-94

    • Jérôme Monnot, Vangelis Th. Paschos, Sophie Toulouse
      Local approximations for maximum partial subgraph problem.Oper. Res. Lett.32(3) 2004:217-224

    • Federico Della Croce, Andrea Grosso, Vangelis Th. Paschos
      Lower Bounds on the Approximation Ratios of Leading Heuristics for the Single-Machine Total Tardiness Problem.J. Scheduling7(1) 2004:85-91

    • Giorgio Ausiello, Marc Demange, Luigi Laura, Vangelis Th. Paschos
      Algorithms for the On-Line Quota Traveling Salesman Problem.COCOON 2004:290-299

    • Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos
      Poly-APX- and PTAS-Completeness in Standard and Differential Approximation.ISAAC 2004:124-136

    • Jérôme Monnot, Vangelis Th. Paschos, Dominique de Werra, Marc Demange, Bruno Escoffier
      Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation.ISAAC 2004:896-907

    • Dominique de Werra, Marc Demange, Jérôme Monnot, Vangelis Th. Paschos
      The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small.WG 2004:377-388

    • Marc Demange, Jérôme Monnot, Vangelis Th. Paschos
      Differential approximation results for the Steiner tree problem.Appl. Math. Lett.16(5) 2003:733-739

    • Vangelis Th. Paschos
      Polynomial Approximation and Graph-Coloring.Computing70(1) 2003:41-86

    • Jérôme Monnot, Vangelis Th. Paschos, Sophie Toulouse
      Differential approximation results for the traveling salesman problem with distances 1 and 2.European Journal of Operational Research145(3) 2003:557-568

    • Cristina Bazgan, Vangelis Th. Paschos
      Differential approximation for optimal satisfiability and related problems.European Journal of Operational Research147(2) 2003:397-404

    • Jérôme Monnot, Vangelis Th. Paschos, Sophie Toulouse
      Approximation algorithms for the traveling salesman problem.Math. Meth. of OR56(3) 2003:387-405

    • Jérôme Monnot, Vangelis Th. Paschos, Sophie Toulouse
      Optima locaux garantis pour l'approximation différentielle.Technique et Science Informatiques22(3) 2003:257-288

    • Giorgio Ausiello, Cristina Bazgan, Marc Demange, Vangelis Th. Paschos
      Completeness in Differential Approximation Classes.MFCS 2003:179-188

    • Cécile Murat, Vangelis Th. Paschos
      The Probabilistic Minimum Coloring Problem.WG 2003:346-357

    • Marc Demange, Vangelis Th. Paschos
      Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation.RAIRO - Operations Research36(3) 2002:237-277

    • Marc Demange, Vangelis Th. Paschos
      Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances.RAIRO - Operations Research36(4) 2002:311-350

    • Cécile Murat, Vangelis Th. Paschos
      A priori optimization for the probabilistic maximum independent set problem.Theor. Comput. Sci.270(1-2) 2002:561-590

    • Marc Demange, Vangelis Th. Paschos
      Algorithms and Models for the On-Line Vertex-Covering.WG 2002:102-113

    • Marc Demange, Dominique de Werra, Jérôme Monnot, Vangelis Th. Paschos
      Weighted Node Coloring: When Stable Sets Are Expensive.WG 2002:114-125

    • Vangelis Th. Paschos
      On-line independent set by coloring vertices.Operational Research1(3) 2001:213-224

    • Jérôme Monnot, Vangelis Th. Paschos, Sophie Toulouse
      Differential Approximation Results for the Traveling Salesman Problem with Distances 1 and 2.FCT 2001:275-286

    • Laurent Alfandari, Vangelis Th. Paschos
      Master-Slave Strategy and Polynomial Approximation.Comp. Opt. and Appl.16(3) 2000:231-245

    • Marc Demange, Xavier Paradon, Vangelis Th. Paschos
      On-Line Maximum-Order Induces Hereditary Subgraph Problems.SOFSEM 2000:327-335

    • Cécile Murat, Vangelis Th. Paschos
      The probabilistic longest path problem.Networks33(3) 1999:207-219

    • Federico Della Croce, Vangelis Th. Paschos, Alexis Tsoukiàs
      An improved general procedure for lexicographic bottleneck problems.Oper. Res. Lett.24(4) 1999:187-194

    • Marc Demange, Vangelis Th. Paschos
      Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems.RAIRO - Operations Research33(4) 1999:481-507

    • Wenceslas Fernandez de la Vega, Vangelis Th. Paschos, Andreas Stafylopatis
      Average-Case Complexity for the Execution of Recursive Definitions on Relational Databases.Acta Inf.35(3) 1998:211-243

    • Marc Demange, Pascal Grisoni, Vangelis Th. Paschos
      Differential Approximation Algorithms for Some Combinatorial Optimization Problems.Theor. Comput. Sci.209(1-2) 1998:107-122

    • Marc Demange, Vangelis Th. Paschos
      The Approximability Behaviour of Some Combinatorial Problems with Respect to the Approximability of a Class of Maximum Independent Set Problems.Comp. Opt. and Appl.7(3) 1997:307-324

    • Vangelis Th. Paschos
      A Survey of Approximately Optimal Solutions to Some Covering and Packing Problems.ACM Comput. Surv.29(2) 1997:171-209

    • Marc Demange, Vangelis Th. Paschos
      On an Approximation Measure Founded on the Links Between Optimization and Polynomial Approximation Theory.Theor. Comput. Sci.158(1&2) 1996:117-141

    • Joël Blot, Wenceslas Fernandez de la Vega, Vangelis Th. Paschos, Rachid Saad
      Average Case Analysis of Greedy Algorithms for Optimisation Problems on Set Systems.Theor. Comput. Sci.147(1&2) 1995:267-298

    • Marc Demange, Vangelis Th. Paschos
      Constructive - Non-constructive Approximation and Maximum Independent Set Problem.Combinatorics and Computer Science 1995:194-207

    • Marc Demange, Pascal Grisoni, Vangelis Th. Paschos
      Approximation Results for the Minimum Graph Coloring Problem.Inf. Process. Lett.50(1) 1994:19-23

    • Vangelis Th. Paschos
      A (Delta/2)-Approximation Algorithm for the Maximum Independent Set Problem.Inf. Process. Lett.44(1) 1992:11-13

    • Wenceslas Fernandez de la Vega, Vangelis Th. Paschos, Rachid Saad
      Average Case Analysis of a Greedy Algorithm for the Minimum Hitting Set Problem.LATIN 1992:130-138

    • Vassilis Zissimopoulos, Vangelis Th. Paschos, Ferhan Pekergin
      On the Approximation of NP-Complete Problems by Using the Boltzmann Machine Method: The Cases of Some Covering and Packing Problems.IEEE Trans. Computers40(12) 1991:1413-1418

    • Vangelis Th. Paschos
      A Theorem on the Approximation of Set Cover and Vertex Cover.FSTTCS 1991:278-287

    • A. Benkouar, Yannis Manoussakis, Vangelis Th. Paschos, Rachid Saad
      On the Complexity of Some Hamiltonian and Eulerian Problems in Edge-Colored Complete Graphs.ISA 1991:190-198

    • Wenceslas Fernandez de la Vega, Vangelis Th. Paschos, A. N. Staylopatis
      On the Mean Execution Time of Recursive Definitions on Relational Databases.MFDBS 1991:119-133



    Publications DFIS


    Publications HAL