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

7th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC)

作者： Huang, Binchao Li, Jianping Lih, Ko-Wei Wang, Haiyan Yunnan Univ Dept Math Kunming Peoples R China Acad Sinica Inst Math Taipei Taiwan Yunnan Univ Finance & Econ Sch Math & Stat Kunming Peoples R China

ISBN: (纸本)9781479986460

We are given a set of items, and a set of knapsacks. Both the weight and the profit of an item are functions of the knapsack, and each knapsack has a positive real capacity. A restriction is setting that the number of the items which are admissible to each knapsack is no more than k, and these items are taken as input for each knapsack. We consider two following objectives: (1) maximizing the total profit of all the knapsacks (Max-Sum k-GMK);(2) maximizing the minimum profit of all the knapsacks (Max-Min k-GMK). We show that the two problems are NP-complete when k is greater than or equal t to 4. For the Max-Sum k-GMK problem, we can obtain a 1/2-approximation algorithm, and especially when k=2, we design an optimal algorithm. For the Max-Min k-GMK problem, we present a 1/(k-1)-approximation algorithm, and especially when k=2, this algorithm is an optimal algorithm.

关键词： an item assignment method approximation algorithms 3-bounded 3-dimensional matching problem (3DM-3) multiple knapsack problem polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

On Hardness of Multiflow Transmission in Delay Constrained Cooperative Wireless Networks

On Hardness of Multiflow Transmission in Delay Constrained C...

引用

54th Annual IEEE Global Telecommunications Conference (GLOBECOM)

作者： Baghaie, Marjan Hochbaum, Dorit S. Krishnamachari, Bhaskar Univ Southern Calif Dept Elect Engn Los Angeles CA 90089 USA Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA

ISBN: (纸本)9781424492688

We consider the problem of energy-efficient transmission in multi-flow multihop cooperative wireless networks. Although the performance gains of cooperative approaches are well known, the combinatorial nature of these schemes makes it difficult to design efficient polynomial-time algorithms for joint routing, scheduling and power control. This becomes more so when there is more than one flow in the network. It has been conjectured by many authors, in the literature, that the multiflow problem in cooperative networks is an NP-hard problem. In this paper, we formulate the problem, as a combinatorial optimization problem, for a general setting of k-flows, and formally prove that the problem not only NP-hard but it is o(n(1/7-epsilon)) inapproxmiable. To our knowledge, the results in this paper provide the first such inapproxmiablity proof in the context of multiflow cooperative wireless networks. We further prove that for a special case of k = 1 the solution is a simple path, and offer a polynomial time algorithm for jointly optimizing routing, scheduling and power control.

关键词： Delay Interference NP-hard problem Peer to peer computing polynomials Relays Routing Wireless networks combinatorial optimization problem cooperative communication delay constrained cooperative wireless networks delays energy-efficient transmission joint routing multi-flow multihop cooperative wireless networks multiflow transmission optimisation polynomial-time algorithms polynomials power control scheduling telecommunication network routing

来源：评论

学校读者我要写书评

暂无评论

algorithms and Complexity of s-Club Cluster Vertex Deletion 32nd

Algorithms and Complexity of <i>s</i>-Club Cluster Vertex De...

引用

32nd International Workshop on Combinatorial algorithms (IWOCA)

作者： Chakraborty, Dibyayan Chandran, L. Sunil Padinhatteeri, Sajith Pillai, Raji R. Indian Inst Sci Bangalore Karnataka India BITS Pilani Hyderabad India

ISBN: (纸本)9783030799878;9783030799861

An s-club is a graph which has diameter at most s. Let G be a graph. A set of vertices D subset of V(G) is an s-club deleting (s-CD) set if each connected component of G - D is an s-club. In the s-CLUB CLUSTER VERTEX DELETION (s-CVD) problem, the goal is to find an s-CD set with minimum cardinality. When s = 1, the s-CVD is equivalent to the well-studied CLUSTER VERTEX DELETION problem. On the negative side, we show that unless the Unique Games Conjecture is false, there is no (2 - epsilon)-algorithm for 2-CVD on split graphs, for any epsilon > 0. This contrast the polynomial-time solvability of CLUSTER VERTEX DELETION on split graphs. We show that for each s >= 2, s-CVD is NP-hard on bounded degree planar bipartite graphs and APX-hard on bounded degree bipartite graphs. On the positive side, we give a polynomial-time algorithm to solve s-CVD on trapezoid graphs, for each s >= 1.

关键词： Vertex deletion problem s-Club Split graphs (Planar) bipartite graphs NP-hardness APX-hardness Trapezoid graphs polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

GENERALIZED QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMMING FOR SIGNAL PROCESSING

GENERALIZED QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMMING ...

引用

IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Khabbazibasmenj, Arash Vorobyov, Sergiy A. Univ Alberta Dept Elect & Comp Engn Edmonton AB Canada Aalto Univ Dept Signal Proc & Acoust Espoo Finland

ISBN: (纸本)9781479928934

In this paper, we introduce and solve a particular generalization of the quadratically constrained quadratic programming (QCQP) problem which is frequently encountered in different fields of signal processing and communications. Specifically, we consider such generalization of the QCQP problem that comprises compositions of one-dimensional convex and quadratic functions in the constraint and the objective functions. We show that this class of problems can be precisely or approximately recast as the difference-of-convex functions (DC) programming problem. Although the DC programming problem can be solved through the branch-and-bound methods, these methods do not have any worst-case polynomial-time complexity guarantees. Therefore, we develop a new approach with worst-case polynomial-time complexity that can solve the corresponding DC problem of a generalized QCQP problem. It is analytically guaranteed that the point obtained by this method satisfies the Karsuh-Kuhn-Tucker (KKT) optimality conditions. Furthermore, the global optimality can be proved analytically under certain conditions. The new proposed method can be interpreted in terms of the Newton's method as applied to a non-constrained optimization problem.

关键词： Generalized QCQP problem DC programming polynomial-time algorithms array processing cooperative communications

来源：评论

学校读者我要写书评

暂无评论

algorithms and Hardness for the Longest Common Subsequence of Three Strings and Related Problems 30th

Algorithms and Hardness for the Longest Common Subsequence o...

引用

30th International Symposium on String Processing and Information Retrieval (SPIRE) / 18th Workshop on Compression, Text, and algorithms (WCTA)

作者： Wang, Lusheng Zhu, Binhai City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China City Univ Hong Kong ShenZhen Res Inst Shenzhen Peoples R China Montana State Univ Gianforte Sch Comp Bozeman MT 59717 USA

ISBN: (纸本)9783031439797;9783031439803

A string is called a square (resp. cube) if it is in the form of XX = X-2 (resp. XXX = X-3). Given a sequence S of length n, a fundamental problem studied in the literature is the problem of computing a longest subsequence of S which is a square or cube (i.e., the longest square/cubic subsequence problem). While the longest square subsequence (LSS) can be computed in O(n(2)) time, the longest cubic subsequence (LCubS) is only known to be solvable in O(n(5)) time, using the longest common subsequence of three strings (LCS-3) as a subroutine (which was much less studied compared with LCS for two strings, or LCS-2). To improve the running time for LCubS, we look at its complementary version and also investigate LCS-3 for three strings S-1, S-2, S-3, with input lengths m <= n(1) <= n(2) respectively. Firstly, we generalize an algorithm by Nakatsu et al. for LCS-2 to have an O(n(1)n(2)delta) algorithm for computing LCS-3, where delta is the minimum number of letters to be deleted in S-1 to have an LCS-3 solution for S-1, S-2 and S-3. This results in an O(k(3)n(2)) algorithm for LCubS, where k is the minimum number of letters deleted in S to have a feasible solution. Then, let R be the number of triples (i, j, k) that match in the input, i.e., S-1[i] = S-2[j] = S-3[k], we show that LCS-3 can be computed in O(n+ R log log n + R-2) time (n is the maximum length of the three input strings). Finally, we define the t-pseudo-subsequence of S under an integer parameter t, which is a string Z containing a subsequence S ' of S such that S ' can be obtained from Z by deleting at most t letters. Subsequently, we study the longest majority t-pseudo-subsequence (LMtPS) of S-i, i = 1..3, which is a t-pseudo-subsequence T = t(1)t(2) center dot center dot center dot t(K) of S-i, i = 1..3, with the maximum length K;moreover, when T is aligned with some subsequence S-i ''s of length K in S-i, i = 1..3, each t(j) matches at least two letters with S-i ', i = 1..3. We show that LMtPS of three

关键词： Longest common subsequence Longest cubic subsequence NP-completeness polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

On Optimal Read Trimming in Next Generation Sequencing and Its Complexity

On Optimal Read Trimming in Next Generation Sequencing and I...

引用

1st International Conference on algorithms for Computational Biology (AlCoB)

作者： Hedtke, Ivo Lemnian, Ioana Mueller-Hannemann, Matthias Grosse, Ivo Univ Osnabruck Dept Math & Comp Sci D-49076 Osnabruck Germany Univ Halle Wittenberg Inst Comp Sci D-06120 Halle Germany German Ctr Integrat Biodivers Res iDiv D-04103 Leipzig Germany

ISBN: (纸本)9783319079530;9783319079523

