Paschos Vangelis - CV

LAMSADE

Paschos Vangelis

Professeur des universités

Envoyer un email

Tel : 01 44 05 45 82

Bureau : P 643

Publications

BU Paris-Dauphine

Articles

Katsikarelis I., Lampis M., Paschos V. (2019), Structural parameters, tight bounds, and approximation for (k,r)-center, Discrete Applied Mathematics, vol. 264, p. 90-117

Bazgan C., Brankovic L., Casel K., Fernau H., Jansen K., Klein K-M., Lampis M., Liedloff M., Monnot J., Paschos V. (2018), The many facets of upper domination, Theoretical Computer Science, vol. 717, p. 2-25

Boria N., Murat C., Paschos V. (2018), The probabilistic minimum dominating set problem, Discrete Applied Mathematics, n°234, p. 93-113

Bonnet É., Paschos V. (2018), Sparsification and subexponential approximation, Acta Informatica, vol. 55, n°1, p. 1-15

Bonnet É., Lampis M., Paschos V. (2018), Time-approximation trade-offs for inapproximable problems, Journal of Computer and System Sciences, vol. 92, p. 171-180

Bonnet E., Paschos V., Sikora F. (2016), Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems, RAIRO - Theoretical Informatics and Applications, vol. 50, n°3, p. 227-240

Paschos V., Kim E., Bonnet E., Escoffier B. (2015), On Subexponential and FPT-Time Inapproximability, Algorithmica, vol. 71, n°3, p. 541-565

Bonnet E., Escoffier B., Paschos V., Tourniaire E. (2015), Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization, Algorithmica, vol. 71, n°3, p. 566-580

Paschos V. (2015), When polynomial approximation meets exact computation, 4OR, vol. 13, n°3, p. 227-245

Monnot J., Xiao M., Escoffier B., Paschos V. (2015), New Results on Polynomial Inapproximability and Fixed Parameter Approximability of Edge Dominating Set, Theory of Computing Systems, vol. 56, n°2, p. 330-346

Della Croce F., Paschos V. (2014), Efficient algorithms for the Max k-Vertex Cover problem, Journal of Combinatorial Optimization, vol. 28, n°3, p. 674-691

Paschos V., Kacem I. (2013), Weighted completion time minimization on a single-machine with a fixed non-availability interval: differential approximability, Discrete Optimization, vol. 10, n°1, p. 61-68

Boria N., Paschos V., Monnot J. (2013), Reoptimization of maximum weight induced hereditary subgraph problems, Theoretical Computer Science, vol. 514, p. 61-74

Boria N., Bourgeois N., Escoffier B., Paschos V. (2013), Exponential approximation schemata for some network design problems, Journal of Discrete Algorithms, vol. 22, p. 43-52

Boria N., Monnot J., Paschos V. (2013), Reoptimization under Vertex Insertion: Max Pk-Free Subgraph and Max Planar Subgraph, Discrete Mathematics, Algorithms and Applications, vol. 05, n°02, p. n°1360004

Bourgeois N., Della Croce F., Escoffier B., Paschos V. (2012), Algorithms for dominating clique problems, Theoretical Computer Science, vol. 459, n°9, p. 77-88

Bourgeois N., Giannakos A., Lucarelli G., Milis I., Paschos V., Pottié O. (2012), The max quasi-independent set problem, Journal of Combinatorial Optimization, vol. 23, n°1, p. 94-117

Paschos V., Paschos S. (2012), Reoptimization of the minimum spanning tree, Wiley Interdisciplinary Reviews. Computational Statistics, vol. 4, n°2, p. 211-217

Ausiello G., Boria N., Giannakos A., Lucarelli G., Paschos V. (2012), Online maximum k-coverage, Discrete Applied Mathematics, vol. 160, n°13-14, p. 1901-1913

Bourgeois N., Escoffier B., Paschos V., Van Rooij J. (2012), Fast Algorithms for max independent set, Algorithmica, vol. 62, n°1-2, p. 382-415

Boria N., Murat C., Paschos V. (2012), On the probabilistic min spanning tree Problem, Journal of Mathematical Modelling and Algorithms, vol. 11, n°1, p. 45-76

Paschos V., Boria N. (2011), A survey on combinatorial optimization in dynamic environments, RAIRO - Operations Research, vol. 45, n°3, p. 241-294

Escoffier B., Bourgeois N., Paschos V. (2011), Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms, Discrete Applied Mathematics, vol. 159, n°17, p. 1954-1970

Milis I., Lucarelli G., Bourgeois N., Paschos V. (2010), Approximating the max edge-coloring problem, Theoretical Computer Science, vol. 411, n°34-36, p. 3055-3067

Paschos V., Escoffier B. (2010), A Survey on the Structure of Approximation Classes, Computer Science Review, vol. 4, n°1, p. 19-40

Boria N., Paschos V. (2010), Fast Reoptimization for the Minimum Spanning Tree Problem, Journal of Discrete Algorithms, vol. 8, n°3, p. 296-310

Milis I., Lucarelli G., Paschos V. (2010), On the max-weight edge coloring problem, Journal of Combinatorial Optimization, vol. 20, n°4, p. 429-442

Paschos V., Calvo R., Della Croce F. (2010), Approximating the Metric 2-Peripatetic Salesman Problem, Algorithmic Operations Research, vol. 5, n°1, p. 13-20

Murat C., Paschos V. (2010), Probabilistic optimization in graph-problems, Algorithmic Operations Research, vol. 15, n°1, p. 49-64

Telelis O., Zissimopoulos V., Paschos V. (2010), Probabilistic models for the Steiner Tree problem, Networks, vol. 56, n°1, p. 39-49

Escoffier B., Paschos V., de Werra D., Monnot J., Demange M. (2009), Weighted coloring on planar, bipartite and split graphs: complexity and approximation, Discrete Applied Mathematics, vol. 157, n°4, p. 819-832

Ausiello G., Monnot J., Paschos V., Escoffier B. (2009), Reoptimization of minimum and maximum traveling salesman's tours, Journal of Discrete Algorithms, vol. 7, n°4, p. 453-463

Paschos V. (2009), An overview on polynomial approximation of NP-hard problems, Yugoslav Journal of Operations Research, vol. 19, n°1, p. 3-40

Bourgeois N., Ausiello G., Paschos V., Giannakos A. (2009), Greedy algorithms for on-line set-covering, Algorithmic Operations Research, vol. 4, n°1, p. 36-48

Paschos V., Della Croce F., Murat C., Escoffier B., Bourgeois N. (2009), Probabilistic graph-coloring in bipartite and split graphs, Journal of Combinatorial Optimization, vol. 17, n°3, p. 274-311

Paschos V., Della Croce F., Glazkov Y., Gimadi E., Baburin A. (2009), Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2, Discrete Applied Mathematics, vol. 157, n°9, p. 1988-1992

Bourgeois N., Escoffier B., Paschos V. (2009), Efficient approximation of MIN SET COVER by moderately exponential algorithms, Theoretical Computer Science, vol. 410, n°21-23, p. 2184-2195

Milanic M., Paschos V., Escoffier B. (2009), Simple and fast reoptimizations for the Steiner tree problem, Algorithmic Operations Research, vol. 4, n°2, p. 86-94

Paschos V., Bourgeois N., Escoffier B. (2009), Approximation of MIN COLORING by moderately exponential algorithms, Information Processing Letters, vol. 109, n°16, p. 950-954

Della Croce F., Paschos V. (2008), Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems, Operational Research, vol. 8, n°3, p. 235-256

Paschos V., Kaminski M., Della Croce F. (2007), An exact algorithm for MAX CUT in sparse graphs, Operations Research Letters, vol. 35, n°3, p. 403-408

Paschos V., Demange M., de Werra D., Monnot J. (2007), Time slot scheduling of compatible jobs, Journal of Scheduling, vol. 10, n°2, p. 111-127

Della Croce F., Escoffier B., Paschos V. (2007), Improved worst-case complexity for the MIN 3-SET COVERING problem, Operations Research Letters, vol. 35, n°2, p. 205-210

Paschos V., Escoffier B. (2007), Differential approximation of MIN SAT, MAX SAT and related problems, European Journal of Operational Research, vol. 181, n°2, p. 620-633

Paschos V. (2006), Review of Jon Lee's book "A First Course in Combinatorial Optimization", CambridgeTexts in Applied Mathematics, European Journal of Operational Research, vol. 168, n°3, p. 1042-1044

Paschos V., Escoffier B. (2006), On-line models and algorithms for max independent set, RAIRO - Operations Research, vol. 40, n°2, p. 129-142

Ausiello G., Paschos V. (2006), Reductions, completeness and the hardness of approximability, European Journal of Operational Research, vol. 172, n°3, p. 719-739

Paschos V., Escoffier B., Monnot J. (2006), Weighted coloring: further complexity and approximability results, Information Processing Letters, vol. 97, n°3, p. 98-103

Paschos V., Murat C. (2006), On the probabilistic minimum coloring and minimum k-coloring, Discrete Applied Mathematics, vol. 154, n°3, p. 564-586

Paschos V., Escoffier B. (2006), Completeness in approximation classes beyond APX, Theoretical Computer Science, vol. 359, n°1-3, p. 369-377

Bazgan C., Escoffier B., Paschos V. (2005), Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness, Theoretical Computer Science, vol. 339, n°2-3, p. 272-292

Ausiello G., Bazgan C., Demange M., Paschos V. (2005), Completeness in differential approximation classes, International Journal of Foundations of Computer Science, vol. 16, n°6, p. 1267-1295

Escoffier B., Paschos V. (2005), Proving completeness by logic, International Journal of Computer Mathematics, vol. 82, n°2, p. 151-161

Demange M., Paschos V. (2005), Improved approximations for weighted and unweighted graph problems, Theory of Computing Systems, vol. 38, n°6, p. 763-787

Demange M., Paschos V. (2005), Polynomial approximation algorithms with performance guarantees: an introduction-by-example, European Journal of Operational Research, vol. 165, n°3, p. 555-568

Paradon X., Paschos V., Demange M. (2005), On-line maximum-order induced hereditary subgraph problems, International Transactions in Operational Research, vol. 12, n°2, p. 185-201

Bazgan C., Monnot J., Paschos V., Serrière F. (2005), On the differential approximation of MIN SET COVER, Theoretical Computer Science, vol. 332, n°1-3, p. 497-513

Paschos V., Demange M. (2005), On-line vertex-covering, Theoretical Computer Science, vol. 332, n°1-3, p. 83-108

Paschos V., Monnot J., de Werra D., Demange M. (2005), A hypocoloring model for batch scheduling, Discrete Applied Mathematics, vol. 146, n°1, p. 3-26

Paschos S., Paschos V., Zissimopoulos V. (2004), The antennas preassignment problem, Chaos, Solitons and Fractals, vol. 22, n°4, p. 821-829

Paschos V., Grosso A., Della Croce F. (2004), Lower bounds on the approximation ratios of leading heuristics for the single machine total tardiness problem, Journal of Scheduling, vol. 7, n°1, p. 85-91

Demange M., Laura L., Paschos V., Ausiello G. (2004), Algorithms for the on-line quota traveling salesman problem, Information Processing Letters, vol. 92, n°2, p. 89-94

Toulouse S., Paschos V., Monnot J. (2004), Local approximations for maximum partial subgraph problem, Operations Research Letters, vol. 32, n°3, p. 217-224

Paschos V., Zissimopoulos V., Hifi M. (2004), A simulated annealing approach for the circular cutting problem, European Journal of Operational Research, vol. 159, n°2, p. 430-448

Paschos V., Ekim T. (2004), Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximation, International Journal of Computer Mathematics, vol. 81, n°5, p. 569-582

Monnot J., Toulouse S., Paschos V. (2003), Approximation algorithms for the traveling salesman problem, Mathematical Methods of Operations Research, vol. 56, n°3, p. 387-405

Monnot J., Toulouse S., Paschos V. (2003), Optima locaux garantis pour l'approximation différentielle, TSI : Technique et Science Informatiques, vol. 22, n°3, p. 257-288

Paschos V. (2003), Approximation, complexity, optimization: a 3-dimensional matching full of interest, AIROnews, vol. 8, n°2, p. 1-4

Bazgan C., Paschos V. (2003), Differential approximation for satisfiability and related problems, European Journal of Operational Research, vol. 147, n°2, p. 397-404

Monnot J., Paschos V., Toulouse S. (2003), Differential approximation results for the traveling salesman problem with distances 1 and 2, European Journal of Operational Research, vol. 145, n°3, p. 557-568

Paschos V. (2003), Polynomial approximation and graph-coloring, Computing, vol. 70, n°1, p. 41-86

Monnot J., Paschos V., Demange M. (2003), Differential approximation results for the Steiner tree problem, Applied Mathematics Letters, vol. 16, n°5, p. 733-739

Paschos V., Murat C. (2002), The probabilistic minimum vertex covering problem, International Transactions in Operational Research, vol. 9, n°1, p. 19-32

Likas A., Paschos V. (2002), A note on a new greedy-solution representation and a new greedy parallelizable heuristic for the traveling salesman problem, Chaos, Solitons and Fractals, vol. 13, n°1, p. 71-78

Paschos V., Demange M. (2002), Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, RAIRO - Operations Research, vol. 36, n°3, p. 237-277

Murat C., Paschos V. (2002), A priori optimization for the probabilistic maximum independent set problem, Theoretical Computer Science, vol. 270, n°1-2, p. 561-590

Paschos V. (2001), On-line independent set by coloring vertices, Operational Research, vol. 1, n°3, p. 213-224

Paschos V. (2001), A note on the approximation ratio of graph-coloring, Foundations of Computing and Decision Sciences, vol. 26, n°4

Paschos V., Monnot J., Demange M. (2001), Maximizing the number of unused bins, Foundations of Computing and Decision Sciences, vol. 26, n°2, p. 169-186

Paschos V. (2000), Studying graph-stability to apprehend relative hardness of constructive -non constructive approximation, Bulletin of the Greek Mathematical Society, vol. 43, p. 37-54

Alfandari L., Paschos V. (2000), Master-slave strategies and polynomial approximation, Computational Optimization and Applications, vol. 16, p. 231-245

Paschos V., Hifi M., Zissimopoulos V. (2000), A neural network for the minimum set covering problem, Chaos, Solitons and Fractals, vol. 11, n°13, p. 2079-2089

Demange M., Paschos V. (1999), Asymptotic differential approximation ratio: definitions, motivations and an application to bin-packing, RAIRO - Operations Research, vol. 33, n°4, p. 481-507

Paschos V., Murat C. (1999), The probabilistic longest path problem, Networks, vol. 33, n°3, p. 207-219

Tsoukiàs A., Paschos V., Della Croce F. (1999), An improved general procedure for lexicographic bottleneck problems, Operations Research Letters, vol. 24, n°4, p. 187-194

Alfandari L., Paschos V. (1999), Approximating minimum spanning tree of depth 2, International Transactions in Operational Research, vol. 6, n°6, p. 607-622

Paschos V., Monnot J., Demange M. (1999), Bridging gap between standard and differential polynomial approximation: the case of bin-packing, Applied Mathematics Letters, vol. 12, n°7, p. 127-133

Demange M., Paschos V., Grisoni P. (1998), Differential approximation algorithms for some combinatorial optimization problems, Theoretical Computer Science, vol. 209, n°1-2, p. 107-122

Fernandez de la Vega W., Stafylopatis A., Paschos V. (1998), Average-case complexity for the execution of recursive definitions on relational databases, Acta Informatica, vol. 35, n°3, p. 211-243

Demange M., Paschos V. (1997), A generalization of König-Egervary graphs and heuristics for maximum independent set problem with improved approximation ratios, European Journal of Operational Research, vol. 97, n°3, p. 580-592

Paschos V., Demange M. (1997), Improved approximations for maximum independent set via approximation chains, Applied Mathematics Letters, vol. 10, n°3, p. 105-110

Moulet A., Gabrel V., Paschos V., Murat C. (1997), A new single model and derived algorithms for the satellite shots planning problem using graph theory concepts, Annals of Operations Research, vol. 69, n°0, p. 115-134

Paschos V. (1997), A survey of approximately optimal solutions to some covering and packing problems, ACM Computing Surveys, vol. 29, n°2, p. 171-209

Demange M., Paschos V. (1997), The approximability behavior of some combinatorial problems with respect to the approximability of a class of maximum independent set problems, Computational Optimization and Applications, vol. 7, n°3, p. 307-324

Manoussakis Y., Saad R., Paschos V., Benkouar A. (1996), Hamiltonian problems in edge-colored complete graphs and Eulerian cycles in edge-colored graphs: some complexity results, RAIRO - Operations Research, vol. 30, n°4

Paschos V., Demange M. (1996), Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale, Mathématiques, Informatique et Sciences Humaines, vol. 135

