Vangelis Th. Paschos

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

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

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

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

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

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

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

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

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

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

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

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

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

Ali Ridha Mahjoub, Vangelis Markakis, Ioannis Milis, Vangelis Th. Paschos (Eds.): Combinatorial Optimization - Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers. Lecture Notes in Computer Science 7422, Springer 2012, isbn 978-3-642-32146-7

Bruno Escoffier, Eun Jung Kim, Vangelis Th. Paschos: Subexponential and FPT-time Inapproximability of Independent Set and Related Problems. CoRR abs/1211.6656 (2012)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos: Max Edge Coloring of Trees. CoRR abs/0901.4002 (2009)

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos: Fast algorithms for min independent dominating set. CoRR abs/0905.1993 (2009)

Vangelis Th. Paschos: Combinatorial Optimization and Theoretical Computer Science - Interfaces and Perspectives: 30th Anniversary of the LAMSADE. Wiley 2008, isbn 978-1-8482-1021-9, pp. 1-515

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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