Parameterized complexity of cardinality constrained optimization problems

被引：52
|
作者：
Cai, Leizhen [1 ]
机构：
[1] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Shatin, Hong Kong, Peoples R China
来源：
COMPUTER JOURNAL | 2008年 / 51卷 / 01期
关键词：
cardinality constrained optimization problem; exact algorithm; fixed-cardinality optimization problem; graph problem; parameterized complexity; FPT algorithm; W[1]-hardness;
D O I：
10.1093/comjnl/bxm086
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
We study the parameterized complexity of cardinality constrained optimization problems, i.e. optimization problems that require their solutions to contain specified numbers of elements to optimize solution values. For this purpose, we consider around 20 such optimization problems, as well as their parametric duals, that deal with various fundamental relations among vertices and edges in graphs. We have almost completely settled their parameterized complexity by giving either FPT algorithms or W[1]-hardness proofs. Furthermore, we obtain faster exact algorithms for several cardinality constrained optimization problems by transforming them into problems of finding maximum (minimum) weight triangles in weighted graphs.
引用
收藏
页码：102 / 121
页数：20
相关论文
共 50 条
  • [1] Parameterized complexity of cardinality constrained optimization problems
    Cai, Leizhen
    Computer Journal, 2008, 51 (01): : 102 - 121
  • [2] Cardinality constrained combinatorial optimization: Complexity and polyhedra
    Stephan, Rudiger
    DISCRETE OPTIMIZATION, 2010, 7 (03) : 99 - 113
  • [3] Cardinality constrained minimum cut problems: complexity and algorithms
    Bruglieri, M
    Maffioli, F
    Ehrgott, M
    DISCRETE APPLIED MATHEMATICS, 2004, 137 (03) : 311 - 341
  • [4] MULTIFUNCTIONS ASSOCIATED WITH PARAMETERIZED CLASSES OF CONSTRAINED OPTIMIZATION PROBLEMS
    SPINGARN, JE
    LECTURE NOTES IN MATHEMATICS, 1984, 1091 : 206 - 215
  • [5] OPTIMALITY CONDITIONS AND CONSTRAINT QUALIFICATIONS FOR CARDINALITY CONSTRAINED OPTIMIZATION PROBLEMS
    Xiao, Z. H. U. O. Y. U.
    Ye, Jane j.
    NUMERICAL ALGEBRA CONTROL AND OPTIMIZATION, 2024, 14 (03): : 614 - 635
  • [6] An Augmented Lagrangian Method for Cardinality-Constrained Optimization Problems
    Christian Kanzow
    Andreas B. Raharja
    Alexandra Schwartz
    Journal of Optimization Theory and Applications, 2021, 189 : 793 - 813
  • [7] An Augmented Lagrangian Method for Cardinality-Constrained Optimization Problems
    Kanzow, Christian
    Raharja, Andreas B.
    Schwartz, Alexandra
    JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2021, 189 (03) : 793 - 813
  • [8] Crossover for Cardinality Constrained Optimization
    Friedrich, Tobias
    Koetzing, Timo
    Radhakrishnan, Aishwarya
    Schiller, Leon
    Schirneck, Martin
    Tennigkeit, Georg
    Wietheger, Simon
    PROCEEDINGS OF THE 2022 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'22), 2022, : 1399 - 1407
  • [9] Sequential optimality conditions for cardinality-constrained optimization problems with applications
    Kanzow, Christian
    Raharja, Andreas B.
    Schwartz, Alexandra
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2021, 80 (01) : 185 - 211
  • [10] A short note on the robust combinatorial optimization problems with cardinality constrained uncertainty
    Lee, Taehan
    Kwon, Changhyun
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2014, 12 (04): : 373 - 378
12345