检索结果-内蒙古大学图书馆

On parameterized exponential time complexity

THEORETICAL COMPUTER SCIENCE 2009年第27-29期410卷 2641-2648页

作者： Chen, Jianer Kanj, Iyad A. Xia, Ge Lafayette Coll Dept Comp Sci Easton PA 18042 USA Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Depaul Univ Sch Comp Chicago IL 60604 USA

In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2(o(f(k)))p(n) time if and only if it is solvable in time O(2(delta f(k))q(n)) for any constant delta>0, where p and q are polynomials. We then illustrate how this equivalence can be used to show that special instances of parameterized NP-hard problems are as difficult as the general instances. For example, we show that the PLANAR DOMINATING SET problem on degree-3 graphs can be solved in 2(0(root k))p(n) parameterized time if and only if the general PLANAR DOMINATING SET problem can. Apart from their complexity theoretic implications, our results have some interesting algorithmic implications as well. (C) 2009 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Subexponential time complexity parameterized algorithms Exact algorithms

来源：评论

学校读者我要写书评

暂无评论

complexity and Approximability of parameterized MAX-CSPs

引用

ALGORITHMICA 2017年第1期79卷 230-250页

作者： Dell, Holger Kim, Eun Jung Lampis, Michael Mitsou, Valia Moemke, Tobias Saarland Univ Saarbrucken Germany Cluster Excellence Saarbrucken Germany Univ Paris 09 Paris France Hungarian Acad Sci SZTAKI Budapest Hungary

We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity;the goal is to compute the maximum fraction of constraints that can be satisfied simultaneously. In standard CSPs, we want to decide whether this fraction equals one. The parameters we investigate are structural measures, such as the treewidth or the clique-width of the variable-constraint incidence graph of the CSP instance. We consider Max-CSPs with the constraint types , , , and , and with various parameters k, and we attempt to fully classify them into the following three cases:The exact optimum can be computed in time. It is -hard to compute the exact optimum, but there is a randomized approximation scheme (), which computes a -approximation in time . There is no unless .

关键词： Constraint satisfaction problems parameterized complexity Approximation Clique width Neighborhood diversity

来源：评论

学校读者我要写书评

暂无评论

The influence of dimensions on the complexity of computing decision trees

引用

ARTIFICIAL INTELLIGENCE 2025年 343卷

作者： Kobourov, Stephen Loffler, Maarten Montecchiani, Fabrizio Pilipczuk, Marcin Rutter, Ignaz Seidel, Raimund Sorge, Manuel Wulms, Jules Tech Univ Munich Dept Comp Sci Munich Germany Univ Utrecht Dept Informat & Comp Sci Utrecht Netherlands Univ Perugia Dept Engn Perugia Italy Univ Warsaw Fac Math Informat & Mech Warsaw Poland Univ Passau Fac Comp Sci & Math Passau Germany Saarland Univ Dept Comp Sci Saarbrucken Germany TU Wien Inst Logic & Computat Vienna Austria

A decision tree recursively splits a feature space & Ropf;(d) and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work considers heuristic algorithms that compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum- size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space & Ropf;(d), which contains n training examples. We show that it can be solved in O(n(2d+1)) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f(d) & sdot;n(O(d / log d)) running time. The problem is solvable in (dR)(O(dR))& sdot;n(1+o(1) )time if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.

关键词： Decision trees parameterized complexity Machine learning

来源：评论

学校读者我要写书评

暂无评论

parameterized inapproximability of Morse matching

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2025年 126卷

作者： Bauer, Ulrich Rathod, Abhishek Tech Univ Munich Munich Germany Ben Gurion Univ Negev Beer Sheva Israel

We study the problem of minimizing the number of critical simplices from the point of view of inapproximability and parameterized complexity. We first show inapproximability of MIN-MORSE MATCHING within a factor of 2 log ( 1-r) n . Our second result shows that MIN- MORSE MATCHING is W [ P ]-hard with respect to the standard parameter. Next, we show that MIN-MORSE MATCHING with standard parameterization has no FPT approximation algorithm for any approximation factor rho . The above hardness results are applicable to complexes of dimension >= 2. On the positive side, we provide a factor O( n log n ) approximation algorithm for MIN-MORSE MATCHING on 2-complexes, noting that no such algorithm is known for higher dimensional complexes. Finally, we devise discrete gradients with very few critical simplices for typical instances drawn from a fairly wide range of parameter values of the Costa-Farber model of random complexes. (c) 2024 Published by Elsevier B.V.

