Paschos Vangelis Th.

Vangelis Th. Paschos

Information about the author Vangelis Th. Paschos will soon be added to the site.
Found 23 papers in total
Improved worst-case complexity for the MIN 3-SET COVERING problem
Improved worst-case complexity for the MIN 3-SET COVERING problem
2007
We consider MIN SET COVERING when the subsets are constrained to have maximum...
Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem
Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem
2004
The weakly NP-hard single-machine total tardiness scheduling problem has been...
On-line models and algorithms for max independent set
On-line models and algorithms for max independent set
2006
In on-line computation, the instance of the problem dealt is not entirely known from...
On-line maximum-order induced hereditary subgraph problems
On-line maximum-order induced hereditary subgraph problems
2005
We first study the competitive ratio for the on-line version of the problem of finding...
Polynomial approximation algorithms with performance guarantees: An introduction-by-example
Polynomial approximation algorithms with performance guarantees: An introduction-by-example
2005
We present a short overview on polynomial approximation of NP-hard problems. We...
A unified formulation and approach to the analysis of approximation algorithms: the structure of NP optimisation problems
A unified formulation and approach to the analysis of approximation algorithms: the structure of NP optimisation problems
2002
This paper is the continuation of the paper “Autour de nouvelles notions pour...
A unified formulation and approach to the analysis of approximation algorithms
A unified formulation and approach to the analysis of approximation algorithms
2002
The main objective of the polynomial approximation is the development of polynomial...
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
1999
We first motivate and define a notion of asymptotic differential approximation ratio....
A simulated annealing approach for the circular cutting problem
A simulated annealing approach for the circular cutting problem
2004
We propose a heuristic for the constrained and unconstrained circular cutting problem...
Local approximations for maximum partial subgraph problem
Local approximations for maximum partial subgraph problem
2004
We deal with MAX H 0 -FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum...
Differential approximation for optimal satisfiability and related problems
Differential approximation for optimal satisfiability and related problems
2003
We study the differential approximability of several optimization satisfiability...
Differential approximation results for the traveling salesman problem with distances 1 and 2
Differential approximation results for the traveling salesman problem with distances 1 and 2
2003
We prove that both minimum and maximum traveling salesman problems on complete graphs...
On-line independent set by coloring vertices
On-line independent set by coloring vertices
2001
In on-line computation, the instance of a problem is revealed step-by-step and one...
A note on a new greedy-solution representation and a new greedy parallelizable heuristic for the traveling salesman problem
A note on a new greedy-solution representation and a new greedy parallelizable heuristic for the traveling salesman problem
2002
A new approach is presented to the traveling salesman problem relying on a novel...
The probabilistic minimum vertex-covering problem
The probabilistic minimum vertex-covering problem
2002
An instance of the probabilistic vertex-covering problem is a pair ( G = (V, E), Pr)...
The probabilistic longest path problem
The probabilistic longest path problem
1999
We study the probabilistic longest path problem. We propose a modification strategy...
An improved general procedure for lexicographic bottleneck problems
An improved general procedure for lexicographic bottleneck problems
1999
In combinatorial optimization, the bottleneck (or minmax) problems are those problems...
Approximating minimum spanning tree of depth 2
Approximating minimum spanning tree of depth 2
1999
We prove that the problem of finding, in an undirected graph with non-negative costs...
A generalization of König–Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
A generalization of König–Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
1997
We first study a generalization of the König–Egervary graphs, the class of...
Probabilistic combinatorial optimization problems on graphs: A new domain in operational research
Probabilistic combinatorial optimization problems on graphs: A new domain in operational research
1995
We present a new research domain in Operational Research, probabilistic combinatorial...
The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
1997
We prove that the existence of a polynomial time ρ-approximation algorithm (where...
A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts
A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts
1997
The satellite shot sequencing problem consists in choosing the pictures to be...
A new efficient heuristic for the minimum set covering problem
A new efficient heuristic for the minimum set covering problem
1995
This paper solves approximately the minimum set covering problem by developing a new...
Papers per page: