37360298
Optimal Gossiping in Square Meshes in All-Port Mode and with Short Packets
We present optimal solutions for the gossiping problem in square meshes under the all-port, full-duplex (F*) and the all-port, half-duplex (H*) models. We assume packets are of finite size, each carrying at most one message.
8121247
On the hardness of minimizing space for all-shortest-path interval routing schemes
k-Interval Routing Scheme (k-IRS) is a compact routing method that allows up to k interval labels to be assigned to an arc; and global k-IRS allows not more than a total of k interval labels in the whole network. A fundamental problem is to characterize the networks that admit k-IRS (or global k-IRS). Many of the problems related to single-shortest-path k-IRS have already been shown to be NP-complete. For all-shortest-path k-IRS, the characterization problem remains open for k>=1. In this paper, we study the time complexity of devising minimal-space all-shortest-path k-IRSs and show that it is NP-complete to decide whether a graph admits an all-shortest-path k-IRS, for every integer k>=3, and so is that of deciding whether a graph admits an all-shortest-path k-strict IRS, for every integer k>=4. These are the first NP-completeness results for all-shortest-path k-IRS where k is a constant and the graph is unweighted. The NP-completeness holds also for the linear case. We also prove that it is NP-complete to decide whether an unweighted graph admits an all-shortest-path IRS with global compactness of at most k, which also holds for the linear and strict cases.
18896215
Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
We show that the Hamiltonicity of a regular graph G can be fully characterized by the numbers of blocks of consecutive ones in the binary matrix A+I, where A is the adjacency matrix of G, I is the unit matrix, and the blocks can be either linear or circular. Concretely, a k-regular graph G with girth g(G)>=5 has a Hamiltonian circuit if and only if the matrix A+I can be permuted on rows such that each column has at most (or exactly) k-1 circular blocks of consecutive ones; and if the graph G is k-regular except for two (k-1)-degree vertices a and b, then there is a Hamiltonian path from a to b if and only if the matrix A+I can be permuted on rows to have at most (or exactly) k-1 linear blocks per column. Then we turn to the problem of determining whether a given matrix can have at most k blocks of consecutive ones per column by some row permutation. For this problem, Booth and Lueker gave a linear algorithm for k=1 [Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, 1975, pp. 255-265]; Flammini et al. showed its NP-completeness for general k [Algorithmica 16 (1996) 549-568]; and Goldberg et al. proved the same for every fixed k>=2 [J. Comput. Biol. 2 (1) (1995) 139-152]. In this paper, we strengthen their result by proving that the problem remains NP-complete for every constant k>=2 even if the matrix is restricted to (1) symmetric, or (2) having at most three blocks per row.
14833504
Optimal gossiping in square 2D meshes
Gossiping is the communication problem in which each node has a unique message to be transmitted to every other node. The nodes exchange their message by packets. A solution to the problem is judged by how many rounds of packet sending it requires. In this paper, we consider the version of the problem in which small-size packets each carrying exactly one message are used. The nodes of the target meshes are assumed to be all-port (a node's incident edges can all be active at the same time); and their edges are either half-duplex or full-duplex, which are also known as the H* model and the F* model, respectively. We study the class of 2D square meshes. Soch and Tvrdik (SIROCCO'97, pp. 253-265; Tech. rep. DC-97-04, Dept. of CS&E, Czech Technical University) have obtained optimal algorithms for the F* model (for square or nonsquare meshes). Lau and Zhang (IEEE Trans. Parallel Distribut. Syst. 13 (4) (2002) 349-358) have obtained fast algorithms for the H* model. We present optimal algorithms for both models, with the interesting property that they route their messages along the same paths and in the same order, i.e. for any edge {u,v}, the i-th message from u to v under either model is the same message.
42750715
NP-Completeness Results for All-Shortest-Path Interval Routing
k-Interval Routing Scheme (k-IRS) is a compact routing method that allows up to k interval labels to be assigned to an arc. A fundamental problem is to characterize the networks that admit k-IRS. Many of the problems related to single-shortest-path k-IRS have already been shown to be NP-complete. For all-shortest-path k-IRS, the characterization problem remains open for k≥ 1. We investigate the time complexity of devising minimal-space all-shortest-path k-IRS and prove that it is NP-complete to decide whether a graph admits an all-shortest-path k-IRS, for every integer k≥ 3, as well as whether a graph admits an all-shortest-path k-strict IRS, for every integer k≥ 4. These are the first NP-completeness results for all-shortest-path k-IRS where k is a constant and the graph is unweighted. Moreover, the NP-completeness holds also for the linear case.
15753148
Bayesian Face Recognition Based on Markov Random Field Modeling
In this paper, a Bayesian method for face recognition is proposed based on Markov Random Fields (MRF) modeling. Constraints on image features as well as contextual relationships between them are explored and encoded into a cost function derived based on a statistical model of MRF. Gabor wavelet coefficients are used as the base features, and relationships between Gabor features at different pixel locations are used to provide higher order contextual constraints. The posterior probability of matching configuration is derived based on MRF modeling. Local search and discriminate analysis are used to evaluate local matches, and a contextual constraint is applied to evaluate mutual matches between local matches. The proposed MRF method provides a new perspective for modeling the face recognition problem. Experiments demonstrate promising results.
14656370
An Analysis-by-Synthesis Method for Heterogeneous Face Biometrics
Face images captured in different spectral bands, e.g. , in visual (VIS) and near infrared (NIR), are said to be heterogeneous. Although a person's face looks different in heterogeneous images, it should be classified as being from the same individual. In this paper, we present a new method, called face analogy , in the analysis-by-synthesis framework, for heterogeneous face mapping, that is, transforming face images from one type to another, and thereby performing heterogeneous face matching. Experiments show promising results.
3505472
Decentralized Fair Scheduling in Two-Hop Relay-Assisted Cognitive OFDMA Systems
In this paper, we consider a two-hop relay-assisted cognitive downlink Orthogonal frequency-division multiple access (OFDMA) system (named as secondary system) dynamically accessing a spectrum licensed to a primary network, thereby improving the efficiency of spectrum usage. A cluster-based relay-assisted architecture is proposed for the secondary system, where relay stations are employed for minimizing the interference to the users in the primary network and achieving fairness for cell-edge users in the secondary system. Based on this architecture, an asymptotically optimal solution is derived for jointly controlling data rates, transmission power, and subchannel allocation to optimize the average weighted sum goodput where the proportional fair scheduling (PFS) is included as a special case. This solution supports decentralized implementation, requires small communication overhead, and is robust against imperfect channel state information at the transmitter (CSIT) and imperfect sensing measurement. The proposed solution achieves significant throughput gain and better user-fairness compared with the existing designs. Finally, we derive a simple and asymptotically optimal scheduling solution as well as the associated closed-form performance under the proportional fair scheduling for a large number of users. The system throughput is shown to be O(N(1-qp)(1-qpN)lnlnKc), where Kc is the number of users in one cluster, N is the number of subchannels, and qp is the active probability of primary users.
9665993
Closed-loop cross-layer SDMA designs with outdated CSIT
In this paper, we propose a novel closed-loop approach for robust downlink multi-antenna cross-layer design with outdated channel state information at the transmitter (CSIT). Based on the ACK/NAK feedbacks from the mobiles, the proposed cross-layer design does not require the knowledge of CSIT error statistics. We formulate the cross-layer design as a mixed combinatorial search and Markov decision process (MDP). While it is well-known that general solutions for MDP are very complex, one important contribution of this paper is that we obtain simple closed-form power, rate and user allocation policies which are asymptotically optimal for small target frame error rate (FER). Simulation results illustrate that the performance of the proposed closed-loop cross-layer design is very robust with respect to the outdated CSIT, CSIT error model mismatch as well as channel variations due to Doppler.
2730430
Robust Optimal Cross-Layer Designs for TDD-OFDMA Systems with Imperfect CSIT and Unknown Interference: State-Space Approach Based on 1-bit ACK/NAK Feedbacks
Cross-layer designs for OFDMA systems have been shown to offer significant gains of spectral efficiency by exploiting the multiuser diversity over the temporal and frequency domains. In this paper, we shall propose a robust optimal cross-layer design for downlink TDD-OFDMA systems with imperfect channel state information at the base station (CSIT) and unknown interference in slow fading channels. Exploiting the ACK/NAK (1-bit) feedbacks from the mobiles, the proposed cross-layer design does not require knowledge of the CSIT error statistics or interference statistics. To take into account of the potential packet error due to the imperfect CSIT and unknown interference, we define average system goodput (which measures the average b/s/Hz successfully delivered to the mobile) as our optimization objective. We formulate the cross-layer design as a state-space control problem. The optimal power, optimal rate and optimal user allocations are determined as the output equations from the system states based on dynamic programming approach. Simulation results illustrate that the performance of the proposed closed-loop cross-layer design is very robust with respect to imperfect CSIT, unknown interference, model mismatch as well as channel variations due to Doppler.