Browsing by Author "Cardei, Mihaela"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    A PTAS for the Grade of Service Steiner Minimum Tree Problem
    (2001-12-26) Kim, Joon-Mo; Cardei, Mihaela
    In this paper, we present the design of a PTAS(Polynomial Time Approximation Scheme) for the Grade of Service Steiner Minimum Tree (GOSST) problem, which is known to be NP-Complete. The previous research has focused on geometric analyses and different approximation algorithms were proposed. But having the PTAS, which provides a near-optimal solution, would be the conclusion for an optimization problem. This problem has some important applications. In the Network Design, a fundamental issue for the physical construction of a network structure is the interconnection of many communication sites with the best choice of the connecting lines and the best allocation of the transmission capacities over these lines. Good solutions always provide paths with enough communication capacities between any two sites, with the least network construction costs. GOSST problem also has applications in transportation, for road constructions and some more potential uses in CAD in terms of interconnecting the elements on a plane such that to provide enough flux between any two elements.
  • Thumbnail Image
    Item
    Approximation Solutions for the Resource Management Problem Using the General Cover Problem
    (2001-12-13) Cardei, Mihaela; MacCallum, David; Chen, Sai; Cardei, Ionut; Du, Ding-Zhu
    Time-critical applications and multimedia systems require a mechanism to arbitrate access to shared resources. Resource Management systems provide the necessary services to applications for admission control and adaptation. This paper defines a model for the Resource Management Problemand describes two near-optimal approximation methods for criticality-based selection scheduling of competing applications. The resource management allocation scheme is designed to follow a set of goals. In this paper we focus on maximizing the number of higher-criticality sessions admitted, where a session is an instance of an application executing on a system, using a set of resources, such as CPU, memory and disk IO. First we reduce the Resource Management Problem to the General Cover Problem and thenpresent two approximation solutions with their performance ratio. First solution uses a greedy algorithm and the second one a linear programming algorithm.
  • Thumbnail Image
    Item
    Optimal Relay Location for Resource-Limited Energy-Efficient Wireless Communication
    (2002-03-26) Cardei, Ionut; Cardei, Mihaela; Wang, Lusheng; Xu, Baogang; Du, Ding-Zhu
    In the design of wireless networks, techniques for improving energy efficiency and extending network lifetime have great importance, particularly for defense and civil/rescue applications where resupplying transmitters with new batteries is not feasible. In this paper we study a method for improving the lifetime of wireless networks by minimizing the length of the longest edge in the interconnecting tree with deploying additional relay nodes.Let P={p1, ..., pn} be a set of n terminals in the Euclideanplane. For a positive integer k, the bottleneck Steinertree problem (BSTP) asks to find a Steiner tree with atmost k Steiner points such that the length of the longest edge in the tree is minimized. We give a ratio - sqrt(3) + e polynomial time approximation algorithm for BSTP, where e is an arbitrary positive number.Keywords:wireless networks, power efficient, approximation algorithms, Steiner tree, bottleneck Steiner tree.
  • Thumbnail Image
    Item
    Wireless Sensor Networks with Energy Efficient Organization
    (2002-12-08) Cardei, Mihaela; MacCallum, David; Cheng, Xiaoyan; Min, Manki; Jia, Xiaohua; Li, Deying; Du, Ding-Zhu; Hung-Chang Du, David
    A critical aspect of applications with wireless sensor networks is network lifetime. Battery-powered sensors are usable as long as they can communicate captured data to a processing node. Sensing and communications consume energy, therefore judicious power management and scheduling caneffectively extend the operational time. One important class of wireless sensor applications consists of deployment of large number of sensors in an area for environmental monitoring. The data collected by the sensors is sent to a central node for processing. In this paper we propose an efficient method to achieve energy savings by organizing the sensor nodes into a maximum number of disjoint dominating sets (DDS) which are activated successively. Only the sensors from the active set are responsible for monitoring the target area and for disseminating the collected data. All other nodes are into a sleep mode, characterized by a low energy consumption. We define the maximum disjoint dominating sets problem and we design a heuristic that computes the sets. Theoretical analysis and performance evaluation results are presented to verify our approach.