Maximum matching in a convex bipartite graph

A special matching problem arising in industry is shown to be solvable by an algorithm of the form: match objects a_i and b_j if they satisfy a local optirnality criterion based on a ranking of currently unmatched objects. When no a_i and b_i remain that can be matched, the largest number of acceptable matches has been found.     

Efficient sequential decision‐making algorithms for container inspection operations

Following work of Stroud and Saeger (Proceedings of ISI, Springer Verlag, New York, 2006) and Anand et al. (Proceedings of Computer, Communication and Control Technologies, 2003), we formulate a port of entry inspection sequencing task as a problem of finding an optimal binary decision tree for an appropriate Boolean decision function. We report on new algorithms for finding such optimal trees that are more efficient computationally than those presented by Stroud and Saeger and Anand et al. We achieve these efficiencies through a combination of specific numerical methods for finding optimal thresholds for sensor functions and two novel binary decision tree search algorithms that operate on a space of potentially acceptable binary decision trees. The improvements enable us to analyze substantially larger applications than was previously possible. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

A NEW STANDARD FOR PREEMPTIVE MILITARY ACTION AGAINST WMD THREATS

International law clearly requires an imminent threat of attack as a justification for the preemptive use of military force. However, the standard definition of an imminent threat was derived centuries before the development of nuclear, chemical, or biological weapons or ballistic missiles and other delivery systems that can reach their targets in a matter of minutes. Any use of force to alleviate threats posed by weapons of mass destruction (WMD) prior to tactical warning of the actual launch of such weapons falls into the legally and ethically controversial category of “anticipatory self-defense,” leaving decision makers potentially liable to prosecution for war crimes. Effective and ethical enforcement of nonproliferation therefore demands a standard for imminence of threat broad enough to allow military action as a last resort but sufficiently restrictive to prohibit indiscriminate action against suspected WMD programs. Following a critical review of selected literature and cases on preemption, the author proposes a new standard for preemptive military action: the existence of operational WMD, or a clandestine program to develop WMD, in contravention of international law. The author discusses the implications of this new proposed standard, which at the time of writing would permit preemptive attack against WMD-armed terrorist groups but prohibit it against all states except Iran and possibly North Korea.     

Finding equivalent transportation formulations for constrained transportation problems

This paper describes a procedure for determining if constrained transportation problems (i.e., transportation problems with additional linear constraints) can be transformed into equivalent pure transportation problems by a linear transformation involving the node constraints and the extra constraints. Our results extend procedures for problems in which the extra constraints consist of bounding certain partial sums of variables.     

Inequalities for mixed integer programs with structure

Mixed integer programming problems arising in practice often contain special structures such as imbedded networks and multiple choice constraints. Easily derived inequalities are given that can be used to reduce the range of admissible solutions for such problems.