Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability

Data reduction is a key technique in the study of fixed parameter algorithms. In the AI literature, pruning techniques based on simple and efficient-to-implement reduction rules also play a crucial role in the success of many industrial-strength solvers. Understanding the effectiveness and the applicability of data reduction as a technique for designing heuristics for intractable problems has been one of the main motivations in studying the phase transition of randomly-generated instances of NP-complete problems.In this paper, we take the initiative to study the power of data reductions in the context of random instances of a generic intractable parameterized problem, the weighted d-CNF satisfiability problem. We propose a non-trivial random model for the problem and study the probabilistic behavior of the random instances from the model. We design an algorithm based on data reduction and other algorithmic techniques and prove that the algorithm solves the random instances with high probability and in fixed-parameter polynomial time O(dknm) where n is the number of variables, m is the number of clauses, and k is the fixed parameter. We establish the exact threshold of the phase transition of the solution probability and show that in some region of the problem space, unsatisfiable random instances of the problem have parametric resolution proof of fixed-parameter polynomial size. Also discussed is a more general random model and the generalization of the results to the model.     

A trust degree based access control in grid environments

The purpose of grid computing is to enable coordinated resource sharing and support cooperative work between different domains in dynamic grid environments. In order to protect each participant’s privilege and security, a secure and efficient access control is essential. This paper presents a new approach of access mechanism based on trust relationships across domains. A new calculation method of trust in grid is proposed and the difference between intro-domain trust and inter-domain trust is analyzed. In addition, a novel access control framework combined with trust degree is given from this proposal. It is shown to be adaptive for both intro-domain and inter-domain conditions. Hence, a prototype system based on the proposed model is introduced; furthermore, it has been shown as a dynamic and fine-granularity access control method through performance analyses and has also been demonstrated as a suitable system for grid environments.     

Opportunistic channel selection approach under collision probability constraint in cognitive radio systems

In this work, we consider a cognitive radio system with multiple primary channels and one secondary user, and then we introduce a channel-usage pattern model and some basic concepts in this system. Based on this system model and the basic concepts, we propose two opportunistic channel selection algorithms to optimize the throughput of the secondary user: minimum collision rate channel selection algorithm and minimum handoff rate channel selection algorithm. According to the two algorithms, we, respectively, present the channel selection scheme based on minimum collision rate algorithm (CSS-MCRA) and the channel selection scheme based on minimum handoff rate algorithm (CSS-MHRA) under the constraint that the collision probability is bounded below collision tolerable level. Theoretical analysis and simulation results both show that, on one hand, both CSS-MCRA scheme and CSS-MHRA can follow the constraint of collision tolerable level; on the other hand, the performance of CSS-MCRA scheme is better than that of CSS-MHRA scheme if handoff latency is zero or very low, while the performance of CSS-MHRA scheme is better than that of CSS-MCRA scheme if handoff latency is long enough.     

Two-Dimensional Multilabel Active Learning with an Efficient Online Adaptation Model for Image Classification

Conventional active learning dynamically constructs the training set only along the sample dimension. While this is the right strategy in binary classification, it is suboptimal for multilabel image classification. We argue that for each selected sample, only some effective labels need to be annotated while others can be inferred by exploring the label correlations. The reason is that the contributions of different labels to minimizing the classification error are different due to the inherent label correlations. To this end, we propose to select sample-label pairs, rather than only samples, to minimize a multilabel Bayesian classification error bound. We call it two-dimensional active learning because it considers both the sample dimension and the label dimension. Furthermore, as the number of training samples increases rapidly over time due to active learning, it becomes intractable for the offline learner to retrain a new model on the whole training set. So we develop an efficient online learner to adapt the existing model with the new one by minimizing their model distance under a set of multilabel constraints. The effectiveness and efficiency of the proposed method are evaluated on two benchmark data sets and a realistic image collection from a real-world image sharing Web site—Corbis.     

Gradient‐Preserving Color Transfer

