Vangelis Th. Paschos

According to our database, Vangelis Th. Paschos authored at least 161 papers between 1991 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Average-case complexity of a branch-and-bound algorithm for Min Dominating Set.

Tom Denat, Ararat Harutyunyan, Nikolaos Melissinos, Vangelis Th. Paschos

Discret. Appl. Math., March, 2024

2023

Improved (In-)Approximability Bounds for d-Scattered Set.

Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos

J. Graph Algorithms Appl., 2023

2022

In memory of Jérôme Monnot.

Bruno Escoffier, Laurent Gourvès, Vangelis Th. Paschos

Theor. Comput. Sci., 2022

Upper Dominating Set: Tight algorithms for pathwidth and sub-exponential approximation.

Louis Dublois, Michael Lampis, Vangelis Th. Paschos

Theor. Comput. Sci., 2022

Structurally parameterized d-scattered set.

Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos

Discret. Appl. Math., 2022

2021

New Algorithms for Mixed Dominating Set.

Louis Dublois, Michael Lampis, Vangelis Th. Paschos

Discret. Math. Theor. Comput. Sci., 2021

The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet.

Nicolas Boria, Laurent Gourvès, Vangelis Th. Paschos, Jérôme Monnot

Proceedings of the 21st International Workshop on Algorithms in Bioinformatics, 2021

2019

Preface to Special Issue on Algorithms and Complexity.

Dimitris Fotakis, Aris Pagourtzis, Vangelis Th. Paschos

Theor. Comput. Sci., 2019

Structural parameters, tight bounds, and approximation for (k, r)-center.

Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos

Discret. Appl. Math., 2019

A polynomial time approximation schema for maximum k-vertex cover in bipartite graphs.

Vangelis Th. Paschos

CoRR, 2019

Average-case complexity of a branch-and-bound algorithm for min dominating set.

Tom Denat, Ararat Harutyunyan, Vangelis Th. Paschos

CoRR, 2019

2018

The many facets of upper domination.

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos

Theor. Comput. Sci., 2018

Combinatorial approximation of maximum <i>k</i>-vertex cover in bipartite graphs within ratio 0.7.

Vangelis Th. Paschos

RAIRO Oper. Res., 2018

Time-approximation trade-offs for inapproximable problems.

Édouard Bonnet, Michael Lampis, Vangelis Th. Paschos

J. Comput. Syst. Sci., 2018

Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs.

Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis

Discret. Optim., 2018

The probabilistic minimum dominating set problem.

Nicolas Boria, Cécile Murat, Vangelis Th. Paschos

Discret. Appl. Math., 2018

When polynomial approximation meets exact computation.

Vangelis Th. Paschos

Ann. Oper. Res., 2018

Sparsification and subexponential approximation.

Édouard Bonnet, Vangelis Th. Paschos

Acta Informatica, 2018

Multistage Matchings.

Evripidis Bampis, Bruno Escoffier, Michael Lampis, Vangelis Th. Paschos

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Differential Ratio Approximation.

Giorgio Ausiello, Vangelis Th. Paschos

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

Reductions That Preserve Approximability.

Giorgio Ausiello, Vangelis Th. Paschos

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

2017

Dual parameterization and parameterized approximability of subset graph problems.

Édouard Bonnet, Vangelis Th. Paschos

RAIRO Oper. Res., 2017

Exact and superpolynomial approximation algorithms for the densest k-subgraph problem.

Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos

Eur. J. Oper. Res., 2017

2016

Super-polynomial approximation branching algorithms.

Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire

RAIRO Oper. Res., 2016

Parameterized exact and approximation algorithms for maximum <i>k</i>-set cover and related satisfiability problems.

Édouard Bonnet, Vangelis Th. Paschos, Florian Sikora

RAIRO Theor. Informatics Appl., 2016

Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse.

Dimitris Fotakis, Michael Lampis, Vangelis Th. Paschos

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs.

Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis

Proceedings of the LATIN 2016: Theoretical Informatics, 2016

Upper Domination: Complexity and Approximation.

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos

Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

Algorithmic Aspects of Upper Domination: A Parameterised Perspective.

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos

Proceedings of the Algorithmic Aspects in Information and Management, 2016

2015

New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set.

Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos, Mingyu Xiao

Theory Comput. Syst., 2015

On the max min vertex cover problem.

Nicolas Boria, Federico Della Croce, Vangelis Th. Paschos

Discret. Appl. Math., 2015

Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio~0.7.

Vangelis Th. Paschos

CoRR, 2015

Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the $\mathcal{G}(n, p)$ random model.

Nicolas Bourgeois, R. Catellier, Tom Denat, Vangelis Th. Paschos

CoRR, 2015

Algorithmic Aspects of Upper Domination.

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos

CoRR, 2015

Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization.

Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire

Algorithmica, 2015

On Subexponential and FPT-Time Inapproximability.

Edouard Bonnet, Bruno Escoffier, Eun Jung Kim, Vangelis Th. Paschos

Algorithmica, 2015

2014

Special Issue: "Combinatorial Optimization: Theory of Algorithms and Complexity".

Vangelis Markakis, Ioannis Milis, Vangelis Th. Paschos

Theor. Comput. Sci., 2014

Approximating MAX SAT by moderately exponential and parameterized algorithms.

Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire

Theor. Comput. Sci., 2014

Parameterized (in)approximability of subset problems.

Edouard Bonnet, Vangelis Th. Paschos

Oper. Res. Lett., 2014

Efficient algorithms for the max k-vertex cover problem.

Federico Della Croce, Vangelis Th. Paschos

J. Comb. Optim., 2014

On the approximation of maximum $k$-vertex cover in bipartite graphs.

Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis

CoRR, 2014

2013

Preface.

Vangelis Th. Paschos

Theor. Comput. Sci., 2013

Reoptimization of maximum weight induced hereditary subgraph problems.

Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos

Theor. Comput. Sci., 2013

Exponential approximation schemata for some network design problems.

Nicolas Boria, Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos

J. Discrete Algorithms, 2013

Reoptimization under Vertex Insertion: Max P_K-Free Subgraph and Max Planar Subgraph.

Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos

Discret. Math. Algorithms Appl., 2013

Weighted completion time minimization on a single-machine with a fixed non-availability interval: Differential approximability.

Imed Kacem, Vangelis Th. Paschos

Discret. Optim., 2013

Fast algorithms for min independent dominating set.

Nicolas Bourgeois, Federico Della Croce, Bruno Escoffier, Vangelis Th. Paschos

Discret. Appl. Math., 2013

Playing with Parameters: Cross-parameterization in Graphs.

Nicolas Bourgeois, Konrad K. Dabrowski, Marc Demange, Vangelis Th. Paschos

CoRR, 2013

Multiparameterizations for max $k$-set cover and related satisfiability problems.

Edouard Bonnet, Vangelis Th. Paschos, Florian Sikora

CoRR, 2013

Exact and Approximation Algorithms for Densest <i>k</i>-Subgraph.

Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos

Proceedings of the WALCOM: Algorithms and Computation, 7th International Workshop, 2013

Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization.

Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Emeric Tourniaire

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

The Probabilistic Min Dominating Set Problem.

Nicolas Boria, Cécile Murat, Vangelis Th. Paschos

Proceedings of the Computer Science - Theory and Applications, 2013

2012

Algorithms for dominating clique problems.

Nicolas Bourgeois, Federico Della Croce, Bruno Escoffier, Vangelis Th. Paschos

Theor. Comput. Sci., 2012

On the probabilistic min spanning tree Problem.

Nicolas Boria, Cécile Murat, Vangelis Th. Paschos

J. Math. Model. Algorithms, 2012

The max quasi-independent set problem.

Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos, O. Pottié

J. Comb. Optim., 2012

Online maximum k-coverage.

Giorgio Ausiello, Nicolas Boria, Aristotelis Giannakos, Giorgio Lucarelli, Vangelis Th. Paschos

Discret. Appl. Math., 2012

Subexponential and FPT-time Inapproximability of Independent Set and Related Problems

Bruno Escoffier, Eun Jung Kim, Vangelis Th. Paschos

