Greedy Approximation Algorithms
Greedy strategy is a simple and natural method in the design of approximation algorithms. This chapter presents greedy approximation algorithms for very broad classes of maximization problems and minimization problems and analyzes their approximation bounds. A number of applications of these greedy approximation algorithms are also described in this chapter. For many applications, the greedy approximation algorithm can achieve the best known approximation bound in a straightforward manner. For some applications, they have different formulations, and the corresponding greedy approximation algorithms have different approximation bounds. In addition, some applications can have better approximation algorithm than the greedy approximation algorithm.

title: Connected Dominating Sets in Wireless Networks with Different Transmission Ranges
abstract: Since there is no fixed infrastructure or centralized management in wireless ad hoc networks, a Connected Dominating Set (CDS) has been proposed to serve as a virtual backbone. The CDS of a graph representing a network has a significant impact on the efficient design of routing protocols in wireless networks. This problem has been studied extensively in Unit Disk Graphs (UDG), in which all nodes have the same transmission ranges. However, in practice, the transmission ranges of all nodes are not necessarily equal. In this paper, we model a network as a disk graph and introduce the CDS problem in disk graphs. We present two efficient approximation algorithms to obtain a minimum CDS. The performance ratio of these algorithms is constant if the ratio of the maximum transmission range over the minimum transmission range in the network is bounded. These algorithms can be implemented as distributed algorithms. Furthermore, we show a size relationship between a maximal independent set and a CDS as well as a bound of the maximum number of independent neighbors of a node in disk graphs. The theoretical analysis and simulation results are also presented to verify our approaches.

title: Improved construction for pooling design
abstract: Pooling design is a mathematical tool with many applications in molecular biology, specially to reduce the number of tests for DNA library screening. In this note, we study construction of pooling design and present an improvement to a recent new construction given by Du et al. ( 2006).

title: A Note on Optical Network with Nonsplitting Nodes
abstract: We study the problem of computing the minimum total weight multicast route in an optical network with both nonsplitting and splitting nodes, and present a simple approximation with performance ratio 3, which is better than existing one in the literature.

title: A Real-Time Network Traffic Profiling System
abstract: This paper presents the design and implementation of a real-time behavior profiling system for high-speed Internet links. The profiling system uses flow-level information from continuous packet or flow monitoring systems, and uses data mining and information-theoretic techniques to automatically discover significant events based on the communication patterns of end-hosts. We demonstrate the operational feasibility of the system by implementing it and performing extensive benchmarking of CPU and memory costs using a variety of packet traces from OC-48 links in an Internet backbone network. To improve the robustness of this system against sudden traffic surges such as those caused by denial of service attacks or worm outbreaks, we propose a simple yet effective filtering algorithm. The proposed algorithm successfully reduces the CPU and memory cost while maintaining high profiling accuracy.

title: Optimization scheme for sensor coverage scheduling with bandwidth constraints
abstract: Wireless Sensor Network has attracted a lot of attentions due to its broad applications in recent years and also introduces many challenges. Network lifetime is a critical issue in Wireless Sensor Networks. It is possible to extend network lifetime by organizing the sensors into a number of sensor covers. However, with the limited bandwidth, coverage breach (i.e, targets that are not covered) can occur if the number of available time-slots/channels is less than the number of sensors in a sensor cover. In this paper, we study a joint optimization problem in which the objective is to minimize the coverage breach as well as to maximize the network lifetime. We show a “trade-off” scheme by presenting two strongly related models, which aim to tradeoffs between the two conflicting objectives. The main approach of our models is organizing sensors into non-disjoint sets, which is different from the current most popular approach and can gain longer network lifetime as well as less coverage breach. We proposed two algorithms for the first model based on linear programming and greedy techniques, respectively. Then we transform these algorithms to solve the second model by revealing the strong connection between the models. Through numerical simulation, we showed the good performance of our algorithms and the pictures of the tradeoff scheme in variant scenarios, which coincide with theoretical analysis very well. It is also showed that our algorithms could obtain less breach rate than the one proposed in (Cheng et al. in INFOCOM’ 05, 2005).