Color transfer is an image processing technique which can produce a new image combining one source image's contents with another image's color style. While being able to produce convincing results, however, Reinhard et al.'s pioneering work has two problems—mixing up of colors in different regions and the fidelity problem. Many local color transfer algorithms have been proposed to resolve the first problem, but the second problem was paid few attentions. In this paper, a novel color transfer algorithm is presented to resolve the fidelity problem of color transfer in terms of scene details and colors. It's well known that human visual system is more sensitive to local intensity differences than to intensity itself. We thus consider that preserving the color gradient is necessary for scene fidelity. We formulate the color transfer problem as an optimization problem and solve it in two steps—histogram matching and a gradient‐preserving optimization. Following the idea of the fidelity in terms of color and gradient, we also propose a metric for objectively evaluating the performance of example‐based color transfer algorithms. The experimental results show the validity and high fidelity of our algorithm and that it can be used to deal with local color transfer.     

Towards capacity and profit optimization of video-on-demand services in a peer-assisted IPTV platform

This paper studies the conditions under which peer-to-peer (P2P) technology may be beneficial in providing IPTV services over typical network architectures. It has three major contributions. First, we contrast two network models used to study the performance of such a system: a commonly used logical “Internet as a cloud” model and a “physical” model that reflects the characteristics of the underlying network. Specifically, we show that the cloud model overlooks important architectural aspects of the network and may drastically overstate the benefits of P2P technology. Second, we propose an algorithm called Zebra that pre-stripes content across multiple peers during idle hours to speed up P2P content delivery in an IPTV environment with limited upload bandwidth. We also perform simulations to measure Zebra’s effectiveness at reducing load on the content server during peak hours. Third, we provide a cost-benefit analysis of P2P video content delivery, focusing on the profit trade-offs for different pricing/incentive models rather than purely on capacity maximization. In particular, we find that under high volume of video demand, a P2P built-in incentive model performs better than any other model, while the conventional no-P2P model generates more profits when the request rate is low. The flat-reward model generally falls in between the usage-based model and the built-in model in terms of profitability except for low request rates. We also find that built-in and flat-reward models are more profitable than the usage-based model for a wide range of subscriber community sizes. Funding for J. Rahe’s research has been provided by AT&T Labs, the State of California under the MICR Oprogram, and by the Toshiba Corporation. Zhen Xiao is partially supported by China MOST project (2006BAH02A10).     

Micromachining of passive planar micromixer on poly (methyl methacrylate) substrate with excimer laser ablation

Excimer laser ablation technique was introduced into this work to fabricate a passive planar micromixer on the PMMA substrate. T-junction shaped and width-changed S-shaped microchannels were both designed in this micromixer to enhance mixing effect. The mixing experiment of distilled water and Rhodamine B with injection flow rate of 500 and 1,500 μm/s validates the mixing effectivity of this micromixer, and indicates the feasibility of excimer laser ablation in the microfabrication of μ-TAS device.     

Femtosecond laser-induced silicon surface morphology in water confinement

This article investigates the use of femtosecond laser induced surface morphology on silicon wafer surface in water confinement. Unlike irradiation of silicon surfaces in the air, there are no laser induced periodic structures, but irregular roughness is formed when the silicon wafer is ablated under water. The unique discovery of a smoothly processed silicon surface in water confinement under certain laser parameter combinations may help improve laser direct micromachining surface quality in industrial applications.     

Design and fabrication of an electrostatically suspended microgyroscope using UV-LIGA technology

A micromachined electrostatically suspended gyroscope, with a wheel-like rotor housed by top stator and bottom stator, using UV-LIGA microfabrication technology, was presented. The designed structure and basic operating principle of the gyroscope are described. The key steps in the fabrication process, such as wet etching of Pyrex glass pits for soldering, and integration of thick nickel structures by removal of SU-8 mold, were considered in detail and well solved. Cr/Pt/photoresist was used as etching mask and the etched pits, in depth of near 30 μm, with aspect ratio (depth to undercutting) of 0.75, were obtained. With metal foundations constructed for consolidation, successful integration of the nickel structures, in thickness of 200 μm, was achieved by successful removal of the SU-8 mold using oleum. After the two stators and the rotor were fabricated separately, they were assembled and soldering bonded to form axial and radial small gaps, hence, the initial prototype of the microgyroscope was realized. The key techniques described in this paper can be applied to fabrication of other micro devices. The metal foundation method, associated with removal of SU-8 mold by oleum, is expected to make SU-8 wider applications in making integrated microstructures with fabricated circuitry on the same chip.