Demange M., Paschos V. (1996), On an approximation measure founded on the links between optimization and polynomial approximation theory, Theoretical Computer Science, vol. 158, n°1-2, p. 117-141

Blot J., Fernandez de la Vega W., Paschos V., Saad R. (1995), Analyse en moyenne de la performance des algorithmes gloutons pour des problèmes d'optimisation sur des systèmes d'ensembles, Comptes rendus. Mathématique, vol. 321

Hifi M., Zissimopoulos V., Afif M., Paschos V. (1995), A new efficient heuristic for minimum set covering problem, Journal of the Operational Research Society, vol. 46, n°10, p. 1260-1268

Murat C., Paschos V., Bellalouna M. (1995), Probabilistic combinatorial optimization problems: a new domain in Operational Research, European Journal of Operational Research, vol. 87, n°3, p. 693-706

Fernandez de la Vega W., Blot J., Paschos V., Saad R. (1995), Average case analysis of greedy algorithms for optimisation problems on set systems, Theoretical Computer Science, vol. 147, n°1-2, p. 267-298

Paschos V., Murat C. (1995), Problème du stable probabiliste, Comptes Rendus de l'Académie des Sciences de Paris, vol. 321, n°4, p. 495-498

Likas A., Afif M., Paschos V. (1995), A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem, Chaos, Solitons and Fractals, vol. 5, n°5, p. 739-746

Paschos V. (1995), A note on the improvement of the maximum independent set's approximation ratio, Yugoslav Journal of Operations Research, vol. 5, n°1

Demange M., Paschos V. (1995), L'approximabilité de la couverture d'ensembles et d'un problème de programmation convexe par rapport à celle d'une classe de problèmes de stabilité, Comptes rendus. Mathématique, vol. 321

Paschos V., Renotte L. (1995), Approximability preserving reductions for NP-complete problems, Foundations of Computing and Decision Sciences, vol. 20, n°1

Demange M., Paschos V. (1994), Approximation algorithms for minimum set covering problem: a survey, Foundations of Computing and Decision Sciences, vol. 19, n°3

Grisoni P., Demange M., Paschos V. (1994), Approximation results for the minimum graph coloring problem, Information Processing Letters, vol. 50, n°1, p. 19-23

Paschos V. (1994), A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set, RAIRO - Operations Research, vol. 28, n°4, p. 413-433

Paschos V., Grisoni P., Demange M. (1994), Quelques résultats dans le cadre d'une nouvelle théorie de l'approximation polynomiale, Comptes Rendus de l'Académie des Sciences de Paris, vol. 318, p. 289-292

Demange M., Paschos V. (1993), Quelques étapes vers la conciliation de la théorie d'approximation et celle d'optimisation : une nouvelle théorie d'approximation polynomiale et résultats préliminaires, Comptes rendus. Mathématique, vol. 317, n°4, p. 409-414

Paschos V., Zissimopoulos V., Pekergin F. (1993), Approximating the optimal solutions of some hard graph problems by a Boltzmann machine, Belgian Journal of Operations Research, Statistics and Computer Science, vol. 33, n°2, p. 119-132

Stafylopatis A., Paschos V. (1992), Evaluation of the execution cost of recursive definitions, Computer Journal, vol. 35

Paschos V. (1992), A (°/2)-approximation algorithm for the maximum independent set problem, Information Processing Letters, vol. 44, n°1, p. 11-13

Zissimopoulos V., Pekergin F., Paschos V. (1991), On the approximation of NP-complete problems by using Boltzmann machine method: the cases of some covering and packing problems, IEEE Transactions on Computers, vol. 40, n°12, p. 1413-1418

Ouvrages

Paschos V., Mahjoub A., Markakis V., Milis I. (2012), Combinatorial Optimization Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers, Berlin: Springer, 476 p.

Paschos V. (2010), Combinatorial optimization Volume 2, Paradigms of Combinatorial Optimization: problems and new approaches Wiley, 704 p.

Paschos V. (2010), Combinatorial Optimization Volume 1, Concepts of Combinatorial Optimization Wiley, 368 p.

Paschos V. (2010), Combinatorial Optimization Volume 3, Applications of Combinatorial Optimization Wiley, 384 p.

Paschos V. (2010), Combinatorial Optimization Volume 3, Applications of Combinatorial Optimization, London, Hoboken: Wiley-ISTE, 371 p.

Paschos V. (2010), Combinatorial optimization Volume 2, Paradigms of combinatorial optimization : problems and new approaches, London, Hoboken: Wiley-ISTE, 687 p.

Paschos V. (2008), Combinatorial optimization and theoretical computer science: interfaces and perspectives: 30th anniversary of the LAMSADE, Hoboken NJ: Wiley, 515 p.

Paschos V. (2007), Optimisation combinatoire. 5, Problèmes paradigmatiques et nouvelles problématiques, Paris: Lavoisier, 271 p.

Paschos V. (2007), Optimisation combinatoire. 4, problèmes paradigmatiques, Paris: Lavoisier, 215 p.

Murat C., Paschos V. (2006), Probabilistic combinatorial optimization on graphs, London Newport Beach: ISTE, 267 p.

Paschos V. (2006), Optimisation combinatoire. 3, Applications, Paris: Lavoisier, 339 p.

Paschos V. (2005), Optimisation combinatoire. 2, Concepts avancés, Paris: Lavoisier, 298 p.

Paschos V. (2005), Optimisation combinatoire. 1, Concepts fondamentaux, Paris: Lavoisier, 349 p.

Paschos V. (2004), Complexité et approximation polynomiale, Paris: Lavoisier, 270 p.

Paschos V., Monnot J., Toulouse S. (2003), Approximation polynomiale des problèmes NP-difficiles : optima locaux et rapport différentiel, Paris: Lavoisier, 221 p.

Chapitres d'ouvrage

