When a store sells items to customers, the store wishes to determine the prices of the items to maximize its profit. Intuitively, if the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. So it would be hard for the store to decide the prices of items. Assume that the store has a set V of n items and there is a set E of m customers who wish to buy those items, and also assume that each item i ∈ V has the production cost di and each customer ej ∈ E has the valuation vj on the bundle ej ⊆ V of items. When the store sells an item i ∈ V at the price ri, the profit for the item i is pi=ri-di. The goal of the store is to decide the price of each item to maximize its total profit. We refer to this maximization problem as the item pricing problem. In most of the previous works, the item pricing problem was considered under the assumption that pi ≥ 0 for each i ∈ V, however, Balcan, et al. [In Proc. of WINE, LNCS 4858, 2007] introduced the notion of "loss-leader," and showed that the seller can get more total profit in the case that pi < 0 is allowed than in the case that pi < 0 is not allowed. In this paper, we derive approximation preserving reductions among several item pricing problems and show that all of them have algorithms with good approximation ratio.

A high-efficiency CMOS rectifier circuit for UHF RFID applications was developed. The rectifier utilizes a self-Vth-cancellation (SVC) scheme in which the threshold voltage of MOSFETs is cancelled by applying gate bias voltage generated from the output voltage of the rectifier itself. A very simple circuit configuration and zero power dissipation characteristics in biasing enable excellent power conversion efficiency (PCE), especially under small RF input power conditions. At higher RF input power conditions, the PCE of the rectifier automatically decreases. This is the built-in self-power-regulation function. The proposed SVC CMOS rectifier was fabricated with a 0.35-µm CMOS process and the measured performance was compared with those of conventional nMOS, pMOS, and CMOS rectifiers and other types of Vth cancellation rectifiers as well. The SVC CMOS rectifier achieves 32% of PCE at the -10 dBm RF input power condition. This PCE is larger than rectifiers reported to date under this condition.

We have recently developed a method for feature extraction from multivariate data using an analogue of Kuramoto's dynamics for modeling collective synchronization in a network of coupled phase oscillators. In our method, which we call data synchronization, phase oscillators carrying multivariate data in their natural and updated rhythms achieve partial synchronizations. Their common rhythms are interpreted as the template vectors representing the general features of the data set. In this study, we discuss the link of data synchronization to the self-organizing map algorithm as a popular method for data mining and show through numerical experiments how our method can overcome the disadvantages of the self-organizing map algorithm in that unintentional selections of inappropriate reference vectors lead to false feature patterns.

The complex-valued self-organizing map (CSOM) realizes an adaptive distinction between plastic landmines and other objects in landmine visualization systems. However, when the spatial resolution in electromagnetic-wave measurement is not sufficiently high, the distinction sometimes fails. To solve this problem, in this paper, we propose two techniques to enhance the visualization ability. One is the utilization of SOM-space topology in the CSOM adaptive classification. The other is a novel feature extraction method paying attention to local correlation in the frequency domain. In experimental results, we find that these two techniques significantly improve the visualization performance. The local-correlation method contributes also to the reduction of the number of tuning parameters in the CSOM classification.

This paper presents a fully self-organized key management scheme for mobile ad hoc networks. Unlike most previous schemes, there is no priori shared secret or no priori trust relationship in the proposed scheme; every node plays the same role and carries out the same function of key management. The proposed scheme consists of (1) Handshaking (HS) and (2) Certificate request/reply (CRR) procedures. In HS, a node acquires the public key of the approaching node via a secure side channel. In CRR, a node requests certificates of a remote node via a radio channel to the nodes that it has HSed. If the number of received valid certificates that contain the same public key exceeds a given threshold, the node accepts the remote node's public key as valid. Security is rigorously analyzed against various known attacks and network costs are intensively analyzed mathematically. Using this analysis, we provide parameter selection guideline to optimize performance and to maintain security for diverse cases. Simulation results show that every node acquires the public keys of all other nodes at least 5 times faster than in a previous scheme.

Testing PLLs (phase-locked loops) is becoming an important issue that affects both time-to-market and production cost of electronic systems. Though a PLL is the most common mixed-signal building block, it is very difficult to test due to internal analog blocks and signals. In this paper, we propose a new PLL BIST (built-in self test) using the distorted frequency detector that uses only internal digital signals. The proposed BIST does not need to load any analog nodes of the PLL. Therefore, it provides an efficient defect-oriented structural test scheme, reduced area overhead, and improved test quality compared with previous approaches.

