2013

Conference Contributions

• Paschos, Vangelis . Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation. 1st International Symposium and 10th Balkan Conference on Operational Research (BALCOR 2011). Thessalonique. Grèce. 2013.

2012

Articles

• Paschos, Vangelis ; Lucarelli, Giorgio ; Giannakos, Aristotelis ; Boria, Nicolas ; Ausiello, Giorgio . Online maximum k-coverage. Discrete Applied Mathematics. Volume 160. n° 13-14. 2012. pages 1901-1913. Elsevier. DOI http://dx.doi.org/10.1016/j.dam.2012.04.005.
• Paschos, Vangelis ; Escoffier, Bruno ; Bourgeois, Nicolas ; Van Rooij, Johan . Fast Algorithms for max independent set. Algorithmica. Volume 62. n° 1-2. 2012. pages 382-415. Springer. DOI http://dx.doi.org/10.1007/s00453-010-9460-7.
• Milis, Ioannis ; Paschos, Vangelis ; Pottié, Olivier ; Giannakos, Aristotelis ; Lucarelli, Giorgio ; Bourgeois, Nicolas . The max quasi-independent set problem. Journal of Combinatorial Optimization. Volume 23. n° 1. 2012. pages 94-117. Springer. DOI http://dx.doi.org/10.1007/s10878-010-9343-5.
• Paschos, Vangelis ; Della Croce, Federico . Efficient algorithms for the Max k-Vertex Cover problem. Journal of Combinatorial Optimization. 2012. Springer. DOI http://dx.doi.org/10.1007/s10878-012-9575-7.
• Boria, Nicolas ; Murat, Cécile ; Paschos, Vangelis . On the probabilistic min spanning tree Problem. Journal of Mathematical Modelling and Algorithms. Volume 11. n° 1. 2012. pages 45-76. Springer. DOI http://dx.doi.org/10.1007/s10852-011-9165-1.

Conference Contributions

• Boria, Nicolas ; Monnot, Jérôme ; Paschos, Vangelis . Reoptimization of the Maximum Weighted Pk-Free Subgraph Problem under Vertex Insertion. WALCOM 2012. Dhaka. Bangladesh. 2012.

Working Papers

• Boria, Nicolas ; Murat, Cécile ; Paschos, Vangelis . An emergency management model for a wireless sensor network problem. Université Paris-Dauphine . 2012 .
• Escoffier, Bruno ; Kim, Eun Jung ; Paschos, Vangelis . Subexponential and FPT-time Inapproximability of Independent Set and Related Problems. Université Paris-Dauphine . 2012 .
• Bourgeois, Nicolas ; Giannakos, Aristotelis ; Lucarelli, Giorgio ; Milis, Ioannis ; Paschos, Vangelis . Exact and approximation algorithms for densest k-subgraph. Université Paris-Dauphine . 2012 .

2011

Articles

• Boria, Nicolas ; Paschos, Vangelis . A survey on combinatorial optimization in dynamic environments. RAIRO Operations Research. Volume 45. n° 3. 2011. pages 241-294. Cambridge University Press. DOI http://dx.doi.org/10.1051/ro/2011114.
• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discrete Applied Mathematics. Volume 159. n° 17. 2011. pages 1954-1970. Elsevier. DOI http://dx.doi.org/10.1016/j.dam.2011.07.009.

Book chapters

• Paschos, Vangelis ; Escoffier, Bruno ; Bourgeois, Nicolas . An Introduction to Exponential Time Exact Algorithms for Solving NP-hard Problems. Mahjoub, Ridha. Progress in Combinatorial Optimization: Recent Progress. . 2011. pages chapter 15.

Conference Contributions

• Paschos, Vangelis ; Lucarelli, Giorgio ; Giannakos, Aristotelis ; Boria, Nicolas ; Ausiello, Giorgio . Online Maximum k-Coverage. Fundamentals of Computation Theory, FCT 2011. Berlin. Norvège. 2011.
• Boria, Nicolas ; Murat, Cécile ; Paschos, Vangelis . On the probabilistic min spanning tree problem. International Multiconference on Computer Science and Information Technology (IMCSIT 2010). Wisla. Pologne. 2010.

Working Papers

• Boria, Nicolas ; Paschos, Vangelis . Optimization in dynamic environments. Université Paris-Dauphine . 2011 .
• Boria, Nicolas ; Monnot, Jérôme ; Paschos, Vangelis . Reoptimization of maximum weight induced hereditary subgraph problems. Université Paris-Dauphine . 2011 .
• Kacem, Imed ; Paschos, Vangelis . Weighted completion time minimization on a single-machine with a fixed non-availability interval: differential approximability. Université Paris-Dauphine . 2011 .
• Escoffier, Bruno ; Paschos, Vangelis ; Tourniaire, Emeric . Approximating MAX SAT by moderately exponential algorithms. Université Paris-Dauphine . 2011 .
• Boria, Nicolas ; Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Exponential approximation schemata for some network design problems. Université Paris-Dauphine . 2011 .

2010

Articles

• Paschos, Vangelis ; Telelis, Orestis ; Zissimopoulos, Vassilis . Probabilistic models for the Steiner Tree problem. Networks. Volume 56. n° 1. 2010. pages 39-49. Wiley. DOI http://dx.doi.org/10.1002/net.20346.
• Lucarelli, Giorgio ; Milis, Ioannis ; Paschos, Vangelis . On the max-weight edge coloring problem. Journal of Combinatorial Optimization. Volume 20. n° 4. 2010. pages 429-442. Springer Netherlands. DOI http://dx.doi.org/10.1007/s10878-009-9223-z.
• Paschos, Vangelis ; Murat, Cécile . Probabilistic optimization in graph-problems. Algorithmic Operations Research. Volume 15. n° 1. 2010. pages 49-64. Preeminent Academic Facets Inc..
• Paschos, Vangelis ; Escoffier, Bruno . A Survey on the Structure of Approximation Classes. Computer Science Review. Volume 4. n° 1. 2010. pages 19-40. Elsevier. DOI http://dx.doi.org/10.1016/j.cosrev.2009.11.001.
• Calvo, Roberto Wolfler ; Paschos, Vangelis ; Della Croce, Federico . Approximating the Metric 2-Peripatetic Salesman Problem. Algorithmic Operations Research. Volume 5. n° 1. 2010. pages 13-20. Preeminent Academic Facets Inc..
• Paschos, Vangelis ; Boria, Nicolas . Fast Reoptimization for the Minimum Spanning Tree Problem. Journal of Discrete Algorithms. Volume 8. n° 3. 2010. pages 296-310. Elsevier. DOI http://dx.doi.org/10.1016/j.jda.2009.07.002.
• Bourgeois, Nicolas ; Lucarelli, Giorgio ; Milis, Ioannis ; Paschos, Vangelis . Approximating the max edge-coloring problem. Theoretical Computer Science. Volume 411. n° 34-36. 2010. pages 3055-3067. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2010.04.031.