Read trimming is a fundamental first step of the analysis of next generation sequencing (NGS) data. Traditionally, read trimming is performed heuristically, and algorithmic work in this area has been neglected. Here, we address this topic and formulate three constrained optimization problems for block-based trimming, i.e., truncating the same low-quality positions at both ends for all reads and removing low-quality truncated reads. We find that the three problems are NP-hard. However, the non-random distribution of quality scores in NGS data sets makes it tempting to speculate that quality constraints for read positions are typically satisfied by fulfilling quality constraints for reads. Based on this speculation, we propose three relaxed problems and develop efficient polynomial-time algorithms for them. We find that (i) the omitted constraints are indeed almost always satisfied and (ii) the algorithms for the relaxed problems typically yield a higher number of untrimmed bases than traditional heuristics.

关键词： Next Generation Sequencing Trimming NP-completeness polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Finding Nontrivial Zeros of Quadratic Forms over Rational Function Fields of Characteristic 2 22

Finding Nontrivial Zeros of Quadratic Forms over Rational Fu...

引用

International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Kutas, Peter Montessinos, Mickael Zabradi, Gergely Csahok, timea Eotvos Lorand Univ Budapest Hungary Univ Birmingham Budapest Hungary Vilnius Univ Fac Math & Informat Vilnius Inst Math Vilnius Lithuania Renyi Inst Math Lendulet Automorph Res Grp Budapest Hungary Univ Oxford Oxford England

ISBN: (纸本)9781450386883

We propose polynomial-time algorithms for finding nontrivial zeros of quadratic forms with four variables over rational function fields of characteristic 2. We apply these results to find prescribed quadratic subfields of quaternion division algebras and zero divisors in M-2(D), the full matrix algebra over a division algebra, given by structure constants. We also provide an implementation of our results in MAGMA which shows that the algorithms are truly practical.

关键词： quadratic forms quaternion algebras polynomial-time algorithms characteristic 2 function fields

来源：评论

学校读者我要写书评

暂无评论

Reconfiguring k-path Vertex Covers 14th

Reconfiguring k-path Vertex Covers

引用

14th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Hoang, Duc A. Suzuki, Akira Yagita, Tsuyoshi Kyushu Inst Technol Fukuoka Japan Tohoku Univ Sendai Miyagi Japan

ISBN: (纸本)9783030398811;9783030398804

A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The k-Path Vertex Cover Reconfiguration (k-PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of k-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of k-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: TS, TJ, and TAR. The problem for k = 2, known as the Vertex Cover Reconfiguration (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes including planar graphs, bounded bandwidth graphs, chordal graphs, and bipartite graphs, can be extended for k-PVCR. In particular, we prove a complexity dichotomy for k-PVCR on general graphs: on those whose maximum degree is 3 (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is 2 (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for k-PVCR on trees under each of TJ and TAR. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.

关键词： Combinatorial Reconfiguration Computational complexity k-path vertex cover PSPACE-completeness polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Compact Wakeup Scheduling in Wireless Sensor Networks

Compact Wakeup Scheduling in Wireless Sensor Networks

引用

IEEE Global Telecommunications Conference (GLOBECOM 2010)

作者： Ma, Junchao Lou, Wei Hong Kong Polytech Univ Dept Comp Kowloon Hong Kong Peoples R China

ISBN: (纸本)9781424456383

In a traditional wakeup scheduling, sensor nodes start up numerous times to communicate in a period, thus consuming extra energy due to state transitions (e.g. from the sleep state to the active state). In this paper, we address a novel wakeup scheduling problem called compact wakeup scheduling, in which a node needs to wake up only once to communicate bidirectionally with all its neighbors. However, not all communication graphs have valid compact wakeup schedulings, and thus we focus on tree and grid topologies that have valid compact wakeup schedulings. We propose polynomial-time algorithms using the optimum number of time slots in a period for tree and grid topologies.

关键词： active state compact wakeup scheduling grid topologies polynomial-time algorithms scheduling sensor nodes sleep state state transitions telecommunication network topology tree topologies wireless sensor networks wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

Maximum colorful independent sets in vertex-colored graphs

引用

Electronic Notes in Discrete Mathematics 2018年 68卷 251-256页

作者： Manoussakis, Yannis Pham, Hong Phong LRI Univ.Paris Sud CNRS CentraleSupélec Université Paris-Saclay Orsay Cedex 91405 France

In this paper we study the problem of finding a maximum colorful independent set in vertex-colored graphs. Specifically, given a graph with colored vertices, we wish to find an independent set containing the maximum number of colors. Here we aim to give a dichotomy overview on the complexity of this problem. We first show that the problem is NP-hard even for some cases where the maximum independent set problem is easy, such as cographs and P₅-free graphs. Next, we provide polynomial-time algorithms for cluster graphs and trees. © 2018 Elsevier B.V.

关键词： maximum colorful independent sets polynomial-time algorithms vertex-colored graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：