This paper proposes an algorithm to obtain the sampling factors to model any frequency partitioning so that it is realized using low complexity rational decimated non-uniform filter banks (RDNUFBs). The proposed algor...
详细信息
This paper proposes an algorithm to obtain the sampling factors to model any frequency partitioning so that it is realized using low complexity rational decimated non-uniform filter banks (RDNUFBs). The proposed algorithm is employed to approximate the Bark scale to find a rational frequency partitioning that can be realized using RDNUFBs with less approximation error. The proposed Bark frequency partitioning is found to reduce the average deviation in centre frequency and bandwidth by 65.04% and 48.50%, respectively, and root-mean-square bandwidth deviation by 54.46% when compared to those of the existing perceptual wavelet approximation of Bark scale. In the first filter bank design approach discussed in the paper, a near-perfect reconstruction partially cosine modulated filter bank is employed to obtain the improved Bark frequency partitioning. In the second design approach, the hardware complexity of the PCM-based RDNUFB is reduced by deriving the channels with different sampling factors from the same prototype filter by the method of channel merging. There is a considerable reduction of 40.83% in the number of multipliers when merging of partially cosine modulated channels is employed. It is also found that both the proposed approaches can reduce the delay by 95.17% when compared to the existing rational tree approximation methods and hence, are suitable for real-time applications.
Given a set of items, and a conflict graph defined on the item set, the problem of bin packing with conflicts asks for a partition of items into a minimum number of independent sets so that the total size of items in ...
详细信息
Given a set of items, and a conflict graph defined on the item set, the problem of bin packing with conflicts asks for a partition of items into a minimum number of independent sets so that the total size of items in each independent set does not exceed the bin capacity. As a generalization of both classic bin packing and classic vertex coloring, it is hard to approximate the problem on general graphs. We present new approximation algorithms for bipartite graphs and split graphs. The absolute approximation ratios are shown to be 5 /3 and 2 respectively, both improving the existing results.
In this paper, we consider the lower-bounded k-median problem (LB k-median) that extends the classical k-median problem. In the LB k-median, a set of facilities, a set of clients and an integer k are given. Every faci...
详细信息
ISBN:
(纸本)9783030581503;9783030581497
In this paper, we consider the lower-bounded k-median problem (LB k-median) that extends the classical k-median problem. In the LB k-median, a set of facilities, a set of clients and an integer k are given. Every facility has its own lower bound on the minimum number of clients that must be connected to the facility if it is opened. Every facility-client pair has its connection cost. We want to open at most k facilities and connect every client to some opened facility, such that the total connection cost is minimized. As our main contribution, we study the LB k-median and present our main bi-criteria approximation algorithm, which, for any given constant alpha is an element of [0,1), outputs a solution that satisfies the lower bound constraints by a factor of a and has an approximation ratio of 1+alpha/1-alpha rho, where rho is the state-of-art approximation ratio for the k-facility location problem (k-FL). Then, by extending the main algorithm to several general versions of the LB k-median, we show the versatility of our algorithm for the LB k-median. Last, through providing relationships between the constant a and the approximation ratios, we demonstrate the performances of all the algorithms for the LB k-median and its generalizations.
In this paper, we initiate the study of total liar's domination of a graph. A subset LaS dagger V of a graph G=(V,E) is called a total liar's dominating set of G if (i) for all vaV, |N (G) (v)a (c) L|a parts p...
详细信息
In this paper, we initiate the study of total liar's domination of a graph. A subset LaS dagger V of a graph G=(V,E) is called a total liar's dominating set of G if (i) for all vaV, |N (G) (v)a (c) L|a parts per thousand yen2 and (ii) for every pair u,vaV of distinct vertices, |(N (G) (u)a(a)N (G) (v))a (c) L|a parts per thousand yen3. The total liar's domination number of a graph G is the cardinality of a minimum total liar's dominating set of G and is denoted by gamma (TLR) (G). The Minimum Total Liar's Domination Problem is to find a total liar's dominating set of minimum cardinality of the input graph G. Given a graph G and a positive integer k, the Total Liar's Domination Decision Problem is to check whether G has a total liar's dominating set of cardinality at most k. In this paper, we give a necessary and sufficient condition for the existence of a total liar's dominating set in a graph. We show that the Total Liar's Domination Decision Problem is NP-complete for general graphs and is NP-complete even for split graphs and hence for chordal graphs. We also propose a 2(ln Delta(G)+1)-approximation algorithm for the Minimum Total Liar's Domination Problem, where Delta(G) is the maximum degree of the input graph G. We show that Minimum Total Liar's Domination Problem cannot be approximated within a factor of for any I mu > 0, unless NPaS dagger DTIME(|V|(loglog|V|)). Finally, we show that Minimum Total Liar's Domination Problem is APX-complete for graphs with bounded degree 4.
In this paper, we study the dynamic facility location problem with submodular penalties （DFLPSP）. We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.
In this paper, we study the dynamic facility location problem with submodular penalties （DFLPSP）. We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.
We study a generalization of the vertex cover problem. For a given graph with weights on the vertices and an integer k, we aim to find a subset of the vertices with minimum total weight, so that at least k edges in th...
详细信息
We study a generalization of the vertex cover problem. For a given graph with weights on the vertices and an integer k, we aim to find a subset of the vertices with minimum total weight, so that at least k edges in the graph are covered. The problem is called the k-partial vertex cover problem. There are some 2-approximation algorithms for the problem. In the paper we do not improve on the approximation ratios of the previous algorithms, but we derive an iterative rounding algorithm. We present our technique in two algorithms. The first is an iterative rounding algorithm and gives a （2 ＋ Q/OPT ）-approximation for the k-partial vertex cover problem where Q is the largest finite weight in the problem definition and OPT is the optimal value for the instance. The second algorithm uses the first as a subroutine and achieves an approximation ratio of 2.
Both matroid means and knapsack means are variations of the classic k-means problem in which we replace the cardinality constraint by matroid constraint or knapsack constraint respectively. In this paper, we give a 64...
详细信息
Both matroid means and knapsack means are variations of the classic k-means problem in which we replace the cardinality constraint by matroid constraint or knapsack constraint respectively. In this paper, we give a 64-approximation algorithm for the matroid means problem and a (1128 + ??)-approximation algorithm for the knapsack means problem by using a simpler and more efficient rounding method. We improve previous 304 approximate ratio for the former and 20016 approximate ratio for the latter. In the rounding process, the application of integrality of the intersection of submodular (or matroid) polyhedra provides strong theoretical support. Moreover, we extend this method to matroid means problem with penalties, and give 64 and 880-approximate algorithms for uniform penalties and nonuniform penalties problem.
Graph routing problems have been investigated extensively in operations research, computer science and engineering due to their ubiquity and vast applications. In this paper, we study constant approximation algorithms...
详细信息
ISBN:
(纸本)9783030581503;9783030581497
Graph routing problems have been investigated extensively in operations research, computer science and engineering due to their ubiquity and vast applications. In this paper, we study constant approximation algorithms for some variations of the cluster general routing problem. In this problem, we are given an edge-weighted complete undirected graph G = (V, E, c), whose vertex set is partitioned into clusters C-1, ..., C-k. We are also given a subset V' of V and a subset E' of E. The weight function c satisfies the triangle inequality. The goal is to find a minimum cost walk T that visits each vertex in V' only once, traverses every edge in E' at least once and for every i is an element of [k] all vertices of C-i are traversed consecutively.
The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (> 1.1379) unless P=NP, a...
详细信息
The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (> 1.1379) unless P=NP, and the current best approximation algorithm achieves the ratio of 1.5. MAX SMTI remains NP-hard even when preference lists of one side do not contain ties, and it cannot be approximated within 21/19 (> 1.1052) unless P=NP. However, even under this restriction, the best known approximation ratio is still 1.5. In this paper, we improve it to 25/17 (< 1.4706).
We consider the scheduling of simple linear deteriorating jobs on parallel machines from a new perspective based on game theory. In scheduling, jobs are often controlled by independent and selfish agents, in which eac...
详细信息
We consider the scheduling of simple linear deteriorating jobs on parallel machines from a new perspective based on game theory. In scheduling, jobs are often controlled by independent and selfish agents, in which each agent tries to select a machine for processing that optimizes its own payoff while ignoring the others. We formalize this situation as a game in which the players are job owners, the strategies are machines, and a player's utility is inversely proportional to the total completion time of the machine selected by the agent. The price of anarchy is the ratio between the worst-case equilibrium makespan and the optimal makespan. In this paper, we design a game theoretic approximation algorithm A and prove that it converges to a pure-strategy Nash equilibrium in a linear number of rounds. We also derive the upper bound on the price of anarchy of A and further show that the ratio obtained by A is tight. Finally, we analyze the time complexity of the proposed algorithm. (C) 2014 Elsevier B.V. All rights reserved.
暂无评论