title: File System Workload Analysis For Large Scientific Computing Applications
abstract: Parallel scientific applications require high-performance I/O support from underlying file systems. A comprehensive understanding of the expected workload is therefore essential for the design of high-performance parallel file systems. We re-examine the workload characteristics in parallel computing environments in the light of recent technology advances and new applications. We analyze application traces from a cluster with hundreds of nodes. On average, each application has only one or two typical request sizes. Large requests from several hundred kilobytes to several megabytes are very common. Although in some applications small requests account for more than 90% of all requests, almost all of the I/O data are transferred by large requests. All of these applications show bursty access patterns. More than 65% of write requests have inter-arrival times within one millisecond in most applications. By running the same benchmark on different file models, we also find that the write throughput of using an individual output file for each node exceeds that of using a shared file for all nodes by a factor of 5. This indicates that current file systems are not well optimized for file sharing.

title: Soft Error Rate Analysis for Combinational Logic Using an Accurate Electrical Masking Model
abstract: Accurate electrical masking modeling represents a significant challenge in soft error rate analysis for combinational logic circuits. In this paper, we use table lookup MOSFET models to accurately capture the nonlinear properties of submicron MOS transistors. Based on these models, we propose and validate the transient pulse generation model and propagation model for soft error rate analysis. The pulse generated by our pulse generation model matches well with that of HSPICE simulation, and the pulse propagation model provides nearly one order of magnitude improvement in accuracy over the previous models. Using these two models, we propose an accurate and efficient block-based soft error rate analysis method for combinational logic circuits.

title: Optimal topology exploration for application-specific 3D architectures
abstract: As technology scales, increasing interconnect costs make it necessary to consider alternate ways of building integrated circuits. One promising option along this direction is 3D architectures where a stack of multiple device layers, with direct vertical tunneling through them, are put together on the same chip. In this paper, we explore how processor cores and storage blocks can be placed in a 3D architecture to minimize data access costs under temperature constraints. This process is referred to as the topology exploration. Using integer linear programming, we compare the best 2D placement with the best 3D placement, and show through experiments with both single-core and multicore systems that the 3D placement generates much better results (in terms of data access costs) under the same temperature bounds. We also discuss the tradeoffs between temperature constraint and data access costs

title: Embedded Multi-Processor System-on-chip (MPSoC) design considering process variations
abstract: As technology scales, the delay uncertainty caused by process variations has become increasingly pronounced in deep sub-micron designs. As a result, a paradigm shift from deterministic to statistical design methodology at all levels of the design hierarchy is inevitable (Borkar, 2005). As part of two NSF projects (NSF CNS CAREER 0643902 and NSF CNS 0720659), a variation-aware task allocation and scheduling method for multiprocessor system-on-chip (MPSoC) architectures is proposed, to mitigate the impact of parameter variations. A new design metric, called performance yield and defined as the probability of the assigned schedule meeting the predefined performance constraints, is used to guide the task allocation and scheduling procedure. An efficient yield computation method for task scheduling complements and significantly improves the effectiveness of the proposed variation-aware scheduling algorithm. Experimental results show that our variation-aware scheduler achieves significant yield improvements.

title: Architecting Microprocessor Components in 3D Design Space
abstract: Interconnect is one of the major concerns in current and future microprocessor designs from both performance and power consumption perspective. The emergence of three-dimensional (3D) chip architectures, with its intrinsic capability to reduce the wire length, is one of the promising solutions to mitigate the interconnect related issues. In this paper we implement a few components of a microprocessor using custom design to show the potential performance and power benefits achievable through 3D integration under thermal constraints. We also introduce a standard cell based 3D design flow which leverages the commercial 2D design tools. Using this design flow we provide performance results of wide range of arithmetic units in 3D, thus introducing a fast method to analyze the performance benefits of 3D designs. In contrast to prior work, which mostly investigates single components of a processor, our work takes multiple components into consideration and the experimental results are promising in terms of delay and power reductions. Complex designs in 3D that have equivalent performance compared to a simple 2D designs is taken for IPC improvement analysis. An IPC improvement of 11% shown for a microprocessor implemented in 2-strata 3D technology