Approximation algorithms and hardness results for labeled connectivity problems

Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ℒ:E→ℕ. In addition, each label ℓ∈ℕ has a non-negative cost c(ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I⊆ℕ such that the edge set {e∈E:ℒ(e)∈I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label s – t path problem (MinLP) the goal is to identify an s–t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.     

Approximation algorithms for connected facility location problems

We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c _e for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d _j and a set of facilities F⊆V each has nonnegative opening cost f _i and capacity to serve all client demands. The objective is to open a subset of facilities, say , to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm.     

Approximation hardness of edge dominating set problems

We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, MINIMUM EDGE DOMINATING SET and MINIMUM MAXIMAL MATCHING. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than . The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs. An extended abstract of this paper was accepted at the 14th Annual International Symposium on Algorithms and Computation, ISAAC 2003.     

Approaches to solve the fleet-assignment,aircraft-routing,crew-pairing and crew-rostering problems of a regional carrier

This paper presents the results of a research project funded by a regional carrier operating inter-island services within the Canary Islands (Spain) in addition to services to Morocco and Portugal. It operates between 100 and 150 flights a day using three airline operators. The main scope of the project was to solve fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems on real-world data. The special characteristics of the carrier, flying between 7 am and 11 pm every day, have motivated us to design models and algorithms that are different than the ones addressed in the literature, typically built for large airline companies. This paper shows a solution approach for an integrated fleet-assignment, aircraft-routing and crew-pairing problem covering the flights of a single day. This is a new combinatorial problem that can be considered as a 2-depot vehicle routing problem with driver changes, where the vehicles represent aircrafts and the drivers represent crews. Adapting approaches from the vehicle routing literature, this paper describes a heuristic algorithm based on an integer programming model. In a similar way, this paper also addresses the rostering problem. This problem can be decomposed in smaller problems taking into account operators, bases and crew groups. These problems admit a compact formulation through mixed integer linear programming models which can be tracked by modern general-purpose solvers. This paper illustrates the success of our solution approaches on real-world instances. The airline carrier is currently using these approaches.     

Multistage Models of Carcinogenesis: An Approximation for the Size and Number Distribution of Late-Stage Clones

Multistage models have become the basic paradigm for modeling carcinogenesis. One model, the two-stage model of carcinogenesis, is now routinely used in the analysis of cancer risks from exposure to environmental chemicals. In its most general form, this model has two states, an initiated state and a neoplastic state, which allow for growth of cells via a simple linear birth-death process. In all analyses done with this model, researchers have assumed that tumor incidence is equivalent to the formation of a single neoplastic cell and the growth kinetics in the neoplastic state have been ignored. Some researchers have discussed the impact of this assumption on their analyses, but no formal methods were available for a more rigorous application of the birth-death process. In this paper, an approximation is introduced which allows for the application of growth kinetics in the neoplastic state. The adequacy of the approximation against simulated data is evaluated and methods are developed for implementing the approximation using data on the number and size of neoplastic clones.     

Exact and heuristic algorithms for the circle cutting problem in the manufacturing industry of electric motors

Circular blanks are often cut from silicon steel plates to make stators and rotors of electric motors. The shearing and punching processes are often used to cut the blanks. First a guillotine shear cuts the plate into strips, and then a stamping press cuts the blanks from the strips. The unconstrained circle cutting problem discussed is the problem of cutting from a rectangular plate a number of circular blanks of given diameters and values, so as to maximize the value of blanks cut, where the shearing and punching processes are applied. Two algorithms based on dynamic programming are presented for generating cutting patterns, one is an exact algorithm and the other is a heuristic one. The computational results indicate that the exact algorithm is adequate for small and middle scale problems, the heuristic algorithm is much more time efficient, and can generate cutting patterns close to optimal.     

Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios

We consider the design of a multicommodity flow network, in which point-to-point demands are routed across the network subject to link capacity restrictions. Such a design must build enough capacity and diverse routing paths through the network to ensure that feasible multicommodity flows continue to exist, even when components of the network fail. In this paper, we examine several methodologies to optimally design a minimum-cost survivable network that continues to support a multicommodity flow under any of a given set of failure scenarios, where each failure scenario consists of the simultaneous failure of multiple arcs. We begin by providing a single extensive form mixed-integer programming formulation for this problem, along with a Benders decomposition algorithm as an alternative to the extensive form approach. We next investigate strategies to improve the performance of the algorithm by augmenting the master problem with several valid inequalities such as cover constraints, connectivity constraints, and path constraints. For the smallest instances (eight nodes, 10 origin–destination pairs, and 10 failure scenarios), the Benders implementation consumes only 10% of the time required by the mixed-integer programming formulation, and our best augmentation strategy reduces the solution time by another 50%. For medium- and large-sized instances, the extensive form problem fails to terminate within 2 h on any instance, while our decomposition algorithms provide optimal solutions on all but two problem instances.     

Decision support system for the batching problems of steelmaking and continuous-casting production

This paper investigates two batching problems for steelmaking and continuous-casting (SCC) production in an integrated iron and steel enterprise. The tasks of the problems are to make the decisions as how to consolidate ordered slabs into charges, and then how to group charges into casts. The effective decisions on these batching problems can help to balance the requirements of materials in downstream production lines, improve the customer satisfaction levels, and reduce production costs (including reduction of open ordered slabs, less slabs quality upgrading, reduction of steel-grade changeovers, and reduction of inefficient utilization of tundishes lives). We first formulate the problems as integer-programming models by consider practical constraints and requirements, and then develop the two heuristic algorithms for the corresponding batching problems. By embedding above models and algorithms, we develop decision support system (DSS) software with interactive planning editor. The DSS has been tested by using practical data set collected from the steelmaking plant in Baosteel which is one of the most advanced iron and steel enterprises in China. Computational experiments demonstrate that the models and algorithms developed can generate the satisfactory solutions when they work together with the planning editor in the DSS.     

Disentangling the Influence of Value Predispositions and Risk/Benefit Perceptions on Support for Nanotechnology Among the American Public

Using nanotechnology as a case study, this article explores (1) how people's perceptions of benefits and risks are related to their approval of nanotechnology, (2) which information‐processing factors contribute to public risk/benefit perceptions, and (3) whether individuals’ predispositions (i.e., deference to scientific authority and ideology) may moderate the relationship between cognitive processing and risk perceptions of the technology. Results indicate that benefit perceptions positively affect public support for nanotechnology; perceptions of risk tend to be more influenced by systematic processing than by heuristic cues, whereas both heuristic and systematic processing influence benefit perceptions. People who are more liberal‐minded tend to be more affected by systematic processing when thinking about the benefits of nanotechnology than those who are more conservative. Compared to less deferent individuals, those who are more deferent to scientific authority tend to be less influenced by systematic processing when making judgments about the benefits and risks of nanotechnology. Implications are discussed.     

On the Use of Hierarchical Probabilistic Models for Characterizing and Managing Uncertainty in Risk/Safety Assessment

A general probabilistically-based approach is proposed for both cancer and noncancer risk/safety assessments. The familiar framework of the original ADI/RfD formulation is used, substituting in the numerator a benchmark dose derived from a hierarchical pharmacokinetic/pharmacodynamic model and in the denominator a unitary uncertainty factor derived from a hierarchical animal/average human/sensitive human model. The empirical probability distributions of the numerator and denominator can be combined to produce an empirical human-equivalent distribution for an animal-derived benchmark dose in external-exposure units.