CoRR, 2012

Fast Algorithms for max independent set.

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij

Algorithmica, 2012

Reoptimization of the Maximum Weighted P k -Free Subgraph Problem under Vertex Insertion.

Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos

Proceedings of the WALCOM: Algorithms and Computation - 6th International Workshop, 2012

Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems.

Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set.

Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos, Mingyu Xiao

Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

2011

A survey on combinatorial optimization in dynamic environments.

Nicolas Boria, Vangelis Th. Paschos

RAIRO Oper. Res., 2011

Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms.

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos

Discret. Appl. Math., 2011

2010

Approximating the max-edge-coloring problem.

Nicolas Bourgeois, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos

Theor. Comput. Sci., 2010

Probabilistic models for the Steiner Tree problem.

Vangelis Th. Paschos, Orestis Telelis, Vassilis Zissimopoulos

Networks, 2010

Fast reoptimization for the minimum spanning tree problem.

Nicolas Boria, Vangelis Th. Paschos

J. Discrete Algorithms, 2010

On the max-weight edge coloring problem.

Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos

J. Comb. Optim., 2010

A survey on the structure of approximation classes.

Bruno Escoffier, Vangelis Th. Paschos

Comput. Sci. Rev., 2010

Probabilistic optimization in graph-problems.

Cécile Murat, Vangelis Th. Paschos

Algorithmic Oper. Res., 2010

Approximating the metric 2-Peripatetic Salesman Problem.

Federico Della Croce, Vangelis Th. Paschos, Roberto Wolfler Calvo

Algorithmic Oper. Res., 2010

Maximum Independent Set in Graphs of Average Degree at Most Three in <i>O</i>(1.08537^<i>n</i>){\mathcal O}(1.08537^n).

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij

Proceedings of the Theory and Applications of Models of Computation, 7th Annual Conference, 2010

A Bottom-Up Method and Fast Algorithms for max independent set.

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij

Proceedings of the Algorithm Theory, 2010

Fast Algorithms for min independent dominating set.

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos

Proceedings of the Structural Information and Communication Complexity, 2010

2009

Efficient approximation of min set cover by moderately exponential algorithms.

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos

Theor. Comput. Sci., 2009

Reoptimization of minimum and maximum traveling salesman's tours.

Giorgio Ausiello, Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos

J. Discrete Algorithms, 2009

Probabilistic graph-coloring in bipartite and split graphs.

Nicolas Bourgeois, Federico Della Croce, Bruno Escoffier, Cécile Murat, Vangelis Th. Paschos

J. Comb. Optim., 2009

Approximation of min coloring by moderately exponential algorithms.

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos

Inf. Process. Lett., 2009

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation.

Dominique de Werra, Marc Demange, Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos

Discret. Appl. Math., 2009

Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2.

Alexey Baburin, Federico Della Croce, Edward Gimadi, Y. V. Glazkov, Vangelis Th. Paschos

Discret. Appl. Math., 2009

Max Edge Coloring of Trees

Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos

CoRR, 2009

Fast Algorithms for Max Independent Set in Graphs of Small Average Degree

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij

CoRR, 2009

Simple and Fast Reoptimizations for the Steiner Tree Problem.

Bruno Escoffier, Martin Milanic, Vangelis Th. Paschos

Algorithmic Oper. Res., 2009

Greedy Algorithms For On-Line Set-Covering.

Giorgio Ausiello, Nicolas Bourgeois, Telis Giannakos, Vangelis Th. Paschos

Algorithmic Oper. Res., 2009

Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms.

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos

Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Exact Algorithms for Dominating Clique Problems.

Nicolas Bourgeois, Federico Della Croce, Bruno Escoffier, Vangelis Th. Paschos

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008

Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems.

Federico Della Croce, Vangelis Th. Paschos

Oper. Res., 2008

On the Maximum Edge Coloring Problem.

Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos

Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

An O*(1.0977ⁿ) Exact Algorithm for max independent set in Sparse Graphs.

Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos

Proceedings of the Parameterized and Exact Computation, Third International Workshop, 2008