Bourgeois N., Escoffier B., Paschos V. (2011), An Introduction to Exponential Time Exact Algorithms for Solving NP-hard Problems, in Mahjoub, Ridha, Progress in Combinatorial Optimization: Recent Progress Wiley-ISTE, p. chapter 15

Paschos V., Ausiello G. (2010), Approximation preserving reductions, in Paschos, Vangelis, Combinatorial Optimization Volume 2, Paradigmatic Problems and New Approaches, London, Hoboken: Wiley-ISTE, p. 687

Murat C., Paschos V. (2010), Probabilistic combinatorial optimization, in Vangelis, Paschos, T., Combinatorial optimization volume 2 Paradigms of combinatorial optimization : problems and new approaches, London, Hoboken: Wiley-ISTE, p. 687

Paschos V., Demange M. (2010), Polynomial approximation, in Vangelis, Paschos, T., Combinatorial Optimization Volume 2, Paradigmatic Problems and New Approaches, London, Hoboken: Wiley-ISTE, p. 687

Paschos V. (2010), Basic concepts in algorithms and complexity theory, in Vangelis, Paschos, T., Combinatorial Optimization Volume 1, Concepts of Combinatorial Optimization, London, Hoboken: Wiley-ISTE, p. 346

Paschos V., Murat C., Demange M., Toulouse S. (2010), A model for the design of a minimum-cost telecommunications network, in Paschos, Vangelis T., Combinatorial Optimization Volume 3, Applications, London, Hoboken: Wiley-ISTE, p. 371

Paschos V., Murat C., Gabrel V. (2008), Mission planning for observation satellites, in G. Finke, Operations research and networks Wiley-ISTE, p. 352

Escoffier B., Paschos V., Monnot J., Demange M., de Werra D. (2008), Complexity and approximation results for the min weighted node coloring problem, in Paschos, Vangelis, Combinatorial optimization and theoretical computer science: interfaces and perspectives Wiley-ISTE, p. 515

Della Croce F., Escoffier B., Kaminski M., Paschos V. (2008), Worst-case complexity of exact algorithms for NP-hard problems, in Paschos, Vangelis, Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives: 30th anniversary of the LAMSADE, Hoboken NJ: Wiley, p. 515

Giannakos A., Paschos V., Ausiello G. (2008), Online models for set-covering: the flaw of greediness, in Paschos, Vangelis, Combinatorial optimization and theoretical computer science: interfaces and perspectives : 30th anniversary of the LAMSADE, London: Wiley-ISTE, p. 65-85

Giannakos A., Paschos V., Pottié O. (2008), Algorithmic games, in Paschos, Vangelis, Combinatorial optimization and theoretical computer science: interfaces and perspectives Wiley-ISTE, p. 515

Demange M., Paschos V., de Werra D., Escoffier B., Milis I., Lucarelli G. (2008), Weighted edge coloring, in Paschos, Vangelis, Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives: 30th anniversary of the LAMSADE, Hoboken NJ: Wiley, p. 515

Giannakos A., Paschos V. (2007), Quand l'optimisation fait du beau jeu : une vision algorithmique de la théorie des jeux, in Paschos, Vangelis, Optimisation combinatoire 5 : problèmes paradigmatiques et nouvelles problématiques, Paris: Lavoisier, p. 271

Ausiello G., Paschos V. (2007), Differential ratio approximation, in T. F. Gonzalez, Handbook of Approximation Algorithms and Metaheuristics, Boca Raton: Taylor & Francis, p. 1432

Paschos V., Ausiello G. (2007), Reductions that preserve approximability, in T. F. Gonzalez, Handbook of Approximation Algorithms and Metaheuristics, Boca Raton, FL: Taylor & Francis, p. XXI-multipagination

Paschos V., Ausiello G. (2005), Réductions préservant l'approximabilité, in Vangelis Paschos, Optimisation combinatoire 2: concepts avancés (Traité IC2, série Informatique et systèmes d'information), Paris: Lavoisier, p. 298

Demange M., Paschos V. (2005), Approximation polynomiale, in Vangelis Paschos, Optimisation combinatoire 2: concepts avancés (Traité IC2, série Informatique et systèmes d'information), Paris: Lavoisier, p. 298

Murat C., Paschos V. (2005), L'optimisation combinatoire probabiliste, in Paschos, Vangelis, Optimisation combinatoire 2: concepts avancés, Paris: Lavoisier, p. 298

Murat C., Gabrel V., Paschos V. (2002), Planification de prises de vue par satellite, in Finke, Gerd, Recherche opérationnelle et réseaux: Méthodes d'analyse spatiale (Traité IGAT, série Aspects fondamentaux de l'analyse spatiale), Paris: Lavoisier, p. 272

Communications avec actes

Katsikarelis I., Lampis M., Paschos V. (2018), Structurally Parameterized d-Scattered Set, in Andreas Brandstädt; Ekkehard Köhler; Klaus Meer, Graph-Theoretic Concepts in Computer Science, 44th International Workshop, WG 2018, Cottbus, Germany, June 27–29, 2018, Proceedings, Springer International Publishing, 292-305 p.

Bazgan C., Brankovic L., Casel K., Fernau H., Jansen K., Klein K-M., Lampis M., Liedloff M., Monnot J., Paschos V. (2016), Upper Domination : Complexity and Approximation, in Veli Mäkinen, Simon J. Puglisi, Leena Salmela, Combinatorial Algorithms. 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings, Berlin Heidelberg, Springer, 241-252 p.

Bazgan C., Brankovic L., Casel K., Fernau H., Jansen K., Klein K-M., Lampis M., Liedloff M., Monnot J., Paschos V. (2016), Algorithmic Aspects of Upper Domination: A Parameterized Perspective, in Riccardo Dondi, Guillaume Fertin, Giancarlo Mauri, Algorithmic Aspects in Information and Management. 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings, Berlin Heidelberg, Springer, 113-124 p.