Wireless Sensor Networks (WSNs) have become a key technology for ubiquitous computing environments. In WSNs, battery recharge or replacement is impossible because sensors are left unattended after deployment. Therefore, WSNs need a networking protocol scheme to increase the life time of sensor nodes. The clustering technique is an efficient approach for reducing energy consumption in wireless sensor networks. In cluster topology, however, there is a problem which causes a large amount of energy consumption of cluster head. In addition, in the sparsely deployed sensor field, mesh topology can be more energy-efficient than cluster topology. In this paper, we propose a Hybrid Cluster Mesh (HCM) scheme, which recognizes the density of neighbor nodes and each node decides its topology itself, and HCM-RO (reorganization) scheme which reorganizes clusters. Simulation results show that the proposed hybrid topology control scheme is more energy-efficient than each topology of cluster or mesh.

An optimized Built-In Self-Test technology is proposed in this paper. A simplified algebraic model is developed to represent the configurations of single input change circuits. A novel single input change sequence generation technique is designed. It consists of a modified scan shift register, a seed storage array and a series of XOR gates. This circuitry can automatically generate single input change sequences of more unique vectors. Experimental results based on the ISCAS-89 benchmark show that the proposed method can achieve high stuck-at fault coverage with low switching activity during test applications.

The heterogeneous integration of GaAs HEMTs on a polyimide-covered AlN ceramic substrate was demonstrated using a fluidic self-assembly (FSA) technique. We used thin device blocks for the FSA, which have various advantages. In particular, they can reduce the drain-source capacitance Cds of the assembled HEMTs if the substrate has a low dielectric constant. This is a novel kind of semiconductor-on-insulator (SOI) technology. The dc and RF properties of the GaAs HEMTs on the polyimide/AlN substrate were studied and the reduction of Cds was confirmed. This technique was successfully applied to the SPDT switch, where a low Cds is essential for good isolation.

A variant of the self-shrinking generator (SSG) proposed at ICISC 2006, which we call SSG-XOR, was claimed to have better cryptographic properties than SSG in a practical setting. It was also claimed that SSG-XOR will be more secure than SSG. But we show that SSG-XOR has no advantage over SSG from the viewpoint of practical cryptanalysis, especially the guess-and-determine attack.

In the real world, it is not always true that neighboring houses are physically adjacent or close to each other. in other words, "neighbors" are not always "true neighbors." In this study, we propose a new Self-Organizing Map (SOM) algorithm, SOM with False-Neighbor degree between neurons (called FN-SOM). The behavior of FN-SOM is investigated with learning for various input data. We confirm that FN-SOM can obtain a more effective map reflecting the distribution state of input data than the conventional SOM and Growing Grid.

This paper proposes a new color halftone image quality assessment method based upon the color structural similarity measure with considering the human visual characteristics. To include the color visual characteristics, we carry out the color filtering for each luminance, red-green, and blue-yellow channels. Then, we apply the color structural similarity measure to the color filtered images, which are the reference image and the halftoned image, to evaluate the localized structural difference. By considering those characteristics, in this paper, the assessment of the color halftone images can be realized. We apply the proposed measure to the various kinds of color halftone images and confirm that the proposed measure can give reasonable results compared with the results by subjective evaluation.

We propose an Adjustable Parallel TCP (AP-TCP) which is a new scheme to control the aggregate throughput of parallel TCP flows. The AP-TCP can adjust the aggregate throughput to be any desired level irrespective of the parallel size (the number of parallel TCP flows). To adjust the aggregate throughput, we modify the increment factor of each parallel TCP flow to K2/N2 where N is the number of parallel TCP flows and K is a value equivalent to any desired level for the aggregate throughput. Once K is given, the AP-TCP attempts to have K times more bandwidth than a single TCP flow when they are competing on the same network path. Another feature of the AP-TCP is its self-adjustment scheme. There is no central coordination or control overhead for parallel TCP flows. We analyze the model of the AP-TCP theoretically and evaluate it by using NS-2 simulation.