Vertex-Uncertainty in Graph-Problems.

Cécile Murat, Vangelis Th. Paschos

Proceedings of the Combinatorial Optimization and Applications, 2008

Combinatorial Optimization and Theoretical Computer Science - Interfaces and Perspectives: 30th Anniversary of the LAMSADE.

Vangelis Th. Paschos

Wiley, ISBN: 978-1-8482-1021-9, 2008

2007

Differential Ratio Approximation.

Giorgio Ausiello, Vangelis Th. Paschos

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

Reductions That Preserve Approximability.

Giorgio Ausiello, Vangelis Th. Paschos

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

Time slot scheduling of compatible jobs.

Marc Demange, Dominique de Werra, Jérôme Monnot, Vangelis Th. Paschos

J. Sched., 2007

An exact algorithm for MAX-CUT in sparse graphs.

Federico Della Croce, Marcin Jakub Kaminski, Vangelis Th. Paschos

Oper. Res. Lett., 2007

Improved worst-case complexity for the MIN 3-SET COVERING problem.

Federico Della Croce, Bruno Escoffier, Vangelis Th. Paschos

Oper. Res. Lett., 2007

Differential approximation of min sat.

Bruno Escoffier, Vangelis Th. Paschos

Eur. J. Oper. Res., 2007

On the Performance of Congestion Games for Optimum Satisfiability Problems.

Aristotelis Giannakos, Laurent Gourvès, Jérôme Monnot, Vangelis Th. Paschos

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Steiner Forests on Stochastic Metric Graphs.

Vangelis Th. Paschos, Orestis Telelis, Vassilis Zissimopoulos

Proceedings of the Combinatorial Optimization and Applications, 2007

2006

Completeness in approximation classes beyond APX.

Bruno Escoffier, Vangelis Th. Paschos

Theor. Comput. Sci., 2006

On-line models and algorithms for max independent set.

Bruno Escoffier, Vangelis Th. Paschos

RAIRO Oper. Res., 2006

Weighted Coloring: further complexity and approximability results.

Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos

Inf. Process. Lett., 2006

Jon Lee, A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics.

Vangelis Th. Paschos

Eur. J. Oper. Res., 2006

Reductions, completeness and the hardness of approximability.

Giorgio Ausiello, Vangelis Th. Paschos

Eur. J. Oper. Res., 2006

Approximation algorithms for 2-Peripathetic Salesman Problem with edge weights 1 and 2.

Yury Glazkov, Alexey Baburin, Edward Gimadi, Federico Della Croce, Vangelis Th. Paschos

Electron. Notes Discret. Math., 2006

On the probabilistic minimum coloring and minimum <i>k</i>-coloring.

Cécile Murat, Vangelis Th. Paschos

Discret. Appl. Math., 2006

Greedy algorithms for on-line set-covering and related problems.

Giorgio Ausiello, Aristotelis Giannakos, Vangelis Th. Paschos

Proceedings of the Theory of Computing 2006, 2006

2005

On-line vertex-covering.

Marc Demange, Vangelis Th. Paschos

Theor. Comput. Sci., 2005

On the differential approximation of MIN SET COVER.

Cristina Bazgan, Jérôme Monnot, Vangelis Th. Paschos, Fabrice Serrière

Theor. Comput. Sci., 2005

Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness.

Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos

Theor. Comput. Sci., 2005

Improved Approximations for Weighted and Unweighted Graph Problems.

Marc Demange, Vangelis Th. Paschos

Theory Comput. Syst., 2005

On-line maximum-order induced hereditary subgraph problems.

Marc Demange, Xavier Paradon, Vangelis Th. Paschos

Int. Trans. Oper. Res., 2005

Completeness in differential approximation classes.

Giorgio Ausiello, Cristina Bazgan, Marc Demange, Vangelis Th. Paschos

Int. J. Found. Comput. Sci., 2005

Proving completeness by logic.

Bruno Escoffier, Vangelis Th. Paschos

Int. J. Comput. Math., 2005

Polynomial approximation algorithms with performance guarantees: An introduction-by-example.

Marc Demange, Vangelis Th. Paschos

