Search

Abstract: The bandwidth of a graph on vertices is the minimum such that the vertices of can be labeled from to such that the labels of every pair of adjacent vertices differ by at most . In this paper, we present a 2-approximation algorithm for the Bandwidth problem that takes worst-case time and uses polynomial space. This improves both the previous best 2- and 3-approximation algorithms of Cygan et al. which have and worst-case running time bounds, respectively. Our algorithm is based on constructing bucket decompositions of the input graph. A bucket decomposition partitions the vertex set of a graph into ordered sets (called buckets) of (almost) equal sizes such that all edges are either incident to vertices in the same bucket or to vertices in two consecutive buckets. The idea is to find the smallest bucket size for which there exists a bucket decomposition. The algorithm uses a divide-and-conquer strategy along with dynamic programming to achieve the improved time bound. [Copyright &y& Elsevier]

In this paper, we propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds reported in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala,Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoret. Comput. Sci. 235(1) (2000), pp. 25–42; J. Povh and F. Rendl,A copositive programming approach to graph partitioning, SIAM J. Optim. 18(1) (2007), pp. 223–241]. [ABSTRACT FROM AUTHOR]

Abstract: Motivated by problems in comparative genomics and paleogenomics, we study the computational complexity of the Gapped Consecutive-Ones Property (-C1P) Problem: given a binary matrix and two integers and , decide if the columns of can be permuted such that each row contains at most blocks of ones and no two neighboring blocks of ones are separated by a gap of more than zeros. The classical C1P decision problem, which is known to be polynomial-time solvable is equivalent to the -C1P problem. We extend our earlier results on this problem [C. Chauve, J. Mauch, M. Patterson, On the gapped consecutive-ones property, in: Proceedings of the European Conference on Combinatorics, Graphs Theory and Applications (EuroComb), in: Electronic Notes in Discrete Mathematics, vol. 34, 2009, pp. 121–125] to show that for every , the -C1P Problem is NP-complete, and that for every , the -C1P Problem is NP-complete. On the positive side, we also show that if and the maximum degree of are constant, the problem is related to the classical Graph Bandwidth Problem and can be solved in polynomial time using a variant of an algorithm of Saxe [J.B. Saxe, Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time, SIAM Journal on Algebraic and Discrete Methods 1 (4) (1980) 363–369]. [Copyright &y& Elsevier]

Channel-optimized quantizer index assignment and maximum a posteriori (MAP) decoding have been extensively studied for error-resilient communications. An interesting and largely untreated problem is how to optimize the index assignment with respect to joint source-channel MAP decoding. In this paper we formulate the above problem as one of quadratic assignment, and discuss its solutions from very general to some special cases. For highly correlated Gaussian Markov sources and Hamming distortion, we can construct the optimal index assignment analytically. For general cases, simulated annealing algorithm is adopted to search for the optimal index assignment. Experimental results are presented to demonstrate the performance improvement of the index assignments optimized for MAP decoding over those designed for hard-decision decoding (e.g. Gray code). The reduction of symbol error rate and mean squared error can be as large as 40% and 50% respectively for highly correlated Gaussian Markov sources. [ABSTRACT FROM AUTHOR]