关键词： Discrete Morse theory Approximation algorithms parameterized complexity Stochastic topology

来源：评论

学校读者我要写书评

暂无评论

Tight complexity bounds for FPT subgraph problems parameterized by the clique-width

引用

THEORETICAL COMPUTER SCIENCE 2013年 485卷 69-84页

作者： Broersma, Hajo Golovach, Petr A. Patel, Viresh Univ Twente Fac EEMCS NL-7500 AE Enschede Netherlands Univ Bergen Dept Informat N-5020 Bergen Norway Univ Birmingham Sch Math Birmingham B15 2TT W Midlands England

We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters. Let G be an arbitrary input graph on n vertices with clique-width at most w. We prove the following results. The DENSE (SPARSE) k-SUBGRAPH problem, which asks whether there exists an induced subgraph of G with k vertices and at least q edges (at most q edges, respectively), can be solved in time k(O(w)) . n, but it cannot be solved in time 2(0(w log k)) . n(0(1)) unless the Exponential Time Hypothesis (ETH) fails. The d-REGULAR INDUCED SUBGRAPH problem, which asks whether there exists a d-regular induced subgraph of G, and the MINIMUM SUBGRAPH OF MINIMUM DEGREE AT LEAST d problem, which asks whether there exists a subgraph of G with k vertices and minimum degree at least d, can be solved in time d(0(w)) . n, but they cannot be solved in time 2(0(w log d)) . n(0(1)) unless ETH fails. (C) 2013 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Clique-width Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

parameterized and subexponential-time complexity of satisfiability problems and applications

引用

THEORETICAL COMPUTER SCIENCE 2015年第Part3期607卷 282-295页

作者： Kanj, Iyad Szeider, Stefan Depaul Univ Sch Comp Chicago IL 60604 USA Vienna Univ Technol A-1040 Vienna Austria

We study the parameterized and the subexponential-time complexity of the weighted and the unweighted satisfiability problems on bounded-depth normalized Boolean circuits. We establish relations between the subexponential-time complexity of the weighted and the unweighted satisfiability problems, and use them to derive relations among the subexponential-time complexity of several NP-hard problem. We then study the role of certain natural structural parameters of the circuit in characterizing the parameterized and the subexponential-time complexity of the circuit satisfiability problems under consideration. We obtain threshold functions on some circuit structural parameters, including the depth, the number of gates, the fan-in, and the maximum number of (variable) occurrences, that lead to tight characterizations of the parameterized and the subexponential-time complexity of the circuit satisfiability problems under consideration. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Circuit satisfiability parameterized complexity Subexponential-time complexity

来源：评论

学校读者我要写书评

暂无评论

complexity of scheduling few types of jobs on related and unrelated machines

引用

JOURNAL OF SCHEDULING 2025年第1期28卷 139-156页

作者： Koutecky, Martin Zink, Johannes Charles Univ Prague Prague Czech Republic Univ Wurzburg Wurzburg Germany