Eur. J. Oper. Res., 2005

A hypocoloring model for batch scheduling.

Dominique de Werra, Marc Demange, Jérôme Monnot, Vangelis Th. Paschos

Discret. Appl. Math., 2005

Greedy Differential Approximations for Min Set Cover.

Cristina Bazgan, Jérôme Monnot, Vangelis Th. Paschos, Fabrice Serrière

Proceedings of the SOFSEM 2005: Theory and Practice of Computer Science, 2005

Computing Optimal Solutions for the min 3-set covering Problem.

Federico Della Croce, Vangelis Th. Paschos

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Differential Approximation of min sat, max sat and Related Problems.

Bruno Escoffier, Vangelis Th. Paschos

Proceedings of the Computational Science and Its Applications, 2005

Probabilistic Coloring of Bipartite and Split Graphs.

Federico Della Croce, Bruno Escoffier, Cécile Murat, Vangelis Th. Paschos

Proceedings of the Computational Science and Its Applications, 2005

2004

Lower Bounds on the Approximation Ratios of Leading Heuristics for the Single-Machine Total Tardiness Problem.

Federico Della Croce, Andrea Grosso, Vangelis Th. Paschos

J. Sched., 2004

Local approximations for maximum partial subgraph problem.

Jérôme Monnot, Vangelis Th. Paschos, Sophie Toulouse

Oper. Res. Lett., 2004

Algorithms for the On-Line Quota Traveling Salesman Problem.

Giorgio Ausiello, Marc Demange, Luigi Laura, Vangelis Th. Paschos

Inf. Process. Lett., 2004

Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximation.

Tínaz Ekim, Vangelis Th. Paschos

Int. J. Comput. Math., 2004

A simulated annealing approach for the circular cutting problem.

Mhand Hifi, Vangelis Th. Paschos, Vassilis Zissimopoulos

Eur. J. Oper. Res., 2004

The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small.

Dominique de Werra, Marc Demange, Jérôme Monnot, Vangelis Th. Paschos

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation.

Jérôme Monnot, Vangelis Th. Paschos, Dominique de Werra, Marc Demange, Bruno Escoffier

Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Poly-APX- and PTAS-Completeness in Standard and Differential Approximation.

Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos

Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

2003

Optima locaux garantis pour l'approximation différentielle.

Jérôme Monnot, Vangelis Th. Paschos, Sophie Toulouse

Tech. Sci. Informatiques, 2003

Approximation algorithms for the traveling salesman problem.

Jérôme Monnot, Vangelis Th. Paschos, Sophie Toulouse

Math. Methods Oper. Res., 2003

Differential approximation results for the traveling salesman problem with distances 1 and 2.

Jérôme Monnot, Vangelis Th. Paschos, Sophie Toulouse

Eur. J. Oper. Res., 2003

Differential approximation for optimal satisfiability and related problems.

Cristina Bazgan, Vangelis Th. Paschos

Eur. J. Oper. Res., 2003

Polynomial Approximation and Graph-Coloring.

Vangelis Th. Paschos

Computing, 2003

Differential approximation results for the Steiner tree problem.

Marc Demange, Jérôme Monnot, Vangelis Th. Paschos

Appl. Math. Lett., 2003

The Probabilistic Minimum Coloring Problem.

Cécile Murat, Vangelis Th. Paschos

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

2002

A priori optimization for the probabilistic maximum independent set problem.

Cécile Murat, Vangelis Th. Paschos

Theor. Comput. Sci., 2002

Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances.

Marc Demange, Vangelis Th. Paschos

RAIRO Oper. Res., 2002

Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation.

Marc Demange, Vangelis Th. Paschos

RAIRO Oper. Res., 2002

Weighted Node Coloring: When Stable Sets Are Expensive.

Marc Demange, Dominique de Werra, Jérôme Monnot, Vangelis Th. Paschos

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

Algorithms and Models for the On-Line Vertex-Covering.

Marc Demange, Vangelis Th. Paschos

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

2001

On-line independent set by coloring vertices.

Vangelis Th. Paschos