Bonnet E., Lampis M., Paschos E. (2016), Time-Approximation Trade-offs for Inapproximable Problems, in Nicolas Ollinger, Heribert Vollmer, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Orléans, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 22:1-22:14 p.

Fotakis D., Lampis M., Paschos E. (2016), Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse, in Nicolas Ollinger, Heribert Vollmer, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Orléans, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 37:1--37:14 p.

Paschos V. (2013), Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, in Stiakakis, Emmanuil, Optimization Theory, Decision Making, and Operations Research Applications, Thessalonique, Springer, 359 p.

Bourgeois N., Della Croce F., Escoffier B., Paschos V. (2013), Fast algorithms for min independent dominating set, in , Seventh International Conference on Graphs and Optimization 2010, Ovronnaz, Discrete Applied Mathematics, 558-572 p.

Boria N., Monnot J., Paschos V. (2012), Reoptimization of the Maximum Weighted Pk-Free Subgraph Problem under Vertex Insertion, in Rahman, Md. Saidur, WALCOM: Algorithms and Computation 6th International Workshop, Dhaka, Springer, 76-87 p.

Escoffier B., Paschos V., Tourniaire E. (2012), Approximating MAX SAT by moderately exponential algorithms, in Li, Angsheng, Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings, Berlin, Springer, 622 p.

Della Croce F., Paschos V. (2012), Efficient Algorithms for the max k -vertex cover Problem, in De Boer, Frank S., Theoretical Computer Science 7th IFIP TC1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012, Proceedings, Berlin, Springer, 393 p.

Boria N., Murat C., Paschos V. (2011), On the probabilistic min spanning tree problem, in , Proceedings of the 2010 International Multiconference on Computer Science and Information Technology (IMCSIT), Wisla, IEEE - Institute of Electrical and Electronics Engineers, 893-900 p.

Paschos V. (2011), Approximation by Moderately Exponential Algorithms, in Mahjoub, Ali Ridha, ISCO International Symposium on Combinatorial Optimization, London, Wiley, 416 p.

Paschos V., Ausiello G., Lucarelli G., Boria N., Giannakos A. (2011), Online Maximum k-Coverage, in Steffen, Martin, Fundamentals of Computation Theory, FCT 2011, Oslo, Springer, 373 p.

Bourgeois N., Escoffier B., Paschos V. (2010), A Bottom-Up Method and Fast Algorithms for max independent set, in Kaplan, Haim, 12th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings, Berlin, Springer, 62-73 p.

Giannakos A., Milis I., Paschos V., Lucarelli G., Bourgeois N., Pottié O. (2010), The Max Quasi-Independent Set Problem, in Mayr, Ernst W., Computer Science – Theory and Applications 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedings, Kazan, Springer, 60-72 p.

Paschos V., Escoffier B., Van Rooij J., Bourgeois N. (2010), Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537^n), in Li, Angsheng, Theory and Applications of Models of Computation 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings, Prague, Springer, 373-384 p.

Escoffier B., Bourgeois N., Paschos V. (2010), Fast Algorithms for min independent dominating set, in Patt-Shamir, Boaz, Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings., Sirince, Springer, 247-261 p.

Bourgeois N., Lucarelli G., Milis I., Paschos V. (2009), Approximating the max edge-coloring problem, in Miller, Mirka, Combinatorial Algorithms 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28--July 2, 2009, Revised Selected Papers, Hradec nad Moravici, Springer, 83-94 p.

Paschos V., Milis I., Lucarelli G. (2009), On the Maximum Edge Coloring Problem (Extended Abstract), in Skutella, Martin, Approximation and Online Algorithms 6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers, Karlsruhe, Springer, 293 p.

Paschos V., Escoffier B., Bourgeois N. (2009), Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms, in Toth, Csaba D., Algorithms and Data Structures 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings, Berlin, Springer, 580 p.

Escoffier B., Paschos V., Bourgeois N., Della Croce F. (2009), Exact Algorithms for Dominating Clique Problems, in Ibarra, Oscar H., ISAAC 2009 20th International Symposium on Algorithms and Computation, Hawaï, Springer, 4-13 p.