The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector are among the oldest and most fundamental tasks in combinatorial optimization. Since all of these problems are in general NP-hard, much attention has been given to the regime where there is only a small number k of job types, but possibly the number of jobs n is large;this is the few job types, high-multiplicity regime. Despite many positive results, the hardness boundary of this regime was not understood until now. We show that makespan minimization on uniformly related machines (Q|HM|Cmax\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q|HM|C_{\max }$$\end{document}) is NP-hard already with 6 job types, and that the related Cutting Stock problem is NP-hard already with 8 item types. For the more general unrelated machines model (R|HM|Cmax\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R|HM|C_{\max }$$\end{document}), we show that if the largest job size pmax\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_{\max }$$\end{document} or the number of jobs n is polynomially bounded in the instance size |I|, there are algorithms with complexity |I|poly(k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|I|<^>{{{\,\ma

关键词： High-multiplicity jobs Cutting stock Hardness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Energy Distribution Optimization in Heterogeneous Networks with Min-Max and Local Constraints as Support of Ambient Intelligence

引用

SENSORS 2025年第9期25卷 2721-2721页

作者： Aloisio, Alessandro Bloisi, Domenico D. Romano, Marco Vinci, Cosimo Univ Int Studies Rome UNINT Dept Int Humanities & Social Sci I-00147 Rome Italy Univ Salento Dept Math & Phys Ennio Giorgi I-73100 Lecce Italy

In recent years, ambient intelligence (AmI) has gained significant attention from both academia and industry. AmI seeks to create environments that automatically adapt to individuals' needs, improving comfort and efficiency. These systems typically rely on Internet of Things (IoT) frameworks, where sensors and actuators enable seamless interaction between people and their surroundings. To ensure the effective operation of AmI systems, robust wireless networks are essential, capable of integrating a wide range of devices across different environments. However, designing such networks presents challenges due to varying communication protocols, power limitations, and the computational capacities of connected devices. This paper introduces a novel approach that leverages multi-interface networks to design a heterogeneous wireless network supporting AmI systems within the IoT ecosystem. The approach centers on selecting the most appropriate communication protocols, such as Wi-Fi, Bluetooth, or 5G, to connect devices. Since many devices are battery-powered, choosing the right communication interface is critical for optimizing energy efficiency. Our primary objective is to improve network performance while extending its operational lifespan by identifying an optimal set of interfaces that balance power consumption and efficiency. We present a new model within the well-established field of multi-interface networks, designed to reduce battery consumption while maximizing network performance. Additionally, we examine the computational complexity of this model and propose two solution algorithms grounded in fixed-parameter tractability theory for specific network classes.

关键词： ambient intelligence multi-interfaces networks coverage parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator Problem

引用

ALGORITHMICA 2025年第4期87卷 537-571页

作者： Baguley, Samuel Friedrich, Tobias Neumann, Aneta Neumann, Frank Pappik, Marcus Zeif, Ziena Potsdam Univ Hasso Plattner Inst Algorithm Engn Prof Dr Helmert Str 2-3 D-14482 Potsdam Brandenburg Germany Univ Adelaide Sch Comp & Math Sci Optimisat & Logist Adelaide SA 5005 Australia

parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary multi-objective algorithms for the W-separator problem, which is a natural generalization of the vertex cover problem. The goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most W vertices. We provide different multi-objective formulations involving two or three objectives that provably lead to fixed-parameter evolutionary algorithms with respect to the value of an optimal solution OPT and W. Of particular interest are kernelizations and the reducible structures used for them. We show that in expectation the algorithms make incremental progress in finding such structures and beyond. The current best known kernelization of the W-separator uses linear programming methods and requires non-trivial post-processing steps to extract the reducible structures. We provide additional structural features to show that evolutionary algorithms with appropriate objectives are also capable of extracting them. Our results show that evolutionary algorithms with different objectives guide the search and admit fixed parameterized runtimes to solve or approximate (even arbitrarily close) the W-separator problem.

关键词： Evolutionary algorithms parameterized complexity Runtime analysis

来源：评论

学校读者我要写书评

暂无评论

AN EXPONENTIAL TIME parameterized ALGORITHM FOR PLANAR DISJOINT PATHS

引用

SIAM JOURNAL ON COMPUTING 2025年第2期54卷 321-418页

作者： Lokshtanov, Daniel Misra, Pranabendu Pilipczuk, Michal Saurabh, Saket Zehavi, Meirav Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA Chennai Math Inst Siruseri 603103 Tamil Nadu India Univ Warsaw Inst Informat PL-02097 Warsaw Poland HBNI Inst Math Sci Chennai 600113 Tamil Nadu India Univ Bergen N-5007 Bergen Norway Chennai Math Inst IRL 2000 ReLaX Siruseri 603103 Tamil Nadu India Ben Gurion Univ Negev Beer Sheva Israel

In the disjoint paths problem, the input is an undirected graph G on n vertices and a set of k vertex pairs, \{si,ti\}ki=1, and the task is to find k pairwise vertex-disjoint paths such that the i'th path connects sito ti. In this paper, we give a parameterized algorithm with running time 2O(k 2)nO(1) for planar disjoint paths, the variant of the problem where the input graph is required to be planar. Our algorithm is based on the unique linkage/treewidth reduction theorem for planar graphs by Adler et al. [J. Combin. Theory Ser. B, 122 (2017), pp. 815--843], the algebraic cohomology based technique of Schrijver [SIAM J. Comput., 23 (1994), pp. 780--788], and one of the key combinatorial insights developed by Cygan et al. [Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 197--206] in their algorithm for disjoint paths on directed planar graphs. To the best of our knowledge, our algorithm is the first parameterized algorithm to exploit the fact that the treewidth of the input graph is small, and it does so in a way that is completely different from the use of dynamic programming.

关键词： planar disjoint paths graph minors parameterized complexity algebraic flow

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：