Design of multiunit electronic exchanges through decomposition

In this paper, we exploit the idea of decomposition to match buyers and sellers in an electronic exchange for trading large volumes of homogeneous goods, where the buyers and sellers specify marginal-decreasing piecewise constant price curves to capture volume discounts. Such exchanges are relevant for automated trading in many e-business applications. The problem of determining winners and Vickrey prices in such exchanges is known to have a worst-case complexity equal to that of as many as (1 + m + n) NP-hard problems, where m is the number of buyers and n is the number of sellers. Our method proposes the overall exchange problem to be solved as two separate and simpler problems: 1) forward auction and 2) reverse auction, which turns out to be generalized knapsack problems. In the proposed approach, we first determine the quantity of units to be traded between the sellers and the buyers using fast heuristics developed by us. Next, we solve a forward auction and a reverse auction using fully polynomial time approximation schemes available in the literature. The proposed approach has worst-case polynomial time complexity. and our experimentation shows that the approach produces good quality solutions to the problem. Note to Practitioners- In recent times, electronic marketplaces have provided an efficient way for businesses and consumers to trade goods and services. The use of innovative mechanisms and algorithms has made it possible to improve the efficiency of electronic marketplaces by enabling optimization of revenues for the marketplace and of utilities for the buyers and sellers. In this paper, we look at single-item, multiunit electronic exchanges. These are electronic marketplaces where buyers submit bids and sellers ask for multiple units of a single item. We allow buyers and sellers to specify volume discounts using suitable functions. Such exchanges are relevant for high-volume business-to-business trading of standard products, such as silicon wafers, very large-scale integrated chips, desktops, telecommunications equipment, commoditized goods, etc. The problem of determining winners and prices in such exchanges is known to involve solving many NP-hard problems. Our paper exploits the familiar idea of decomposition, uses certain algorithms from the literature, and develops two fast heuristics to solve the problem in a near optimal way in worst-case polynomial time.

Macro-economic analysis of forestry options on carbon sequestration in India

The forestry sector provides a number of climate change mitigation options. Apart from this ecological benefit, it has significant social and economic relevance. Implementation of forestry options requires large investments and sustained long-term planning. Thus there is a need for a detailed analysis of forestry options to understand their implications on stock and flow of carbon, required investments, value of forest wealth, contribution to GNP and livelihood, demand management, employment and foreign trade. There is a need to evaluate the additional spending on forestry by analysing the environmental (particularly carbon abatement), social and economic benefits. The biomass needs for India are expected to increase by two to three times by 2020. Depending upon the forest types, ownership patterns and land use patterns, feasible forestry options are identified. It is found among many supply options to be feasible to meet the 'demand based needs' with a mix of management options, species choices and organisational set up. A comparative static framework is used to analyze the macro-economic impacts. Forestry accounts for 1.84% of GNP in India. It is characterized by significant forward industrial linkages and least backward linkage. Forestry generates about 36 million person years of employment annually. India imports Rs. 15 billion worth of forest based materials annually. Implementation of the demand based forestry options can lead to a number of ecological, economic and institutional changes. The notable ones are: enhancement of C stock from 9578 to 17 094 Mt and a net annual C-sequestration from 73 to 149 Mt after accounting for all emissions; a trebling of the output of forestry sector from Rs. 49 billion to Rs. 146 billion annually; an increase in GDP contribution of forestry from Rs. 32 billion to Rs. 105 billion over a period of 35 years; an increase in annual employment level by 23 million person years, emergence of forestry as a net contributor of foreign exchange through trading of forestry products; and an increase in economic value of forest capital stock by Rs. 7260 billion with a cost benefit analysis showing forestry as a profitable option. Implementation of forestry options calls for an understanding of current forest policies and barriers which are analyzed and a number of policy options are suggested. (C) 1997 Elsevier Science B.V.

Modern energy access to all in rural India: An integrated implementation strategy

Expanding energy access to the rural population of India presents a critical challenge for its government. The presence of 364 million people without access to electricity and 726 million who rely on biomass for cooking indicate both the failure of past policies and programs, and the need for a radical redesign of the current system. We propose an integrated implementation framework with recommendations for adopting business principles with innovative institutional, regulatory, financing and delivery mechanisms. The framework entails establishment of rural energy access authorities and energy access funds, both at the national and regional levels, to be empowered with enabling regulatory policies, capital resources and the support of multi-stakeholder partnership. These institutions are expected to design, lead, manage and monitor the rural energy interventions. At the other end, trained entrepreneurs would be expected to establish bioenergy-based micro-enterprises that will produce and distribute energy carriers to rural households at an affordable cost. The ESCOs will function as intermediaries between these enterprises and the international carbon market both in aggregating carbon credits and in trading them under CDM. If implemented, such a program could address the challenges of rural energy empowerment by creating access to modern energy carriers and climate change mitigation. (C) 2011 Elsevier Ltd. All rights reserved.

Fast Likelihood Computation in Speech Recognition using Matrices

Acoustic modeling using mixtures of multivariate Gaussians is the prevalent approach for many speech processing problems. Computing likelihoods against a large set of Gaussians is required as a part of many speech processing systems and it is the computationally dominant phase for Large Vocabulary Continuous Speech Recognition (LVCSR) systems. We express the likelihood computation as a multiplication of matrices representing augmented feature vectors and Gaussian parameters. The computational gain of this approach over traditional methods is by exploiting the structure of these matrices and efficient implementation of their multiplication. In particular, we explore direct low-rank approximation of the Gaussian parameter matrix and indirect derivation of low-rank factors of the Gaussian parameter matrix by optimum approximation of the likelihood matrix. We show that both the methods lead to similar speedups but the latter leads to far lesser impact on the recognition accuracy. Experiments on 1,138 work vocabulary RM1 task and 6,224 word vocabulary TIMIT task using Sphinx 3.7 system show that, for a typical case the matrix multiplication based approach leads to overall speedup of 46 % on RM1 task and 115 % for TIMIT task. Our low-rank approximation methods provide a way for trading off recognition accuracy for a further increase in computational performance extending overall speedups up to 61 % for RM1 and 119 % for TIMIT for an increase of word error rate (WER) from 3.2 to 3.5 % for RM1 and for no increase in WER for TIMIT. We also express pairwise Euclidean distance computation phase in Dynamic Time Warping (DTW) in terms of matrix multiplication leading to saving of approximately of computational operations. In our experiments using efficient implementation of matrix multiplication, this leads to a speedup of 5.6 in computing the pairwise Euclidean distances and overall speedup up to 3.25 for DTW.