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...
详细信息
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 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 ...
详细信息
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.
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...
详细信息
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 polynomialtime algorithm for jointly optimizing routing, scheduling and power control.
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 comm...
详细信息
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.
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 subseq...
详细信息
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
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, ...
详细信息
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.
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 subfield...
详细信息
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.
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 o...
详细信息
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 polynomialtime. 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.
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,...
详细信息
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.
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a ...
详细信息
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints;the problem is to decide whether or not the larger set of constraints has a satisfying assignment. This model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.
暂无评论