Book chapters

• Paschos, Vangelis . Basic concepts in algorithms and complexity theory. Vangelis, Paschos, T.. Combinatorial Optimization Volume 1, Concepts of Combinatorial Optimization. London, Hoboken. 2010. pages 3-19.
• Paschos, Vangelis ; Demange, Marc . Polynomial approximation. Vangelis, Paschos, T.. Combinatorial Optimization Volume 2, Paradigmatic Problems and New Approaches. London, Hoboken. 2010. pages 313-349.
• Paschos, Vangelis ; Ausiello, Giorgio . Approximation preserving reductions. Paschos, Vangelis. Combinatorial Optimization Volume 2, Paradigmatic Problems and New Approaches. London, Hoboken. 2010. pages 351-380.
• Paschos, Vangelis ; Murat, Cécile . Probabilistic combinatorial optimization. Vangelis, Paschos, T.. Combinatorial optimization volume 2 Paradigms of combinatorial optimization : problems and new approaches. London, Hoboken. 2010. pages 588-613.
• Toulouse, Sophie ; Paschos, Vangelis ; Murat, Cécile ; Demange, Marc . A model for the design of a minimum-cost telecommunications network. Paschos, Vangelis T.. Combinatorial Optimization Volume 3, Applications. London, Hoboken. 2010. pages 209-224.

Conference Contributions

• Pottié, Olivier ; Paschos, Vangelis ; Milis, Ioannis ; Lucarelli, Giorgio ; Giannakos, Aristotelis ; Bourgeois, Nicolas . The Max Quasi-Independent Set Problem. Computer Science – Theory and Applications 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedings. Berlin. Russie. 2010.
• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . A Bottom-Up Method and Fast Algorithms for max independent set. 12th Scandinavian Symposium and Workshops on Algorithm Theory - SWAT'10. Bergen. Norvège. 2010.
• Van Rooij, Johan ; Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537^n). Theory and Applications of Models of Computation 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings. Berlin. République tchèque. 2010.
• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Fast Algorithms for min independent dominating set. SIROCCO 2010: 17th International Colloquium on Structural Information and Communication Complexity. Sirince. Turquie. 2010.
• Bellalouna, Monia ; Paschos, Vangelis ; Khaznaji, Walid . Well solved cases of probabilistic traveling salesman problem. 42èmes Journées de Statistique. Marseille. France. 2010.
• Bourgeois, Nicolas ; Della Croce, Federico ; Escoffier, Bruno ; Paschos, Vangelis . Exact Algorithms for Dominating Clique Problems. ISAAC 2009 20th International Symposium on Algorithms and Computation. Hawaï. États-Unis. 2009.
• Paschos, Vangelis . Approximation by Moderately Exponential Algorithms. Combinatorial Optimization ISCO2010. Recent Progress. London. Tunisie. 2011.

Books

• Paschos, Vangelis . Combinatorial Optimization Volume 1, Concepts of Combinatorial Optimization. . Wiley-VCH . 2010 . pages 368 . ISBN 978-1-84821-147-6 .
• Paschos, Vangelis . Combinatorial optimization Volume 2, Paradigms of Combinatorial Optimization: problems and new approaches. . Wiley-VCH . 2010 . pages 704 . ISBN 978-1-84821-148-3 .
• Paschos, Vangelis . Combinatorial Optimization Volume 3, Applications of Combinatorial Optimization. . Wiley-VCH . 2010 . pages 384 . ISBN 978-1-84821-149-0 .

2009

Articles

• Paschos, Vangelis ; Ausiello, Giorgio ; Bourgeois, Nicolas ; Giannakos, Aristotelis . Greedy algorithms for on-line set-covering. Algorithmic Operations Research. Volume 4. n° 1. 2009. pages 36-48. Preeminent Academic Facets Inc..
• Paschos, Vangelis ; Escoffier, Bruno ; Milanic, Martin . Simple and fast reoptimizations for the Steiner tree problem. Algorithmic Operations Research. Volume 4. n° 2. 2009. pages 86-94. Preeminent Academic Facets Inc..
• Paschos, Vangelis ; Escoffier, Bruno ; Bourgeois, Nicolas . Efficient approximation of MIN SET COVER by moderately exponential algorithms. Theoretical Computer Science. Volume 410. n° 21-23. 2009. pages 2184-2195. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2009.02.007.
• Ausiello, Giorgio ; Escoffier, Bruno ; Monnot, Jérôme ; Paschos, Vangelis . Reoptimization of minimum and maximum traveling salesman's tours. Journal of Discrete Algorithms. Volume 7. n° 4. 2009. pages 453-463. Elsevier. DOI http://dx.doi.org/10.1016/j.jda.2008.12.001.
• Murat, Cécile ; Escoffier, Bruno ; Della Croce, Federico ; Bourgeois, Nicolas ; Paschos, Vangelis . Probabilistic graph-coloring in bipartite and split graphs. Journal of Combinatorial Optimization. Volume 17. n° 3. 2009. pages 274-311. Springer Netherlands. DOI http://dx.doi.org/10.1007/s10878-007-9112-2.
• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Approximation of MIN COLORING by moderately exponential algorithms. Information Processing Letters. Volume 109. n° 16. 2009. pages 950-954. Elsevier. DOI http://dx.doi.org/10.1016/j.ipl.2009.05.002.
• Paschos, Vangelis ; Monnot, Jérôme ; Escoffier, Bruno ; Demange, Marc ; de Werra, Dominique . Weighted coloring on planar, bipartite and split graphs: complexity and approximation. Discrete Applied Mathematics. Volume 157. n° 4. 2009. pages 819-832. Elsevier. DOI http://dx.doi.org/10.1016/j.dam.2008.06.013.
• Paschos, Vangelis . An overview on polynomial approximation of NP-hard problems. Yugoslav Journal of Operations Research. Volume 19. n° 1. 2009. pages 3-40.
• Baburin, Aleksei ; Della Croce, Federico ; Gimadi, Edward ; Glazkov, Yuri ; Paschos, Vangelis . Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2. Discrete Applied Mathematics. Volume 157. n° 9. 2009. pages 1988-1992. Elsevier. DOI http://dx.doi.org/10.1016/j.dam.2008.06.025.

Conference Contributions

• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms. 11th International Symposium on Algorithms and Data Structures (WADS'09). Banff. Canada. 2009.
• Bourgeois, Nicolas ; Lucarelli, Giorgio ; Milis, Ioannis ; Paschos, Vangelis . Approximating the max edge-coloring problem. Combinatorial Algorithms 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28--July 2, 2009, Revised Selected Papers. Berlin. République tchèque. 2009.
• Lucarelli, Giorgio ; Milis, Ioannis ; Paschos, Vangelis . On the Maximum Edge Coloring Problem (Extended Abstract). 6th International Workshop on Approximation and Online Algorithms, WAOA 2008. Karlsruhe. Allemagne. 2008.

2008

Articles

• Paschos, Vangelis ; Della Croce, Federico . Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems. Operational Research. Volume 8. n° 3. 2008. pages 235-256. Springer. DOI http://dx.doi.org/10.1007/s12351-008-0020-8.

Book chapters

• Paschos, Vangelis ; Giannakos, Aristotelis ; Pottié, Olivier . Algorithmic games. Paschos, Vangelis. Combinatorial optimization and theoretical computer science: interfaces and perspectives. . 2008. pages 327-360.
• Della Croce, Federico ; Escoffier, Bruno ; Kaminski, Marcin ; Paschos, Vangelis . Worst-case complexity of exact algorithms for NP-hard problems. Paschos, Vangelis. Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives: 30th anniversary of the LAMSADE. Hoboken NJ. 2008. pages 203-240.
• Escoffier, Bruno ; Demange, Marc ; de Werra, Dominique ; Milis, Ioannis ; Lucarelli, Giorgio ; Paschos, Vangelis ; Monnot, Jérôme . Weighted edge coloring. Paschos, Vangelis. Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives: 30th anniversary of the LAMSADE. Hoboken NJ. 2008. pages 291-318.
• Paschos, Vangelis ; Giannakos, Aristotelis ; Ausiello, Giorgio . Online models for set-covering: the flaw of greediness. Paschos, Vangelis. Combinatorial optimization and theoretical computer science: interfaces and perspectives : 30th anniversary of the LAMSADE. London. 2008. pages 65-85.
• Murat, Cécile ; Gabrel, Virginie ; Paschos, Vangelis . Mission planning for observation satellites. G. Finke. Operations research and networks. . 2008. pages -.
• Escoffier, Bruno ; Demange, Marc ; Paschos, Vangelis ; de Werra, Dominique ; Monnot, Jérôme . Complexity and approximation results for the min weighted node coloring problem. Paschos, Vangelis. Combinatorial optimization and theoretical computer science: interfaces and perspectives. . 2008. pages 251-280.

Conference Contributions

• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs. Third International Workshop on Parameterized and Exact Computation Parameterized and Exact Computation (IWPEC 2008). Victoria. Canada. 2008.
• Murat, Cécile ; Paschos, Vangelis . Vertex-uncertainty in graph-problems. Second International Conference on Combinatorial Optimization and Applications (COCOA'08) LNCS 5165. St John's. Canada. 2008.

Working Papers

• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis . Efficient approximation by “low-complexity” exponential algorithms. Université Paris-Dauphine . 2008 .
• Bourgeois, Nicolas ; Escoffier, Bruno ; Paschos, Vangelis ; van Rooij, Johan . Fast algorithms for Max Independant Set in graphs of small average degree. Université Paris-Dauphine . 2008 .

Books

• Paschos, Vangelis . Combinatorial optimization and theoretical computer science: interfaces and perspectives: 30th anniversary of the LAMSADE. Hoboken NJ. Wiley . 2008 . pages 515 . ISBN .

2007

Articles

• Paschos, Vangelis ; Della Croce, Federico ; Escoffier, Bruno . Improved worst-case complexity for the MIN 3-SET COVERING problem. Operations Research Letters. Volume 35. n° 2. 2007. pages 205-210. Elsevier. DOI http://dx.doi.org/10.1016/j.orl.2006.02.004.
• Paschos, Vangelis ; Escoffier, Bruno . Differential approximation of MIN SAT, MAX SAT and related problems. European Journal of Operational Research. Volume 181. n° 2. 2007. pages 620-633. Elsevier. DOI http://dx.doi.org/10.1016/j.ejor.2005.04.057.
• Kaminski, Marcin ; Della Croce, Federico ; Paschos, Vangelis . An exact algorithm for MAX CUT in sparse graphs. Operations Research Letters. Volume 35. n° 3. 2007. pages 403-408. Elsevier. DOI http://dx.doi.org/10.1016/j.orl.2006.04.001.
• Demange, Marc ; de Werra, Dominique ; Monnot, Jérôme ; Paschos, Vangelis . Time slot scheduling of compatible jobs. Journal of Scheduling. Volume 10. n° 2. 2007. pages 111-127. DOI http://dx.doi.org/10.1007/s10951-006-0003-7.

Book chapters

• Paschos, Vangelis ; Ausiello, Giorgio . Differential ratio approximation. T. F. Gonzalez. Handbook of Approximation Algorithms and Metaheuristics. Boca Raton. 2007.
• Paschos, Vangelis ; Giannakos, Aristotelis . Quand l'optimisation fait du beau jeu : une vision algorithmique de la théorie des jeux. Paschos, Vangelis. Optimisation combinatoire 5 : problèmes paradigmatiques et nouvelles problématiques. Paris. 2007. pages 207-240.
• Paschos, Vangelis ; Ausiello, Giorgio . Reductions that preserve approximability. T. F. Gonzalez. Handbook of Approximation Algorithms and Metaheuristics. Boca Raton, FL. 2007.

Conference Contributions

• Lucarelli, Giorgio ; Milis, Ioannis ; Paschos, Vangelis . On a generalized graph coloring/batch scheduling problem. Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2007). Paris. France. 2007.
• Paschos, Vangelis ; Telelis, Orestis ; Zissimopoulos, Vassilis . Steiner forests on stochastic metric graphs. First International Conference on Combinatorial Optimization and Applications (COCOA'07). Berlin. Chine. 2007.
• Giannakos, Aristotelis ; Gourvès, Laurent ; Monnot, Jérôme ; Paschos, Vangelis . On the performance of congestion games for optimum satisfiability problems. Internet and Network Economics 3rd International Workshop, WINE 2007, San Diego, CA, USA, December 12-14, 2007, Proceedings. San Diego. États-Unis. 2007.

Working Papers

• Paschos, Vangelis ; Telelis, Orestis ; Zissimopoulos, Vassilis . A robust 2-stage version for the Steiner tree problem. Université Paris-Dauphine . 2007 .
• Escoffier, Bruno ; Paschos, Vangelis . Structures des classes d'approximation : un état de l'art. Université Paris-Dauphine . 2007 .

Books

• Paschos, Vangelis . Optimisation combinatoire. 5, Problèmes paradigmatiques et nouvelles problématiques. Paris. Hermès Science : Lavoisier . 2007 . pages 271 . ISBN 978-2-7462-1696-9 .
• Paschos, Vangelis . Optimisation combinatoire. 4, problèmes paradigmatiques. Paris. Hermès Science : Lavoisier . 2007 . pages 215 . ISBN 978-2-7462-1180-3 .

2006

Articles

• Ausiello, Giorgio ; Paschos, Vangelis . Reductions, completeness and the hardness of approximability. European Journal of Operational Research. Volume 172. n° 3. 2006. pages 719-739. Elsevier. DOI http://dx.doi.org/10.1016/j.ejor.2005.06.006.
• Paschos, Vangelis ; Escoffier, Bruno . On-line models and algorithms for max independent set. RAIRO Operations Research. Volume 40. n° 2. 2006. pages 129-142. EDP Sciences. DOI http://dx.doi.org/10.1051/ro:2006014.
• Paschos, Vangelis ; Escoffier, Bruno ; Monnot, Jérôme . Weighted coloring: further complexity and approximability results. Information Processing Letters. Volume 97. n° 3. 2006. pages 98-103. Elsevier. DOI http://dx.doi.org/10.1016/j.ipl.2005.09.013.
• Paschos, Vangelis ; Escoffier, Bruno . Completeness in approximation classes beyond APX. Theoretical Computer Science. Volume 359. n° 1-3. 2006. pages 369-377. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2006.05.023.
• Murat, Cécile ; Paschos, Vangelis . On the probabilistic minimum coloring and minimum k-coloring. Discrete Applied Mathematics. Volume 154. n° 3. 2006. pages 564-586. Elsevier. DOI http://dx.doi.org/10.1016/j.dam.2005.06.007.
• Paschos, Vangelis . Review of Jon Lee's book "A First Course in Combinatorial Optimization", CambridgeTexts in Applied Mathematics. European Journal of Operational Research. Volume 168. n° 3. 2006. pages 1042-1044. Elsevier. DOI http://dx.doi.org/10.1016/j.ejor.2005.01.003.

Conference Contributions

• Ausiello, Giorgio ; Escoffier, Bruno ; Monnot, Jérôme ; Paschos, Vangelis . Reoptimization of minimum and maximum traveling salesman's tours. 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Berlin. Lettonie. 2006.
• Ausiello, Giorgio ; Giannakos, Aristotelis ; Paschos, Vangelis . Greedy algorithms for on-line set-covering and related problems. Twelfth Computing: The Australasian Theory Symposium (CATS'06). Hobart. Australie. 2006.

Working Papers

• Ausiello, Giorgio ; Giannakos, Aristotelis ; Paschos, Vangelis . On-line models for set-covering: the power of greediness. Université Paris-Dauphine . 2006 .
• Giannakos, Aristotelis ; Paschos, Vangelis . Un tour d'horizon sur quelques classes de jeux combinatoires. Université Paris-Dauphine . 2006 .

Books

• Murat, Cécile ; Paschos, Vangelis . Probabilistic combinatorial optimization on graphs. London Newport Beach. ISTE . 2006 . pages 267 . ISBN 1-905209-33-9 .
• Paschos, Vangelis . Optimisation combinatoire. 3, Applications. Paris. Hermès Science : Lavoisier . 2006 . pages 339 . ISBN 2-7462-1179-3 .

2005

Articles

• Paschos, Vangelis ; Demange, Marc ; Paradon, Xavier . On-line maximum-order induced hereditary subgraph problems. International Transactions in Operational Research. Volume 12. n° 2. 2005. pages 185-201. Blackwell Publishing Limited. DOI http://dx.doi.org/10.1111/j.1475-3995.2005.00497.x.
• Demange, Marc ; Paschos, Vangelis . Polynomial approximation algorithms with performance guarantees: an introduction-by-example. European Journal of Operational Research. Volume 165. n° 3. 2005. pages 555-568. Elsevier. DOI http://dx.doi.org/10.1016/j.ejor.2004.03.021.
• Demange, Marc ; Bazgan, Cristina ; Ausiello, Giorgio ; Paschos, Vangelis . Completeness in differential approximation classes. International Journal of Foundations of Computer Science. Volume 16. n° 6. 2005. pages 1267-1295. World Scientific Publishing Company.
• Bazgan, Cristina ; Escoffier, Bruno ; Paschos, Vangelis . Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness. Theoretical Computer Science. Volume 339. n° 2-3. 2005. pages 272-292. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2005.03.007.
• Bazgan, Cristina ; Monnot, Jérôme ; Paschos, Vangelis ; Serrière, Fabrice . On the differential approximation of MIN SET COVER. Theoretical Computer Science. Volume 332. n° 1-3. 2005. pages 497-513. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2004.12.022.
• Demange, Marc ; Monnot, Jérôme ; Paschos, Vangelis ; de Werra, Dominique . A hypocoloring model for batch scheduling. Discrete Applied Mathematics. Volume 146. n° 1. 2005. pages 3-26. Elsevier. DOI http://dx.doi.org/10.1016/j.dam.2004.06.016.
• Escoffier, Bruno ; Paschos, Vangelis . Proving completeness by logic. International Journal of Computer Mathematics. Volume 82. n° 2. 2005. pages 151-161. Taylor & Francis. DOI http://dx.doi.org/10.1080/00207160412331296625.
• Demange, Marc ; Paschos, Vangelis . Improved approximations for weighted and unweighted graph problems. Theory of Computing Systems. Volume 38. n° 6. 2005. pages 763-787. Springer. DOI http://dx.doi.org/10.1007/s00224-004-1162-6.
• Demange, Marc ; Paschos, Vangelis . On-line vertex-covering. Theoretical Computer Science. Volume 332. n° 1-3. 2005. pages 83-108. Elsevier. DOI http://dx.doi.org/10.1016/j.tcs.2004.08.015.

Book chapters

• Ausiello, Giorgio ; Paschos, Vangelis . Réductions préservant l'approximabilité. Vangelis Paschos. Optimisation combinatoire 2: concepts avancés (Traité IC2, série Informatique et systèmes d'information). Paris. 2005.
• Demange, Marc ; Paschos, Vangelis . Approximation polynomiale. Vangelis Paschos. Optimisation combinatoire 2: concepts avancés (Traité IC2, série Informatique et systèmes d'information). Paris. 2005.
• Paschos, Vangelis ; Murat, Cécile . L'optimisation combinatoire probabiliste. Paschos, Vangelis. Optimisation combinatoire 2: concepts avancés. Paris. 2005.

Conference Contributions

• Della Croce, Federico ; Paschos, Vangelis . Computing optimal solutions for the MIN SET 3-COVERING problem. Algorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings. Berlin. Chine. 2005.
• Escoffier, Bruno ; Monnot, Jérôme ; Paschos, Vangelis . Weighted coloring: further complexity and approximability results. 9th Italian Conference on Theoretical Computer Science (ICTCS'05). Berlin. Italie. 2005.
• Bazgan, Cristina ; Monnot, Jérôme ; Paschos, Vangelis ; Serrière, Fabrice . Greedy differential approximations for MIN SET COVER. SOFSEM 2005: Theory and Practice of Computer Science 31st Conference on Current Trends in Theory and Practice of Computer Science, Liptovský Ján, Slovakia, January 22-28, 2005, Proceedings. Berlin. Slovaquie. 2005.
• Escoffier, Bruno ; Paschos, Vangelis . Differential approximation of MIN SAT, MAX SAT and related problems. International Conference on Computational Science and Its Applications (ICCSA'05). Berlin. Singapour. 2005.
• Della Croce, Federico ; Escoffier, Bruno ; Murat, Cécile ; Paschos, Vangelis . Probabilistic coloring of bipartite and split graphs. International Conference on Computational Science and Its Applications (ICCSA'05). Singapour. Singapour. 2005.

Books

• Paschos, Vangelis . Optimisation combinatoire. 1, Concepts fondamentaux. Paris. Hermès Science : Lavoisier . 2005 . pages 349 . ISBN 2-7462-1038-X .
• Paschos, Vangelis . Optimisation combinatoire. 2, Concepts avancés. Paris. Hermès Science : Lavoisier . 2005 . pages 298 . ISBN 2-7462-1039-8 .

2004

Articles

• Ekim, Tinaz ; Paschos, Vangelis . Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximation. International Journal of Computer Mathematics. Volume 81. n° 5. 2004. pages 569-582. Taylor & Francis. DOI http://dx.doi.org/10.1080/00207160410001688592.
• Ausiello, Giorgio ; Demange, Marc ; Laura, Luigi ; Paschos, Vangelis . Algorithms for the on-line quota traveling salesman problem. Information Processing Letters. Volume 92. n° 2. 2004. pages 89-94. Elsevier. DOI http://dx.doi.org/10.1016/j.ipl.2004.06.013.
• Zissimopoulos, Vassilis ; Hifi, Mhand ; Paschos, Vangelis . A simulated annealing approach for the circular cutting problem. European Journal of Operational Research. Volume 159. n° 2. 2004. pages 430-448. Elsevier. DOI http://dx.doi.org/10.1016/S0377-2217(03)00417-X.
• Toulouse, Sophie ; Paschos, Vangelis ; Monnot, Jérôme . Local approximations for maximum partial subgraph problem. Operations Research Letters. Volume 32. n° 3. 2004. pages 217-224. Elsevier. DOI http://dx.doi.org/10.1016/j.orl.2003.08.004.
• Grosso, Andrea ; Della Croce, Federico ; Paschos, Vangelis . Lower bounds on the approximation ratios of leading heuristics for the single machine total tardiness problem. Journal of Scheduling. Volume 7. n° 1. 2004. pages 85-91. Springer. DOI http://dx.doi.org/10.1023/B:JOSH.0000013056.09936.fd.
• Paschos, Stratos ; Paschos, Vangelis ; Zissimopoulos, Vassilis . The antennas preassignment problem. Chaos, Solitons and Fractals. Volume 22. n° 4. 2004. pages 821-829. Elsevier. DOI http://dx.doi.org/10.1016/j.chaos.2004.02.049.

Conference Contributions

• de Werra, Dominique ; Demange, Marc ; Escoffier, Bruno ; Monnot, Jérôme ; Paschos, Vangelis . Weighted coloring on planar, bipartite and split graphs: complexity and improved approximation. Algorithms and Computation 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings. Berlin. Chine. 2004.
• Bazgan, Cristina ; Escoffier, Bruno ; Paschos, Vangelis . Poly-APX- and PTAS-completeness in standard and differential approximation. ISAAC'04 :15th International Symposium. Hong Kong. Chine. 2004.
• Ausiello, Giorgio ; Demange, Marc ; Laura, Luigi ; Paschos, Vangelis . Algorithms for the on-line quota traveling salesman problem. 10th Annual International Conference on Computing and Combinatorics (COCOON'04). Berlin. Corée du Sud. 2004.
• de Werra, Dominique ; Demange, Marc ; Monnot, Jérôme ; Paschos, Vangelis . The hypocoloring problem: complexity and approximability results when the chromatic number is small. 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'04). Bad Honnef. Allemagne. 2004.

Working Papers

• Escoffier, Bruno ; Paschos, Vangelis . An Alternative proof of SAT NP-Completeness. Université Paris-Dauphine . 2004 .
• Paschos, Vangelis . Annales du LAMSADE: numéro multi-thématique. Université Paris-Dauphine . 2004 .

Books

• Paschos, Vangelis . Complexité et approximation polynomiale. Paris. Hermès Science . 2004 . pages 270 . ISBN 2-7462-0936-5 .

2003

Articles

• Paschos, Vangelis . Polynomial approximation and graph-coloring. Computing. Volume 70. n° 1. 2003. pages 41-86. Springer Wien. DOI http://dx.doi.org/10.1007/s00607-002-1468-7.
• Bazgan, Cristina ; Paschos, Vangelis . Differential approximation for satisfiability and related problems. European Journal of Operational Research. Volume 147. n° 2. 2003. pages 397-404. Elsevier. DOI http://dx.doi.org/10.1016/S0377-2217(02)00299-0.
• Toulouse, Sophie ; Paschos, Vangelis ; Monnot, Jérôme . Differential approximation results for the traveling salesman problem with distances 1 and 2. European Journal of Operational Research. Volume 145. n° 3. 2003. pages 557-568. DOI http://dx.doi.org/10.1016/S0377-2217(02)00222-9.
• Monnot, Jérôme ; Demange, Marc ; Paschos, Vangelis . Differential approximation results for the Steiner tree problem. Applied Mathematics Letters. Volume 16. n° 5. 2003. pages 733-739. Elsevier. DOI http://dx.doi.org/10.1016/S0893-9659(03)00075-2.
• Monnot, Jérôme ; Paschos, Vangelis ; Toulouse, Sophie . Optima locaux garantis pour l'approximation différentielle. Technique et Science Informatiques. Volume 22. n° 3. 2003. pages 257-288. Hermès. DOI http://dx.doi.org/10.3166/tsi.22.257-288.
• Paschos, Vangelis ; Monnot, Jérôme ; Toulouse, Sophie . Approximation algorithms for the traveling salesman problem. Mathematical Methods of Operational Research. Volume 56. n° 3. 2003. pages 387-405. Springer. DOI http://dx.doi.org/10.1007/s001860200239.
• Paschos, Vangelis . Approximation, complexity, optimization: a 3-dimensional matching full of interest. AIROnews. Volume 8. n° 2. 2003. pages 1-4. Associazione Italiana di Ricerca Operativa.

Conference Contributions

• Ausiello, Giorgio ; Bazgan, Cristina ; Demange, Marc ; Paschos, Vangelis . Completeness in differential approximation classes. 28th International Symposium on Mathematical Foundations of Computer Science (MFCS'03). Berlin. Slovaquie. 2003.

Books

• Toulouse, Sophie ; Paschos, Vangelis ; Monnot, Jérôme . Approximation polynomiale des problèmes NP-difficiles : optima locaux et rapport différentiel. Paris. Hermès Science . 2003 . pages 221 . ISBN .

2002

Articles

• Likas, Aris ; Paschos, Vangelis . A note on a new greedy-solution representation and a new greedy parallelizable heuristic for the traveling salesman problem. Chaos, Solitons and Fractals. Volume 13. n° 1. 2002. pages 71-78. Elsevier. DOI http://dx.doi.org/10.1016/S0960-0779(00)00227-7.
• Paschos, Vangelis ; Murat, Cécile . The probabilistic minimum vertex covering problem. International Transactions in Operational Research. Volume 9. n° 1. 2002. pages 19-32. Blackwell Publishing Limited.
• Murat, Cécile ; Paschos, Vangelis . A priori optimization for the probabilistic maximum independent set problem. Theoretical Computer Science. Volume 270. n° 1-2. 2002. pages 561-590. Elsevier. DOI http://dx.doi.org/10.1016/S0304-3975(01)00005-6.
• Demange, Marc ; Paschos, Vangelis . Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation. RAIRO Operations Research. Volume 36. n° 3. 2002. pages 237-277. EDP Sciences. DOI http://dx.doi.org/10.1051/ro:2003005.

Book chapters

• Paschos, Vangelis ; Murat, Cécile ; Gabrel, Virginie . Planification de prises de vue par satellite. Finke, Gerd. Recherche opérationnelle et réseaux: Méthodes d'analyse spatiale (Traité IGAT, série Aspects fondamentaux de l'analyse spatiale). Paris. 2002.

Conference Contributions

• Monnot, Jérôme ; Paschos, Vangelis ; Toulouse, Sophie . Differential approximation of the traveling salesman problem. 6th Balkan Conference on Operational Research. Thessalonique. Grèce. 2002.
• Demange, Marc ; de Werra, Dominique ; Monnot, Jérôme ; Paschos, Vangelis . Weighted node coloring: when stable sets are expensive. 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'02). Berlin. République tchèque. 2002.

Working Papers

• Demange, Marc ; Paschos, Vangelis . Thoughts about new notions for the analysis of approximation algorithms. Université Paris-Dauphine . 2002 .
• Paschos, Vangelis . Annales du LAMSADE : numéro multi-thématique. Université Paris-Dauphine . 2002 .

2001

Articles

• Paschos, Vangelis . A note on the approximation ratio of graph-coloring. Foundations of Computing and Decision Sciences. Volume 26. n° 4. 2001.
• Demange, Marc ; Monnot, Jérôme ; Paschos, Vangelis . Maximizing the number of unused bins. Foundations of Computing and Decision Sciences. Volume 26. n° 1. 2001. pages 169-186. Politechnika Poznanska.
• Paschos, Vangelis . On-line independent set by coloring vertices. Operational Research. Volume 1. n° 3. 2001. pages 213-224. Springer. DOI http://dx.doi.org/10.1007/BF02936352.
• Demange, Marc ; Monnot, Jérôme ; Paschos, Vangelis . Maximizing the number of unused bins by first-fit-decreasing. Foundations of Computing and Decision Sciences. Volume 26. n° 1. 2001. Poznań University of Technology.

Conference Contributions

• Monnot, Jérôme ; Paschos, Vangelis ; Toulouse, Sophie . Differential approximation results for the traveling salesman problem with distances 1 and 2. Fundamentals of Computation Theory 13th International Symposium, FCT 2001, Riga, Latvia, August 22-24, 2001. Proceedings. Berlin. Lettonie. 2001.
• Paschos, Vangelis ; Veslot, Hélène . Solving on line independent set by coloring vertices. 16th International Symposium on Computer and Information Sciences (ISCIS'01). Antalya. Turquie. 2001.

Working Papers

• Demange, Marc ; Paschos, Vangelis . Towards a general formal framework for polynomial approximation. Université Paris-Dauphine . 2001 .

2000

Articles

• Paschos, Vangelis . Studying graph-stability to apprehend relative hardness of constructive -non constructive approximation. Bulletin of the Greek Mathematical Society. Volume 43. 2000. pages 37-54. Greek Mathematical Society.
• Alfandari, Laurent ; Paschos, Vangelis . Master-slave strategies and polynomial approximation. Computational Optimization and Applications. Volume 16. 2000. pages 231-245. Springer.
• Zissimopoulos, Vassilis ; Paschos, Vangelis ; Hifi, Mhand . A neural network for the minimum set covering problem. Chaos, Solitons and Fractals. Volume 11. n° 13. 2000. pages 2079-2089. Elsevier. DOI http://dx.doi.org/10.1016/S0960-0779(99)00104-6.

Conference Contributions

• Demange, Marc ; Paradon, Xavier ; Paschos, Vangelis . On-line maximum-order induced hereditary subgraph problems. 27th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM'00). Berlin. République tchèque. 2000.

Working Papers

• Blot, Joël ; Paschos, Vangelis . Sur la convergence d'un système différentiel de premier ordre, vectoriel, ordinaire, linéaire non-homogene et non-autonome. Université Paris-Dauphine . 2000 .
• Demange, Marc ; Paschos, Vangelis . Approximation polynomiale : notions de difficulté et leur impact pour étudier la structure de NP. Université Paris-Dauphine . 2000 .
• Demange, Marc ; Murat, Cécile ; Paschos, Vangelis ; Toulouse, Sophie . Un nouveau modèle pour la construction de réseau de télécommunication à coût minimum. Université Paris-Dauphine . 2000 .

1999

Articles

• Paschos, Vangelis ; Murat, Cécile . The probabilistic longest path problem. Networks. Volume 33. n° 3. 1999. pages 207-219. Wiley InterScience.
• Della Croce, Federico ; Paschos, Vangelis ; Tsoukiàs, Alexis . An improved general procedure for lexicographic bottleneck problems. Operations Research Letters. Volume 24. n° 4. 1999. pages 187-194. Elsevier. DOI http://dx.doi.org/10.1016/S0167-6377(99)00013-9.
• Demange, Marc ; Monnot, Jérôme ; Paschos, Vangelis . Bridging gap between standard and differential polynomial approximation: the case of bin-packing. Applied Mathematics Letters. Volume 12. n° 7. 1999. pages 127-133. Elsevier. DOI http://dx.doi.org/10.1016/S0893-9659(99)00112-3.
• Demange, Marc ; Paschos, Vangelis . Asymptotic differential approximation ratio: definitions, motivations and an application to bin-packing. RAIRO Operations Research. Volume 33. n° 4. 1999. pages 481-507. EDP.
• Alfandari, Laurent ; Paschos, Vangelis . Approximating minimum spanning tree of depth 2. International Transactions in Operational Research. Volume 6. n° 6. 1999. pages 607-622. Wiley. DOI http://dx.doi.org/10.1111/j.1475-3995.1999.tb00176.x.

Working Papers

• Demange, Marc ; Paschos, Vangelis . Maximum-weight independent set is as "well" approximated as the unweighted one. Université Paris-Dauphine . 1999 .
• Demange, Marc ; Paschos, Vangelis . Approximation of weighted hereditary induced subgraph maximization problems. Université Paris-Dauphine) . 1999 .

1998

Articles

• Stafylopatis, Andreas ; Paschos, Vangelis ; Fernandez de la Vega, Wenceslas . Average-case complexity for the execution of recursive definitions on relational databases. Acta Informatica. Volume 35. n° 3. 1998. pages 211-243. Springer. DOI http://dx.doi.org/10.1007/s002360050119.
• Demange, Marc ; Grisoni, Pascal ; Paschos, Vangelis . Differential approximation algorithms for some combinatorial optimization problems. Theoretical Computer Science. Volume 209. n° 1-2. 1998. pages 107-122. Elsevier. DOI http://dx.doi.org/10.1016/S0304-3975(97)00099-6.

Conference Contributions

• Murat, Cécile ; Paschos, Vangelis . A priori optimization of the probabilistic maximum independent set. International Symposium on Computer and Information Sciences (ISCIS'98). Antalya. Turquie. 1998.
• Murat, Cécile ; Paschos, Vangelis . The probabilistic longest path problem. 3rd International Symposium on Operations Research and its Applications (ISORA'98). Kunming. Chine. 1998.
• Alfandari, Laurent ; Paschos, Vangelis . On the approximation of some spanning-arborescence problems. Advances in Computer and Information Science '98. Proceedings of the 13th International Symposium on Computer and Information Sciences. Amsterdam. Turquie. 1998.
• Paschos, Vangelis ; Renotte, Laure . 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. 1998.

1997

Articles

• Paschos, Vangelis . A survey of approximately optimal solutions to some covering and packing problems. ACM Computing Surveys. Volume 29. n° 2. 1997. pages 171-209. ACM. DOI http://doi.acm.org/10.1145/254180.254190.
• Demange, Marc ; Paschos, Vangelis . Improved approximations for maximum independent set via approximation chains. Applied Mathematics Letters. Volume 10. n° 3. 1997. pages 105-110. Elsevier. DOI http://dx.doi.org/10.1016/S0893-9659(97)00044-X.
• Gabrel, Virginie ; Moulet, Alain ; Murat, Cécile ; Paschos, Vangelis . A new single model and derived algorithms for the satellite shots planning problem using graph theory concepts. Annals of Operations Research. Volume 69. n° 0. 1997. pages 115-134. Springer Netherlands. DOI http://dx.doi.org/10.1023/A:1018920709696.
• Paschos, Vangelis ; Demange, Marc . A generalization of König-Egervary graphs and heuristics for maximum independent set problem with improved approximation ratios. European Journal of Operational Research. Volume 97. n° 3. 1997. pages 580-592. Elsevier. DOI http://dx.doi.org/10.1016/S0377-2217(96)00271-8.
• Demange, Marc ; Paschos, Vangelis . The approximability behavior of some combinatorial problems with respect to the approximability of a class of maximum independent set problems. Computational Optimization and Applications. Volume 7. n° 3. 1997. pages 307-324. Springer. DOI http://dx.doi.org/10.1023/A:1008660812834.

Conference Contributions

• Alfandari, Laurent ; Paschos, Vangelis . Approximating the minimum weighted rooted spanning tree with radius less than two. EURO XV, INFORMS XXXIV. Barcelone. Espagne. 1997.

1996

Articles

• Benkouar, A. ; Manoussakis, Yannis ; Paschos, Vangelis ; Saad, Rachid . Hamiltonian problems in edge-colored complete graphs and Eulerian cycles in edge-colored graphs: some complexity results. RAIRO Operations Research. Volume 30. n° 4. 1996. EDP Sciences.
• Demange, Marc ; Paschos, Vangelis . On an approximation measure founded on the links between optimization and polynomial approximation theory. Theoretical Computer Science. Volume 158. n° 1-2. 1996. pages 117-141. Elsevier. DOI http://dx.doi.org/10.1016/0304-3975(95)00060-7.
• Demange, Marc ; Paschos, Vangelis . Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale. Mathématiques, Informatique et Sciences Humaines. Volume 135. 1996. EHESS.

Conference Contributions

• Demange, Marc ; Paschos, Vangelis . Constructive-non-constructive approximation and maximum independent set problem. 8th Franco-Japanese and 4th Franco-Chinese Conference on Combinatorics and Computer Science (CCS'95). Brest. France. 1995.

1995

Articles

• Paschos, Vangelis ; Renotte, Laure . Approximability preserving reductions for NP-complete problems. Foundations of Computing and Decision Sciences. Volume 20. n° 1. 1995. Poznań University of Technology.
• Fernandez de la Vega, Wenceslas ; Blot, Joël ; Paschos, Vangelis ; Saad, Rachid . Average case analysis of greedy algorithms for optimisation problems on set systems. Theoretical Computer Science. Volume 147. n° 1-2. 1995. pages 267-298. Elsevier. DOI http://dx.doi.org/10.1016/0304-3975(95)00242-O.
• Paschos, Vangelis . A note on the improvement of the maximum independent set's approximation ratio. Yugoslav Journal of Operations Research. Volume 5. n° 1. 1995. University of Belgrad, Faculty of Organizational Sciences, et. al.
• Afif, Mohamed ; Likas, Aris ; Paschos, Vangelis . A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem. Chaos, Solitons and Fractals. Volume 5. n° 5. 1995. pages 739-746. Elsevier. DOI http://dx.doi.org/10.1016/0960-0779(94)00175-P.
• Bellalouna, Monia ; Murat, Cécile ; Paschos, Vangelis . Probabilistic combinatorial optimization problems: a new domain in Operational Research. European Journal of Operational Research. Volume 87. n° 3. 1995. pages 693-706. Elsevier. DOI http://dx.doi.org/10.1016/0377-2217(95)00240-5.
• Afif, Mohamed ; Hifi, Mhand ; Paschos, Vangelis ; Zissimopoulos, Vassilis . A new efficient heuristic for minimum set covering problem. Journal of the Operational Research Society. Volume 46. n° 10. 1995. pages 1260-1268. Palgrave. DOI http://dx.doi.org/10.1057/jors.1995.173.
• Murat, Cécile ; Paschos, Vangelis . Problème du stable probabiliste. Comptes Rendus de l'Académie des Sciences de Paris. Volume 321. n° 4. 1995. pages 495-498. Elsevier.
• Blot, Joël ; Fernandez de la Vega, Wenceslas ; Paschos, Vangelis ; Saad, Rachid . Analyse en moyenne de la performance des algorithmes gloutons pour des problèmes d'optimisation sur des systèmes d'ensembles. Comptes Rendus de l'Académie des Sciences - Series I - Mathematics. Volume 321. 1995. Elsevier.
• Paschos, Vangelis ; Demange, Marc . 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 de l'Académie des Sciences - Series I - Mathematics. Volume 321. 1995. Elsevier.

Conference Contributions

• Murat, Cécile ; Paschos, Vangelis . The probabilistic maximum independent set problem. 7th International Symposium on Applied Stochastic Models and Data Analysis (ASMDA'95). Ulster. Irlande. 1995.
• Demange, Marc ; Paschos, Vangelis . Maximum independent set and linear programming. Proceedings of the Tenth International Symposium on Computer and Information Sciences: held at Kuşadası, Aydın, Turkey, Octomber 30-November 1, 1995. Kuşadası. Turquie. 1995.

1994

Articles

• Demange, Marc ; Grisoni, Pascal ; Paschos, Vangelis . 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. Volume 318. 1994. pages 289-292. Académie des Sciences.
• Paschos, Vangelis ; Demange, Marc . Approximation algorithms for minimum set covering problem: a survey. Foundations of Computing and Decision Sciences. Volume 19. n° 3. 1994. Poznań University of Technology.
• Paschos, Vangelis . A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set. RAIRO Operations Research. Volume 28. n° 4. 1994. pages 413-433. EDP Sciences.
• Paschos, Vangelis ; Grisoni, Pascal ; Demange, Marc . Approximation results for the minimum graph coloring problem. Information Processing Letters. Volume 50. n° 1. 1994. pages 19-23. Elsevier. DOI http://dx.doi.org/10.1016/0020-0190(94)90039-6.

1993

Articles

• Paschos, Vangelis ; Pekergin, Ferhan ; Zissimopoulos, Vassilis . Approximating the optimal solutions of some hard graph problems by a Boltzmann machine. Belgian Journal of Operations Research, Statistics and Computer Science. Volume 33. n° 2. 1993. pages 119-132.
• Demange, Marc ; Paschos, Vangelis . 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 de l'Académie des Sciences - Series I - Mathematics. Volume 317. n° 4. 1993. pages 409-414. Elsevier.

1992

Articles

• Paschos, Vangelis ; Stafylopatis, Andreas . Evaluation of the execution cost of recursive definitions. Computer Journal. Volume 35. 1992. Oxford University Press.
• Paschos, Vangelis . A (°/2)-approximation algorithm for the maximum independent set problem. Information Processing Letters. Volume 44. n° 1. 1992. pages 11-13. Elsevier. DOI http://dx.doi.org/10.1016/0020-0190(92)90248-T.

Conference Contributions

• Fernandez de la Vega, Wenceslas ; Paschos, Vangelis ; Saad, Rachid . Average case analysis of a greedy algorithm for the minimum hitting set problem. LATIN '92 1st Latin American Symposium on Theoretical Informatics, Sao Paulo, Brazil, April 6-10, 1992. Proceedings. Sao Paulo. Brésil. 1992.
• Paschos, Vangelis ; Pekergin, Ferhan ; Zissimopoulos, Vassilis . Solving vertex cover, independent set and related problems by a Boltzmann machine. European Joint Conference on Engineering Systems Design and Analysis (ESDA). Istanbul. Turquie. 1992.

1991

Articles

• Zissimopoulos, Vassilis ; Paschos, Vangelis ; Pekergin, Ferhan . On the approximation of NP-complete problems by using Boltzmann machine method: the cases of some covering and packing problems. IEEE Transactions on Computers. Volume 40. n° 12. 1991. pages 1413-1418. IEEE. DOI http://doi.ieeecomputersociety.org/10.1109/12.106226.

Conference Contributions

• Benkouar, A. ; Manoussakis, Yannis ; Paschos, Vangelis ; Saad, Rachid . On the complexity of some Hamiltonian and Eulerian problems in edge-colored complete graphs (Extended abstract). 2nd International Symposium on Algorithms (ISA'91). Berlin. Taïwan. 1991.
• Paschos, Vangelis . Some approximation results on set packing. Computer and information sciences 6‎, proceedings‎ of the 1991 International symposium on computer and information sciences. Side. Turquie. 1991.
• Paschos, Vangelis . A theorem on the approximation of set cover and vertex cover. 11th Conference on Foundations of Software Technology and Theoretical Computer Science (FCT&TCS'91). Berlin. Inde. 1991.
• Fernandez de la Vega, Wenceslas ; Paschos, Vangelis ; Stafylopatis, Andreas . On the mean execution time of recursive definitions on relational databases. 3rd Symposium on Mathematical Fundamentals of Database and Knowledge Base Systems, MFDBS'91. Berlin. Allemagne. 1991.
• Zissimopoulos, Vassilis ; Paschos, Vangelis ; Pekergin, Ferhan . 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. 1991.

1990

Conference Contributions

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