Oper. Res., 2001

2000

Master-Slave Strategy and Polynomial Approximation.

Laurent Alfandari, Vangelis Th. Paschos

Comput. Optim. Appl., 2000

On-Line Maximum-Order Induces Hereditary Subgraph Problems.

Marc Demange, Xavier Paradon, Vangelis Th. Paschos

Proceedings of the SOFSEM 2000: Theory and Practice of Informatics, 27th Conference on Current Trends in Theory and Practice of Informatics, Milovy, Czech Republic, November 25, 2000

1999

Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems.

Marc Demange, Vangelis Th. Paschos

RAIRO Oper. Res., 1999

An improved general procedure for lexicographic bottleneck problems.

Federico Della Croce, Vangelis Th. Paschos, Alexis Tsoukiàs

Oper. Res. Lett., 1999

The probabilistic longest path problem.

Cécile Murat, Vangelis Th. Paschos

Networks, 1999

1998

Differential Approximation Algorithms for Some Combinatorial Optimization Problems.

Marc Demange, Pascal Grisoni, Vangelis Th. Paschos

Theor. Comput. Sci., 1998

Average-Case Complexity for the Execution of Recursive Definitions on Relational Databases.

Wenceslas Fernandez de la Vega, Vangelis Th. Paschos, Andreas Stafylopatis

Acta Informatica, 1998

1997

A Survey of Approximately Optimal Solutions to Some Covering and Packing Problems.

Vangelis Th. Paschos

ACM Comput. Surv., 1997

The Approximability Behaviour of Some Combinatorial Problems with Respect to the Approximability of a Class of Maximum Independent Set Problems.

Marc Demange, Vangelis Th. Paschos

Comput. Optim. Appl., 1997

A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts.

Virginie Gabrel, Alain Moulet, Cécile Murat, Vangelis Th. Paschos

Ann. Oper. Res., 1997

1996

On an Approximation Measure Founded on the Links Between Optimization and Polynomial Approximation Theory.

Marc Demange, Vangelis Th. Paschos

Theor. Comput. Sci., 1996

1995

Average Case Analysis of Greedy Algorithms for Optimisation Problems on Set Systems.

Joël Blot, Wenceslas Fernandez de la Vega, Vangelis Th. Paschos, Rachid Saad

Theor. Comput. Sci., 1995

Constructive - Non-constructive Approximation and Maximum Independent Set Problem.

Marc Demange, Vangelis Th. Paschos

Proceedings of the Combinatorics and Computer Science, 1995

1994

Approximation Results for the Minimum Graph Coloring Problem.

Marc Demange, Pascal Grisoni, Vangelis Th. Paschos

Inf. Process. Lett., 1994

1992

A (Delta/2)-Approximation Algorithm for the Maximum Independent Set Problem.

Vangelis Th. Paschos

Inf. Process. Lett., 1992

Evaluation of the Execution Cost of Recursive Definitions.

Vangelis Th. Paschos, Andreas Stafylopatis

Comput. J., 1992

Average Case Analysis of a Greedy Algorithm for the Minimum Hitting Set Problem.

Wenceslas Fernandez de la Vega, Vangelis Th. Paschos, Rachid Saad

Proceedings of the LATIN '92, 1992

1991

On the Approximation of NP-Complete Problems by Using the Boltzmann Machine Method: The Cases of Some Covering and Packing Problems.

Vassilis Zissimopoulos, Vangelis Th. Paschos, Ferhan Pekergin

IEEE Trans. Computers, 1991

On the Mean Execution Time of Recursive Definitions on Relational Databases.

Wenceslas Fernandez de la Vega, Vangelis Th. Paschos, A. N. Staylopatis

Proceedings of the MFDBS 91, 1991

On the Complexity of Some Hamiltonian and Eulerian Problems in Edge-Colored Complete Graphs.

A. Benkouar, Yannis Manoussakis, Vangelis Th. Paschos, Rachid Saad

Proceedings of the ISA '91 Algorithms, 1991

A Theorem on the Approximation of Set Cover and Vertex Cover.

Vangelis Th. Paschos

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991