Murat C., Paschos V. (2008), Vertex-uncertainty in graph-problems, in Yang, Boting, Second International Conference on Combinatorial Optimization and Applications (COCOA'08), St John's, Springer, 480 p.

Bourgeois N., Paschos V., Escoffier B. (2008), An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs, in Niedermeier, Rolf, Third International Workshop on Parameterized and Exact Computation Parameterized and Exact Computation (IWPEC 2008), Victoria, Springer, 55-65 p.

Telelis O., Zissimopoulos V., Paschos V. (2007), Steiner forests on stochastic metric graphs, in Zhu, Binhai, First International Conference on Combinatorial Optimization and Applications (COCOA'07), Xi'an, Springer, 390 p.

Monnot J., Giannakos A., Gourvès L., Paschos V. (2007), On the performance of congestion games for optimum satisfiability problems, in Graham, Fan Chung, Internet and Network Economics 3rd International Workshop, WINE 2007, San Diego, CA, USA, December 12-14, 2007, Proceedings, San Diego, Springer, 598 p.

Giannakos A., Paschos V., Ausiello G. (2006), Greedy algorithms for on-line set-covering and related problems, in Jay, Barry, Twelfth Computing: The Australasian Theory Symposium (CATS'06), Hobart, Australian Computer Society, 154 p.

Escoffier B., Ausiello G., Monnot J., Paschos V. (2006), Reoptimization of minimum and maximum traveling salesman's tours, in Freivalds, Rusins, Algorithm Theory - SWAT 2006 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedings, Riga, Springer, 436 p.

Bazgan C., Monnot J., Paschos V., Serrière F. (2005), Greedy differential approximations for MIN SET COVER, in Vojtas, Peter, SOFSEM'05 : Theory and Practice of Computer Science, Liptovský Ján, Springer, 62-71 p.

Paschos V., Della Croce F. (2005), Computing optimal solutions for the MIN 3-SET COVERING problem, in Du, Ding-Zhu, Algorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings, Sanya (Hainan), Springer, 685-692 p.

Escoffier B., Della Croce F., Paschos V., Murat C. (2005), Probabilistic coloring of bipartite and split graphs, in Taniar, David, International Conference on Computational Science and Its Applications (ICCSA'05), Singapour, Springer, 91-97 p.

Paschos V., Monnot J., Escoffier B. (2005), Weighted coloring: further complexity and approximability results, in Pinna, G. Michele, Theoretical Computer Science 9th Italian Conference, ICTCS 2005, Siena, Italy, October 12-14, 2005, Proceedings, Sienne, Springer, 411 p.

Escoffier B., Paschos V. (2005), Differential approximation of MIN SAT, MAX SAT and related problems, in Taniar, David, International Conference on Computational Science and Its Applications (ICCSA'05), Singapour, Springer, 192-201 p.

de Werra D., Monnot J., Paschos V., Escoffier B., Demange M. (2004), Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation, in Trippen, Gerhard, Algorithms and Computation 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings, Hong-Kong, Springer, 935 p.

Paschos V., Demange M., Monnot J., de Werra D. (2004), The hypocoloring problem: complexity and approximability results when the chromatic number is small, in Westfechtel, Bernhard, Graph-Theoretic Concepts in Computer Science 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Berlin, Springer, 404 p.

Bazgan C., Escoffier B., Paschos V. (2004), Poly-APX- and PTAS-completeness in standard and differential approximation, in Trippen, Gerhard, ISAAC'04 :15th International Symposium, Hong Kong, Springer, 124-136 p.

Laura L., Demange M., Ausiello G., Paschos V. (2004), Algorithms for the on-line quota traveling salesman problem, in Munro, J. Ian, Computing and Combinatorics 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004, Proceedings, Jeju Island, Springer, 474 p.

Ausiello G., Bazgan C., Demange M., Paschos V. (2003), Completeness in differential approximation classes, in Vojtas, Peter, Mathematical Foundations of Computer Science 2003 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings, Bratislava, Springer, 179-188 p.

Paschos V., Monnot J., de Werra D., Demange M. (2002), Weighted node coloring: when stable sets are expensive, in Kucera, Ludek, Graph-Theoretic Concepts in Computer Science 28th International Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002, Revised Papers, Cesky Krumlov, Springer, 422 p.

Toulouse S., Monnot J., Paschos V. (2001), Differential approximation results for the traveling salesman problem with distances 1 and 2, in Freivalds, Rusins, Fundamentals of Computation Theory 13th International Symposium, FCT 2001, Riga, Latvia, August 22-24, 2001. Proceedings, Riga, Springer, 541 p.

Paradon X., Paschos V., Demange M. (2000), On-line maximum-order induced hereditary subgraph problems, in Wiedermann, Jiri, 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, Milovy, Springer, 460 p.

Paschos V., Alfandari L. (1998), On the approximation of some spanning-arborescence problems, in Gürsoy, A., ISCIS'98, Ankara, IOS Press, 574-582 p.

Murat C., Paschos V. (1998), A priori optimization of the probabilistic maximum independent set, in Gursoy, Attila, International Symposium on Computer and Information Sciences (ISCIS'98), Antalya, IOS Press, 584 p.

Paschos V., Demange M. (1996), Constructive-non-constructive approximation and maximum independent set problem, in Manoussakis, Ioannis, Combinatorics and Computer Science 8th Franco-Japanese and 4th Franco-Chinese Conference, Brest, France, July 3-5, 1995 Selected Papers, Brest, Springer, 415 p.

Murat C., Paschos V. (1995), The probabilistic maximum independent set problem, in McClean, S., 7th International Symposium on Applied Stochastic Models and Data Analysis (ASMDA'95), Ulster, University of Ulster

Fernandez de la Vega W., Saad R., Paschos V. (1992), Average case analysis of a greedy algorithm for the minimum hitting set problem, in Simon, Imre, LATIN '92 1st Latin American Symposium on Theoretical Informatics, Sao Paulo, Brazil, April 6-10, 1992. Proceedings, Sao Paulo, Springer, 545 p.

Paschos V. (1991), Some approximation results on set packing, in Ozguc‎, Bulent, Computer and information sciences 6‎, proceedings‎ of the 1991 International symposium on computer and information sciences, Side, Elsevier, 624 p.

Paschos V. (1991), A theorem on the approximation of set cover and vertex cover, in Nori, Kesav V., Foundations of Software Technology and Theoretical Computer Science 11th Conference, New Delhi, India, December 17-19, 1991. Proceedings, New Delhi, Springer, 420 p.

Paschos V., Manoussakis Y., Benkouar A., Saad R. (1991), On the complexity of some Hamiltonian and Eulerian problems in edge-colored complete graphs (Extended abstract), in Lee, R.C.T., ISA '91 Algorithms 2nd International Symposium on Algorithms, Taipei, Republic of China [sic], December 16-18, 1991. Proceedings, Taipei, Springer, 396 p.

Paschos V., Stafylopatis A., Fernandez de la Vega W. (1991), On the mean execution time of recursive definitions on relational databases, in Thalheim, Bernhard, MFDBS 91 3rd Symposium on Mathematical Fundamentals of Database and Knowledge Base Systems, Rostock, Germany, May 6-9, 1991 Proceedings, Rostock, Springer, 395 p.

Communications sans actes

Paschos V., Bellalouna M., Khaznaji W. (2010), Well solved cases of probabilistic traveling salesman problem, 42èmes Journées de Statistique, Marseille, France

Milis I., Paschos V., Lucarelli G. (2007), On a generalized graph coloring/batch scheduling problem, Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2007), Paris, France

Paschos V., Monnot J., Toulouse S. (2002), Differential approximation of the traveling salesman problem, 6th Balkan Conference on Operational Research, Thessalonique, Grèce

Paschos V., Veslot H. (2001), Solving on line independent set by coloring vertices, 16th International Symposium on Computer and Information Sciences (ISCIS'01), Antalya, Turquie

Paschos V., Renotte L. (1998), Réductions continues: un outil pour préserver l'approximabilité, 4èmes Journées Nationale sur la Résolution Pratique des Problèmes NP-Complets (JNPC'98), Nantes, France

Murat C., Paschos V. (1998), The probabilistic longest path problem, 3rd International Symposium on Operations Research and its Applications (ISORA'98), Kunming, Chine

Alfandari L., Paschos V. (1997), Approximating the minimum weighted rooted spanning tree with radius less than two, EURO XV, INFORMS XXXIV, Barcelone, Espagne

Paschos V., Demange M. (1995), Maximum independent set and linear programming, Tenth International Symposium on Computer and Information Sciences (ISCIS'95), Kuşadası, Turquie

Pekergin F., Paschos V., Zissimopoulos V. (1992), Solving vertex cover, independent set and related problems by a Boltzmann machine, European Joint Conference on Engineering Systems Design and Analysis (ESDA), Istanbul, Turquie

Pekergin F., Zissimopoulos V., Paschos V. (1991), On the approximation of NP-complete problems by using Boltzmann machine method. The cases of some covering and packing problems, International Conference on Novel Methods in Optimization, Copenhague, Danemark

Paschos V. (1990), On the complexity of an optimisation problem in relational databases, 5th international Symposium on Computers and Information Sciences (ISCIS V), Nevsehir, Turquie

Prépublications / Cahiers de recherche

Bourgeois N., Catellier R., Denat T., Paschos V. (2015), Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the $\mathcal{G}(n,p)$ random model, Paris, Cahier du LAMSADE

Bourgeois N., Dabrowski K., Demange M., Paschos V. (2013), Playing with Parameters: Cross-parameterization in Graphs, Paris, Cahiers du Lamsade, 17 p.

Bonnet E., Escoffier B., Paschos V., Tourniaire E. (2012), Using greediness for parameterization: the case of max and min (k, n − k)-cut, Paris, Cahiers du Lamsade, 13 p.

Boria N., Murat C., Paschos V. (2012), An emergency management model for a wireless sensor network problem, Paris, Cahier du LAMSADE

Escoffier B., Paschos V., Tourniaire E. (2012), Moderate exponential time approximation and branching algorithms, Paris, Cahiers du Lamsade, 16 p.

Boria N., Paschos V. (2011), Optimization in dynamic environments, Paris, Cahier du LAMSADE, 48 p.

van Rooij J., Bourgeois N., Escoffier B., Paschos V. (2008), Fast algorithms for Max Independant Set in graphs of small average degree, Paris, Cahier du LAMSADE, 29 p.

Paschos V., Escoffier B., Bourgeois N. (2008), Efficient approximation by “low-complexity” exponential algorithms, Paris, Cahiers du LAMSADE, 26 p.

Escoffier B., Paschos V. (2007), Structures des classes d'approximation : un état de l'art, Paris, Cahier du LAMSADE, 51 p.

Telelis O., Zissimopoulos V., Paschos V. (2007), A robust 2-stage version for the Steiner tree problem, Paris, Annales du LAMSADE, 17 p.

Ausiello G., Giannakos A., Paschos V. (2006), On-line models for set-covering: the power of greediness, Paris, Cahier du LAMSADE, 17 p.

Giannakos A., Paschos V. (2006), Un tour d'horizon sur quelques classes de jeux combinatoires, Paris, Cahier du LAMSADE, 22 p.

Paschos V., Escoffier B. (2004), An Alternative proof of SAT NP-Completeness, Paris, Annales du LAMSADE, 207-213 p.

Paschos V. (2004), Annales du LAMSADE: numéro multi-thématique, Paris, Annales du LAMSADE, 323 p.

Paschos V. (2002), Annales du LAMSADE : numéro multi-thématique, Paris, Annales du LAMSADE, 384 p.

Paschos V., Demange M. (2002), Thoughts about new notions for the analysis of approximation algorithms, Paris, Université Paris-Dauphine, 62 p.

Paschos V., Demange M. (2001), Towards a general formal framework for polynomial approximation, Paris, Cahier du LAMSADE, 41 p.

Paschos V., Demange M. (2000), Approximation polynomiale : notions de difficulté et leur impact pour étudier la structure de NP, Paris, Cahier du LAMSADE, 20 p.

Murat C., Demange M., Toulouse S., Paschos V. (2000), Un nouveau modèle pour la construction de réseau de télécommunication à coût minimum, Paris, Cahier du LAMSADE, 15 p.

Blot J., Paschos V. (2000), Sur la convergence d'un système différentiel de premier ordre, vectoriel, ordinaire, linéaire non-homogene et non-autonome, Paris, Note de recherche du LAMSADE, 109 p.

Demange M., Paschos V. (1999), Approximation of weighted hereditary induced subgraph maximization problems, Paris, Cahier du LAMSADE, 10 p.

Demange M., Paschos V. (1999), Maximum-weight independent set is as "well" approximated as the unweighted one, Paris, Cahiers du LAMSADE

Retour à la liste