17041567
On-line scheduling of small open shops
We investigate the problem of on-line scheduling open shops of two and three machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive scheduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines, which is most competitive.
4000197
Lot-sizing scheduling with batch setup times
This paper is concerned with scheduling independent jobs on m parallel machines in such a way that the makespan is minimized. Each job j is allowed to split arbitrarily into several parts, which can be individually processed on any machine at any time. However, a setup for uninterrupted sj time units is required before any split part of job j can be processed on any machine. The problem is strongly NP-hard if the number m of machines is variable and weakly NP-hard otherwise. We give a polynomial-time $$\frac{5}{3}$$-approximation algorithm for the former case and a fully polynomial-time approximation scheme for the latter.
10605643
3D Volume Rotation Using Shear Transformations
We present a group of methods for decomposing an arbitrary 3D volume rotation into a sequence of simple shear (i.e., regular shift) operations. We explore different types of shear operations: 2Dbeam shear, a shear in one coordinate based on the other two coordinates; 2Dslice shear, a shear of a volume slice (in two coordinates) according to the third coordinate; and 2Dslice?beam shear, the combination of a beam shear and a slice shear. We show that an arbitrary 3D rotation can be decomposed into four 2D beam shears. We use this decomposition as a basis to obtain the sequence of 3D rotation decomposition into four 2D slice shears or three 2D slice?beam shears. Moreover, we observe that two consecutive slice shears can be achieved by shifting beams in 3D space, a transformation we call a 3D beam shear. Therefore, an arbitrary 3D rotation can be decomposed into only two 3D beam shears. Because of the regularity and simplicity of the shear operation, these decompositions are suitable for implementations on a multipipelined hardware or a massively parallel machine. In addition, we present a resampling scheme in which only a single-pass resampling is required for performing multiple-pass shears to achieve the 3D volume rotation.
987186
Implementing Minimized Multivariate PKC on Low-Resource Embedded Systems
Multivariate (or $\mathcal{MQ}$) public-key cryptosystems (PKC) are alternatives to traditional PKCs based on large algebraic structures (e.g., RSA and ECC); they usually execute much faster than traditional PKCs on the same hardware. However, one major challenge in implementing multivariates in embedded systems is that the key size can be prohibitively large for applications with stringent resource constraints such as low-cost smart cards, sensor networks (e.g., Berkeley motes), and radio-frequency identification (RFID). In this paper, we investigate strategies for shortening the key of a multivariate PKC. We apply these strategies to the Tame Transformation Signatures (TTS) as an example and quantify the improvement in key size and running speed, both theoretically and via implementation. We also investigate ways to save die space and energy consumption in hardware, reporting on our ASIC implementation of TTS on a TSMC 0.25μm process. Even without any key shortening, the current consumption of TTS is only 21 μA for computing a signature, using 22,000 gate equivalents and 16,000 100-kHz cycles (160 ms). With circulant-matrix key shortening, the numbers go down to 17,000 gates and 4,400 cycles (44 ms). We therefore conclude: besides representing a future-proofing investment against the emerging quantum computers, multivariates can be immediately useful in niches.
607529
Toward a Query Language for Network Attack Data
The growing sophistication and diversity of malicious activity in the Internet presents a serious challenge for network security analysts. In this paper, we describe our efforts to develop a database and query language for network attack data from firewalls, intrusion detection systems and honeynets. Our first step toward this objective is to develop a prototype database and query interface to identify coordinated scanning activity in network attack data. We have created a set of aggregate views and templatized SQL queries that consider timing, persistence, targeted services, spatial dispersion and temporal dispersion, thereby enabling us to evaluate coordinated scanning along these dimensions. We demonstrate the utility of the interface by conducting a case study on a set of firewall and intrusion detection system logs from Dshield.org. We show that the interface is able to identify general characteristics of coordinated activity as well as instances of unusual activity that would otherwise be difficult to mine from the data. These results highlight the potential for developing a more generalized query language for a broad class of network intrusion data. The case study also exposes some of the challenges we face in extending our system to more generalized queries over potentially vast quantities of data.
10767971
The duality between information embedding and source coding with side information and some applications
Aspects of the duality between the information-embedding problem and the Wyner-Ziv (1976) problem of source coding with side information at the decoder are developed and used to establish a spectrum new results on these and related problems, with implications for a number of important applications. The single-letter characterization of the information-embedding problem is developed and related to the corresponding characterization of the Wyner-Ziv problem, both of which correspond to optimization of a common mutual information difference. Dual variables and dual Markov conditions are identified, along with the dual role of noise and distortion in the two problems. For a Gaussian context with quadratic distortion metric, a geometric interpretation of the duality is developed. From such insights, we develop a capacity-achieving information-embedding system based on nested lattices. We show the resulting encoder-decoder has precisely the same decoder-encoder structure as the corresponding Wyner-Ziv system based on nested lattices that achieves the rate-distortion limit. For a binary context with Hamming distortion metric, the information-embedding capacity is developed, along with its relationship to the corresponding Wyner-Ziv rate-distortion function. In turn, an information-embedding system for this case based on nested linear codes is constructed having an encoder-decoder that is identical to the decoder-encoder structure for the corresponding system that achieves the Wyner-Ziv rate-distortion limit. Finally, based on these results, a simple layered joint source-channel coding system is developed with a perfectly symmetric encoder-decoder structure. Its application and performance is discussed in a broadcast setting in which there is a need to control the fidelity experienced by different receivers. Among other results, we show that such systems and their multilayer extensions retain attractive optimality properties in the Gaussian-quadratic case, but not in the binary-Hamming case.
9470216
Quantization index modulation: A class of provably good methods for digital watermarking and information embedding
We consider the problem of embedding one signal (e.g., a digital watermark), within another "host" signal to form a third, "composite" signal. The embedding is designed to achieve efficient tradeoffs among the three conflicting goals of maximizing the information-embedding rate, minimizing the distortion between the host signal and composite signal, and maximizing the robustness of the embedding. We introduce new classes of embedding methods, termed quantization index modulation (QIM) and distortion-compensated QIM (DC-QIM), and develop convenient realizations in the form of what we refer to as dither modulation. Using deterministic models to evaluate digital watermarking methods, we show that QIM is "provably good" against arbitrary bounded and fully informed attacks, which arise in several copyright applications, and in particular it achieves provably better rate distortion-robustness tradeoffs than currently popular spread-spectrum and low-bit(s) modulation methods. Furthermore, we show that for some important classes of probabilistic models, DC-QIM is optimal (capacity-achieving) and regular QIM is near-optimal. These include both additive white Gaussian noise (AWGN) channels, which may be good models for hybrid transmission applications such as digital audio broadcasting, and mean-square-error-constrained attack channels that model private-key watermarking applications.