• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Structurally Parameterized Tight Bounds and Approximation for Generalizations of Independence and Domination

Limites exactes et approximation structurellement paramétré pour généralisations d'indépendance et de domination

Katsikarelis, Ioannis (2019), Structurally Parameterized Tight Bounds and Approximation for Generalizations of Independence and Domination, doctoral thesis prepared under the supervision of Paschos, Vangelis T.; Lampis, Michael, Paris Sciences et Lettres (ComUE)

View/Open
2019PSLED048.pdf (12.12Mb)
Type
Thèse
Date
2019-12-12
Metadata
Show full item record
Author(s)
Katsikarelis, Ioannis
Under the direction of
Paschos, Vangelis T.; Lampis, Michael
Abstract (FR)
Nous nous concentrons sur les problèmes (k, r)-CENTER et d-SCATTERED SET qui généralisent les concepts de domination et indépendance des sommets, sur les distances plus grandes.Dans la première partie, nous examinons le paramétrage standard, ainsi que les paramètres des graphes mesurant la structure de l’entrée. Nous proposons des résultats qui montrent qu’il n’existe pas d’algorithme avec un temps d’exécution inférieur à certaines limites, si l’hypothèse du temps exponentiel est vraie, nous produisons des algorithmes de complexité essentiellement optimale qui correspondent à ces limites et nous essayons en outre de proposer une alternative au calcul exact en temps considérablement réduit, grâce à l’approximation.Dans la deuxième partie, nous considérons l’approximabilité (super-)polynômiale du problème de d-SCATTERED SET c’est-à-dire que nous déterminons la relation exacte entre un réalisable rapport d’approximation ρ, le paramètre de distance d et le temps d’exécution de l’algorithme avec un rapport de ρ, en fonction de ce qui précède et de la taille de l’entrée n. Nous considérons ensuite les temps d’exécution strictement polynomiaux et les graphes de degré maximal borné, ainsi que les graphes bipartites.
Abstract (EN)
In this thesis we focus on the NP-hard problems (k, r)-CENTER and d-SCATTERED SET that generalize the well-studied concepts of domination and independence over larger distances. In the first part we maintain a parameterized viewpoint and examine the standard parameterization as well as the most widely-used graph parameters measuring the input’s structure. We offer hardness results that show there is no algorithm of running-time below certain bounds, subject to the (Strong) Exponential Time Hypothesis, produce essentially optimal algorithms of complexity that matches these lower bounds and further attempt to offer an alternative to exact computation in significantly reduced running-time by way of approximation algorithms. In the second part we consider the (super-)polynomial (in-)approximability of the d-SCATTERED SET problem, i.e. we determine the exact relationship between an achievable approximation ratio ρ, the distance parameter d, and the runningtime of any ρ-approximation algorithm expressed as a function of the above and the size of the input n. We then consider strictly polynomial running-times and improve our understanding on the approximability characteristics of the problem on graphs of bounded maximum degree as well as bipartite graphs.
Subjects / Keywords
Paramétrage; Approximation; Indépendance; Domination; ETH; Paramètre de distance; SETH; Parameterization; Approximation; Independence; Domination; ETH; Treewidth; SETH; Clique-width; Distance parameter; Vertex degree

Related items

Showing items related by title and author.

  • Thumbnail
    Structural parameters, tight bounds, and approximation for (k,r)-center 
    Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis (2019) Article accepté pour publication ou publié
  • Thumbnail
    Parameterized Complexity of Safe Set 
    Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
  • Thumbnail
    Parameterized Complexity of Safe Set 
    Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Article accepté pour publication ou publié
  • Thumbnail
    Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems 
    Bonnet, Édouard; Paschos, Vangelis; Sikora, Florian (2016) Article accepté pour publication ou publié
  • Thumbnail
    Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée 
    Bonnet, Édouard (2014-11) Thèse
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo