Algorithms for the minimax transportation problem

In this paper, we consider a variant of the classical transportation problem as well as of the bottleneck transportation problem, which we call the minimax transportation problem. The problem considered is to determine a feasible flow x_ij from a set of origins I to a set of destinations J for which max_(i,j)εIxJ{c_ijx_ij} is minimum. In this paper, we develop a parametric algorithm and a primal-dual algorithm to solve this problem. The parametric algorithm solves a transportation problem with parametric upper bounds and the primal-dual algorithm solves a sequence of related maximum flow problems. The primal-dual algorithm is shown to be polynomially bounded. Numerical investigations with both the algorithms are described in detail. The primal-dual algorithm is found to be computationally superior to the parametric algorithm and it can solve problems up to 1000 origins, 1000 destinations and 10,000 arcs in less than 1 minute on a DEC 10 computer system. The optimum solution of the minimax transportation problem may be noninteger. We also suggest a polynomial algorithm to convert this solution into an integer optimum solution.     

The Fire Within: Naxalite Insurgency Violence in India

India is at a crossroads today. While it is fast emerging as a global power with a vibrant democratic polity, a robust economy and a nuclear-weapons capable military, the country is also witnessing a growing polarisation between the rich and poor and between urban and rural areas, a rise in communal tensions, large numbers of suicides by impoverished and indebted farmers and a spurt in terrorist activities and attacks by various disgruntled organisations and groups. Of these various challenges, as attested to by Prime Minister Manmohan Singh himself, the most dangerous threat to India's territorial integrity, prosperity and wellbeing has come from the Naxalite insurgency or ‘people's war’ that is manifest in large areas of eastern, central and southern India. But what factors account for the formation and persistence of Naxalite insurgency in India? What are the key objectives of the Naxalites and why is violence directed against the Indian State? And how has the Indian State (both central and state governments) responded to the Naxalite insurgency and with what effect? These are the main research questions that we attempt to answer in this paper. We put forward two broad arguments. First, the Naxalite insurgency in India is the latest manifestation of peasant struggles caused by grinding poverty, exploitation and inequality that have prevailed in rural areas for centuries. What sustains these struggles to this day is the fact that socio-economic conditions in rural areas have changed little and the policies followed by the post-independent Indian State have generally failed to mitigate rural problems. Second, the Naxalite insurgency has emerged as the most dangerous threat mainly due to the movement's spatial spread, growing support base in tribal and backward areas and enhanced fighting capabilities. The Indian State has viewed the movement as a ‘law and order’ problem and responded with force. But a ‘law and order’ approach to the Naxalite insurgency is unlikely to produce a lasting resolution of the problem, since it would not effectively redress deep-rooted grievances felt by a majority of India's rural poor for decades.