This paper presents an asynchronous design technique, an enabler for the emerging technology of flexible microelectronics that feature low-temperature processed polysilicon (LTPS) thin-film transistors (TFT) and surface-free technology by laser annealing/ablation (SUFTLA®). The first design instance chosen is an 8-bit microprocessor. LTPS TFTs are good for realizing displays having integrated VLSI circuit at lower costs. However, LTPS TFTs have drawbacks, including substantial deviations in characteristics and the self-heating phenomenon. To solve these problems, the authors adopted the asynchronous circuit design technique and developed an asynchronous design language called Verilog+, which is based on a subset of Verilog HDL® and includes minimal primitives used for describing the communications between modules, and the dedicated tools including a translator called xlator and a synthesizer called ctrlsyn. The flexible 8-bit microprocessor stably operates at 500 kHz, drawing 180 µA from a 5 V power source. The microprocessor's electromagnetic emissions are 21 dB less than those of the synchronous counterpart.

This paper will propose a wolf attack probability (WAP) as a new measure for evaluating security of biometric authentication systems. The wolf attack is an attempt to impersonate a victim by feeding "wolves" into the system to be attacked. The "wolf" means an input value which can be falsely accepted as a match with multiple templates. WAP is defined as a maximum success probability of the wolf attack with one wolf sample. In this paper, we give a rigorous definition of the new security measure which gives strength estimation of an individual biometric authentication system against impersonation attacks. We show that if one reestimates using our WAP measure, a typical fingerprint algorithm turns out to be much weaker than theoretically estimated by Ratha et al. Moreover, we apply the wolf attack to a finger-vein-pattern based algorithm. Surprisingly, we show that there exists an extremely strong wolf which falsely matches all templates for any threshold value.

In this paper, we design a new coded cooperation protocol utilizing superposition modulation together with iterative decoding/detection algorithms. The aim of the proposed system is to apply "dirty paper coding" theory in the context of half-duplex relay systems. In the proposed system, the node transmits a superposed signal which consists of its own coded information and other node's re-coded information. The destination node detects and decodes the signal using the received signals at two continuous time-slots with iterative decoding algorithm. Moreover, the destination node detects the received signal using the results of decoding, iteratively. This paper provides the outage probability of the proposed system under the assumption that the proposed system can ideally perform dirty paper coding, and it is shown from the comparison between outage probabilities and simulated results that the proposed system can get close to the dirty paper coding theory.

This paper presents a new low power BIST TPG scheme for reducing scan transitions. It uses a transition freezing and melting method which is implemented of the transition freezing block and a MUX. When random test patterns are generated from an LFSR, transitions of those patterns satisfy pseudo-random Gaussian distribution. The proposed technique freezes transitions of patterns using a freezing value. Experimental results show that the proposed BIST TPG schemes can reduce average power reduction by about 60% without performance loss and peak power by about 30% in ISCAS'89 benchmark circuits.

This paper proposes a self-test method of coarse grain dynamically reconfigurable processors (DRPs) without hardware overhead. In the method, processor elements (PEs) compose a test frame, which consists of test pattern generators (TPGs), processor elements under test (PEUTs) and response analyzers (RAs), while testing themselves one another by changing test frames appropriately. We design several test frames with different structures, and discuss the relationship of the structures to the numbers of contexts and test frames for testing all the functions of PEs. A case study shows that there exists an optimal test frame which minimizes the test application time under a constraint.

In this paper, we propose a design for testability method for test programs of software-based self-test using test program templates. Software-based self-test using templates has a problem of error masking where some faults detected in a test generation for a module are not detected by the test program synthesized from the test. The proposed method achieves 100% template level fault efficiency, that is, it completely avoids the error masking. Moreover, the proposed method has no performance degradation (adds only observation points) and enables at-speed testing.

This paper describes novel CMOS level-conversion flip-flops for use in low-power SoCs with clustered voltage scaling. These flip-flops feed outputs directly into the front stage to support self-resetting and conditional operations. They thus have simple structures to avoid clock level shifting and redundant transitions, leading to substantial improvements in terms of power and area. The comparison results indicate that the proposed level-conversion flip-flops achieve power and area savings up to 50% and 31%, respectively, with no speed degradation as compared to conventional level-conversion flip-flops.