8 results on '"Khosravian Ghadikolaei, Mehdi"'
Search Results
2. Abundant Extensions
- Author
-
Casel, Katrin, Fernau, Henning, Khosravian Ghadikolaei, Mehdi, Monnot, Jérôme, Sikora, Florian, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,ComputingMilieux_MISCELLANEOUS - Abstract
International audience
- Published
- 2021
3. Extension and its price for the connected vertex cover problem.
- Author
-
Khosravian Ghadikolaei, Mehdi, Melissinos, Nikolaos, Monnot, Jérôme, and Pagourtzis, Aris
- Subjects
- *
CHARTS, diagrams, etc. , *INDEPENDENT sets , *BIPARTITE graphs , *APPROXIMATION algorithms , *HARDNESS - Abstract
• Definition and study of the extension variants of the connected vertex cover problem (Ext-CVC), and of the Non-Separating Independent Set problem (Ext-NSIS). • Solvability and hardness results for Ext-CVC , notably in bipartite graphs of maximum degree 3 and in weakly triangulated graphs, applying also to Ext-NSIS. • Formulation of the concept of Price of Extension (PoE) as the approximation ratio for the problem Max Ext-CVC (resp., Min Ext-NSIS). • Lower bounds for PoE of Max Ext-CVC in general and bipartite graphs; proof that it is equal to 1 in chordal graphs, carrying over to Min Ext-NSIS. We consider extension variants of Vertex Cover and Independent Set , following a line of research initiated in [10]. In particular, we study the Ext-CVC and the Ext-NSIS problems: given a graph G = (V , E) and a vertex set U ⊆ V , does there exist a minimal connected vertex cover (respectively, a maximal non-separating independent set) S , such that U ⊆ S (respectively, U ⊇ S). We present hardness results for both problems, for certain graph classes such as bipartite, chordal and weakly chordal. To this end we exploit the relation of Ext-CVC to Ext-VC , that is, to the extension variant of Vertex Cover. We also study the Price of Extension (PoE) , a measure that reflects the distance of a vertex set U to its maximum efficiently computable subset that is extensible to a minimal connected vertex cover, and provide negative and positive results for PoE in general and special graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
4. Extension des problèmes NPO
- Author
-
Khosravian Ghadikolaei, Mehdi, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres, and Jérôme Monnot
- Subjects
Computational complexity ,Parameterized complexity ,Extension problems ,Graphe ,Graph problems ,Complexité ,Problèmes d’extension ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,Approximation ,Complexité paramétrée - Abstract
The problem of determining the quality of a partial solution occurs in almost every algorithmic approach that gradually computes a global solution. Pruning search trees, proving approximation guarantees, or the efficiency of enumeration strategies usually require a suitable way to decide if a given partial solution is a reasonable candidate to pursue for extension to a global one, of assured quality. In this thesis, we study a special type of optimization problems, called extension problems for a large number of optimization problems on graphs. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimization problem can be solved in polynomial time. We present many positive/negative hardness and approximation results for different input scenarios. Moreover, the parameterized complexity of extension problems with respect to size of partial solutions, as well as the optimality of some exact algorithms under the Exponential-Time Hypothesis (ETH) are studied.; Le problème de la détermination de la qualité d’une solution partielle se pose dans la majeure partie des approches algorithmiques cherchant à calculer progressivement une solution globale. L’élagage des arbres de recherche, la preuve de garanties d’approximation et l’efficacité des stratégies d’énumération sont des approches algorithmiques qui exigent souvent un moyen approprié de décider si une solution partielle donnée est un bon candidat pour l’étendre à une solution globale de bonne qualité. Dans cette thèse, nous étudions un type particulier de problèmes d’optimisation, appelés problèmes d’extension pour un grand nombre de problèmes basés sur des graphes. Contredisant peut-être l’intuition, ces problèmes ont tendance à être NP-difficile, même quand le problème d’optimisation sous-jacent peut être résolu en temps polynomial. Nous présentons de nombreux résultats positifs et négatifs de NP-difficulté et d’approximation pour différents scénarios d’entrée. De plus, nous étudions la complexité paramétrée des problèmes d’extension par rapport à la taille des pré-solutions, ainsi que l’optimalité de certains algorithmes exacts sous l’hypothèse du temps exponentielle.
- Published
- 2019
5. Extension of NP Optimization Problems
- Author
-
KHOSRAVIAN GHADIKOLAEI, Mehdi, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres, Jérôme Monnot, Bruno Escoffier [Président], Mamadou Moustapha Kanté [Rapporteur], David F. Manlove [Rapporteur], Marthe Bonamy, Michel Habib, Florian Sikora, and Martin Milanič
- Subjects
Computational complexity ,Parameterized complexity ,Extension problems ,Graphe ,Graph problems ,Complexité ,Problèmes d’extension ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,Approximation ,Complexité paramétrée - Abstract
The problem of determining the quality of a partial solution occurs in almost every algorithmic approach that gradually computes a global solution. Pruning search trees, proving approximation guarantees, or the efficiency of enumeration strategies usually require a suitable way to decide if a given partial solution is a reasonable candidate to pursue for extension to a global one, of assured quality. In this thesis, we study a special type of optimization problems, called extension problems for a large number of optimization problems on graphs. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimization problem can be solved in polynomial time. We present many positive/negative hardness and approximation results for different input scenarios. Moreover, the parameterized complexity of extension problems with respect to size of partial solutions, as well as the optimality of some exact algorithms under the Exponential-Time Hypothesis (ETH) are studied.; Le problème de la détermination de la qualité d’une solution partielle se pose dans la majeure partie des approches algorithmiques cherchant à calculer progressivement une solution globale. L’élagage des arbres de recherche, la preuve de garanties d’approximation et l’efficacité des stratégies d’énumération sont des approches algorithmiques qui exigent souvent un moyen approprié de décider si une solution partielle donnée est un bon candidat pour l’étendre à une solution globale de bonne qualité. Dans cette thèse, nous étudions un type particulier de problèmes d’optimisation, appelés problèmes d’extension pour un grand nombre de problèmes basés sur des graphes. Contredisant peut-être l’intuition, ces problèmes ont tendance à être NP-difficile, même quand le problème d’optimisation sous-jacent peut être résolu en temps polynomial. Nous présentons de nombreux résultats positifs et négatifs de NP-difficulté et d’approximation pour différents scénarios d’entrée. De plus, nous étudions la complexité paramétrée des problèmes d’extension par rapport à la taille des pré-solutions, ainsi que l’optimalité de certains algorithmes exacts sous l’hypothèse du temps exponentielle.
- Published
- 2019
6. Complexity and approximability of extended Spanning Star Forest problems in general and complete graphs.
- Author
-
Khoshkhah, Kaveh, Khosravian Ghadikolaei, Mehdi, Monnot, Jérôme, and Theis, Dirk Oliver
- Subjects
- *
COMPLETE graphs , *TRAVELING salesman problem - Abstract
A solution extension problem consists in an instance and a partial feasible solution which is given in advance and the goal is to extend this partial solution to a feasible one. Many well-known problems like Coloring Extension Problems, Traveling Salesman Problem and Routing problems, have been studied in this framework. In this paper, we focus on the edge-weighted spanning star forest problem for both minimization and maximization versions. The goal here is to find a vertex partition of an edge-weighted graph into disjoint non-trivial stars and the value of a solution is given by the sum of the edge-weights of the stars. We propose NP -hardness, parameterized complexity, positive and negative approximation results. • An extension variant of the weighted edge cover problem is studied. • The problem is NP -complete in complete graphs while polynomial solvable in bounded tree-width graphs. • For non-negative weights, the minimization version is in-approximable at all while the maximization version is in RAPX. • If weight function satisfies (extended) c -relaxed triangle inequalities, the minimization version is in RAPX. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
7. (In)approximability of maximum minimal FVS.
- Author
-
Dublois, Louis, Hanaka, Tesshu, Khosravian Ghadikolaei, Mehdi, Lampis, Michael, and Melissinos, Nikolaos
- Subjects
- *
POLYNOMIAL time algorithms , *APPROXIMATION algorithms , *POLYNOMIAL approximation , *DOMINATING set , *HARDNESS , *INTUITION - Abstract
We study the approximability of the NP-complete Maximum Minimal Feedback Vertex Set problem. Informally, this natural problem seems to lie in an intermediate space between two more well-studied problems of this type: Maximum Minimal Vertex Cover , for which the best achievable approximation ratio is n , and Upper Dominating Set , which does not admit any n 1 − ϵ approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for Maximum Minimal Feedback Vertex Set with a ratio of O (n 2 / 3) , as well as a matching hardness of approximation bound of n 2 / 3 − ϵ , improving the previously known hardness of n 1 / 2 − ϵ. Having settled the problem's approximability in polynomial time, we move to the context of super-polynomial time. We devise a generalization of our approximation algorithm which, for any desired approximation ratio r , produces an r -approximate solution in time n O (n / r 3 / 2). This time-approximation trade-off is essentially tight under the ETH. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
8. On the complexity of solution extension of optimization problems.
- Author
-
Casel, Katrin, Fernau, Henning, Khosravian Ghadikolaei, Mehdi, Monnot, Jérôme, and Sikora, Florian
- Subjects
- *
BIPARTITE graphs , *BIN packing problem , *DOMINATING set , *POLYNOMIAL time algorithms , *PLANAR graphs , *UNDIRECTED graphs , *NP-hard problems , *PARAMETERIZATION - Abstract
• Extending a partial solution of an optimization problem occurs as a subproblem in many areas. • We propose a general framework for dealing with these extension problems. • We present several problems from different areas which can be expressed in this framework. • We show NP-hardness results and parameterized complexity results for the presented problems. The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal vertex covers of a graph G = (V , E) , one usually arrives at the problem to decide for a vertex set U ⊆ V (pre-solution), if there exists a minimal vertex cover S (i.e., a vertex cover S ⊆ V such that no proper subset of S is a vertex cover) with U ⊆ S (minimal extension of U). We propose a general, partial-order based formulation of such extension problems which allows to model parameterization and approximation aspects of extension, and also highlights relationships between extension tasks for different specific problems. As examples, we study a number of specific problems which can be expressed and related in this framework. In particular, we discuss extension variants of the problems dominating set and feedback vertex/edge set. All these problems are shown to be NP -complete even when restricted to bipartite graphs of bounded degree, with the exception of our extension version of feedback edge set on undirected graphs which is shown to be solvable in polynomial time. For the extension variants of dominating and feedback vertex set, we also show NP -completeness for the restriction to planar graphs of bounded degree. As non-graph problem, we also study an extension version of the bin packing problem. We further consider the parameterized complexity of all these extension variants, where the parameter is a measure of the pre-solution as defined by our framework. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.