Design of an optimal auction for sponsored search auctions

In this paper we first describe a framework to model the sponsored search auction on the web as a mechanism design problem. Using this framework, we design a novel auction which we call the OPT (optimal) auction. The OPT mechanism maximizes the search engine's expected revenue while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We show that the OPT mechanism is superior to two of the most commonly used mechanisms for sponsored search namely (1) GSP (Generalized Second Price) and (2) VCG (Vickrey-Clarke-Groves). We then show an important revenue equivalence result that the expected revenue earned by the search engine is the same for all the three mechanisms provided the advertisers are symmetric and the number of sponsored slots is strictly less than the number of advertisers.

Optimal Nonlinear Control and Estimation for a Reusable Launch Vehicle During Reentry Phase

In this paper a nonlinear optimal controller has been designed for aerodynamic control during the reentry phase of the Reusable Launch Vehicle (RLV). The controller has been designed based on a recently developed technique Optimal Dynamic Inversion (ODI). For full state feedback the controller has required full information about the system states. In this work an Extended Kalman filter (EKF) is developed to estimate the states. The vehicle (RLV) has been has been consider as a nonlinear Six-Degree-Of-Freedom (6-DOF) model. The simulation results shows that EKF gives a very good estimation of the states and it is working well with ODI. The resultant trajectories are very similar to those obtained by perfect state feedback using ODI only.

Optimal resource allocation in conflicts with the Lanchester linear law (2,1) model

This paper presents a detailed analysis of a model for military conflicts where the defending forces have to determine an optimal partitioning of available resources to counter attacks from an adversary in two different fronts in an area fire situation. Lanchester linear law attrition model is used to develop the dynamical equations governing the variation in force strength. Here we address a static resource allocation problem namely, Time-Zero-Allocation (TZA) where the resource allocation is done only at the initial time. Numerical examples are given to support the analytical results.

Optimal sleep-wake scheduling for quickest intrusion detection using sensor networks

We consider the problem of quickest detection of an intrusion using a sensor network, keeping only a minimal number of sensors active. By using a minimal number of sensor devices, we ensure that the energy expenditure for sensing, computation and communication is minimized (and the lifetime of the network is maximized). We model the intrusion detection (or change detection) problem as a Markov decision process (MDP). Based on the theory of MDP, we develop the following closed loop sleep/wake scheduling algorithms: (1) optimal control of Mk+1, the number of sensors in the wake state in time slot k + 1, (2) optimal control of qk+1, the probability of a sensor in the wake state in time slot k + 1, and an open loop sleep/wake scheduling algorithm which (3) computes q, the optimal probability of a sensor in the wake state (which does not vary with time), based on the sensor observations obtained until time slot k. Our results show that an optimum closed loop control on Mk+1 significantly decreases the cost compared to keeping any number of sensors active all the time. Also, among the three algorithms described, we observe that the total cost is minimum for the optimum control on Mk+1 and is maximum for the optimum open loop control on q.

Quantitative photoacoustic tomography from boundary pressure measurements: noniterative recovery of optical absorption coefficient from the reconstructed absorbed energy map

We describe a noniterative method for recovering optical absorption coefficient distribution from the absorbed energy map reconstructed using simulated and noisy boundary pressure measurements. The source reconstruction problem is first solved for the absorbed energy map corresponding to single- and multiple-source illuminations from the side of the imaging plane. It is shown that the absorbed energy map and the absorption coefficient distribution, recovered from the single-source illumination with a large variation in photon flux distribution, have signal-to-noise ratios comparable to those of the reconstructed parameters from a more uniform photon density distribution corresponding to multiple-source illuminations. The absorbed energy map is input as absorption coefficient times photon flux in the time-independent diffusion equation (DE) governing photon transport to recover the photon flux in a single step. The recovered photon flux is used to compute the optical absorption coefficient distribution from the absorbed energy map. In the absence of experimental data, we obtain the boundary measurements through Monte Carlo simulations, and we attempt to address the possible limitations of the DE model in the overall reconstruction procedure.

Optimal configurations of active fiber composites based on asymptotic torsional analysis - art. no. 641413

Active Fiber Composites (AFC) possess desirable characteristics over a wide range of smart structure applications, such as vibration, shape and flow control as well as structural health monitoring. This type of material, capable of collocated actuation and sensing, call be used in smart structures with self-sensing circuits. This paper proposes four novel applications of AFC structures undergoing torsion: sensors and actuators shaped as strips and tubes; and concludes with a preliminary failure analysis. To enable this, a powerful mathematical technique, the Variational Asymptotic Method (VAM) was used to perform cross-sectional analyses of thin generally anisotropic AFC beams. The resulting closed form expressions have been utilized in the applications presented herein.

Optimal auctions for multi-unit procurement with volume discount bids

Our attention, is focused on designing an optimal procurement mechanism which a buyer can use for procuring multiple units of a homogeneous item based on bids submitted by autonomous, rational, and intelligent suppliers. We design elegant optimal procurement mechanisms for two different situations. In the first situation, each supplier specifies the maximum quantity that can be supplied together with a per unit price. For this situation, we design an optimal mechanism S-OPT (Optimal with Simple bids). In the more generalized case, each supplier specifies discounts based on the volume of supply. In this case, we design an optimal mechanism VD-OPT (Optimal with Volume Discount, bids). The VD-OPT mechanism uses the S-OPT mechanism as a building block. The proposed mechanisms minimize the cost to the buyer, satisfying at the same time, (a) Bayesian, incentive compatibility and (b) interim individual rationality.

Optimal Reservoir Operation for Flood Control Using Folded Dynamic Programming

Folded Dynamic Programming (FDP) is adopted for developing optimalnreservoir operation policies for flood control. It is applied to a case study of Hirakud Reservoir in Mahanadi basin, India with the objective of deriving optimal policy for flood control. The river flows down to Naraj, the head of delta where a major city is located and finally joins the Bay of Bengal. As Hirakud reservoir is on the upstream side of delta area in the basin, it plays an important role in alleviating the severity of the flood for this area. Data of 68 floods such as peaks of inflow hydrograph, peak of outflow from reservoir during each flood, peak of flow hydrograph at Naraj and d/s catchment contribution are utilized. The combinations of 51, 54, 57 thousand cumecs as peak inflow into reservoir and 25.5, 20, 14 thousand cumecs respectively as,peak d/s catchment contribution form the critical combinations for flood situation. It is observed that the combination of 57 thousand cumecs of inflow into reservoir and 14 thousand cumecs for d/s catchment contribution is the most critical among the critical combinations of flow series. The method proposed can be extended to similar situations for deriving reservoir operating policies for flood control.

Resource recovery potential from secondary components of segregated municipal solid wastes

Fermentable components of municipal solid wastes (MSW) such as fruit and vegetable wastes (FVW), leaf litter, paddy straw, cane bagasse, cane trash and paper are generated in large quantities at various pockets of the city. These form potential feedstocks for decentralized biogas plants to be operated in the vicinity. We characterized the fermentation potential of six of the above MSW fractions for their suitability to be converted to biogas and anaerobic compost using the solid-state stratified bed (SSB) process in a laboratory study. FVW and leaf litter (papermulberry leaves) decomposed almost completely while paddy straw, sugarcane trash, sugarcane bagasse and photocopying paper decomposed to a lower extent. In the SSB process between 50-60% of the biological methane potential (BMP) could be realized. Observations revealed that the SSB process needs to be adapted differently for each of the feedstocks to obtain a higher gas recovery. Bagasse produced the largest fraction of anaerobic compost (fermentation residue) and has the potential for reuse in many ways.

A model based factorization approach for dense 3D recovery from monocular video

Feature track matrix factorization based methods have been attractive solutions to the Structure-front-motion (Sfnl) problem. Group motion of the feature points is analyzed to get the 3D information. It is well known that the factorization formulations give rise to rank deficient system of equations. Even when enough constraints exist, the extracted models are sparse due the unavailability of pixel level tracks. Pixel level tracking of 3D surfaces is a difficult problem, particularly when the surface has very little texture as in a human face. Only sparsely located feature points can be tracked and tracking error arc inevitable along rotating lose texture surfaces. However, the 3D models of an object class lie in a subspace of the set of all possible 3D models. We propose a novel solution to the Structure-from-motion problem which utilizes the high-resolution 3D obtained from range scanner to compute a basis for this desired subspace. Adding subspace constraints during factorization also facilitates removal of tracking noise which causes distortions outside the subspace. We demonstrate the effectiveness of our formulation by extracting dense 3D structure of a human face and comparing it with a well known Structure-front-motion algorithm due to Brand.

A unified construction of space-time codes with optimal rate-diversity tradeoff

The problem of constructing space-time (ST) block codes over a fixed, desired signal constellation is considered. In this situation, there is a tradeoff between the transmission rate as measured in constellation symbols per channel use and the transmit diversity gain achieved by the code. The transmit diversity is a measure of the rate of polynomial decay of pairwise error probability of the code with increase in the signal-to-noise ratio (SNR). In the setting of a quasi-static channel model, let n(t) denote the number of transmit antennas and T the block interval. For any n(t) <= T, a unified construction of (n(t) x T) ST codes is provided here, for a class of signal constellations that includes the familiar pulse-amplitude (PAM), quadrature-amplitude (QAM), and 2(K)-ary phase-shift-keying (PSK) modulations as special cases. The construction is optimal as measured by the rate-diversity tradeoff and can achieve any given integer point on the rate-diversity tradeoff curve. An estimate of the coding gain realized is given. Other results presented here include i) an extension of the optimal unified construction to the multiple fading block case, ii) a version of the optimal unified construction in which the underlying binary block codes are replaced by trellis codes, iii) the providing of a linear dispersion form for the underlying binary block codes, iv) a Gray-mapped version of the unified construction, and v) a generalization of construction of the S-ary case corresponding to constellations of size S-K. Items ii) and iii) are aimed at simplifying the decoding of this class of ST codes.

Optimal multicommodity flow through the complete graph with random edge capacities

We consider a multicommodity flow problem on a complete graph whose edges have random, independent, and identically distributed capacities. We show that, as the number of nodes tends to infinity, the maximumutility, given by the average of a concave function of each commodity How, has an almost-sure limit. Furthermore, the asymptotically optimal flow uses only direct and two-hop paths, and can be obtained in a distributed manner.

Interactions of linear dicationic molecules with lipid A: structural requisites for optimal binding affinity

The structural determinants of the binding affinity of linear dicationic molecules toward lipid A have been examined with respect to the distance between the terminal cationic functions, the basicity, and the type of cationic moieties using a series of spermidine derivatives and pentamidine analogs by fluorescence spectroscopic methods, The presence of two terminal cationic groups corresponds to enhanced affinity, A distinct sigmoidal relationship between the intercationic distance and affinity was observed with a sharp increase at 11 Angstrom, levelling off at about 13 Angstrom. The basicity (pK) and nature of the cationic functions are poor correlates of binding potency, since molecules bearing primary amino, imidazolino, or guanido termini are equipotent, The interaction of pentamidine, a bisamidine drug, with lipid A, characterized in considerable detail employing the putative intermolecular excimerization of the drug, suggests a stoichiometry of 1:1 in the resultant complex, The binding is driven almost exclusively by electrostatic forces, and is dependent on the ionization states of both lipid A and the drug, Under conditions when lipid A is highly disaggregated, pentamidine binds specifically to bis-phosphoryl- but not to monophosphoryl-lipid A indicating that both phosphate groups of lipid A are necessary for electrostatic interactions by the terminal amidininium groups of the drug, Based on these data, a structural model is proposed for the pentamidine-lipid A complex, which may be of value in designing endotoxin antagonists from first principles.

Optimal Resource Partitioning in a Military Conflict based on Lanchester Attrition Models

This paper develops a model for military conflicts where the defending forces have to determine an optimal partitioning of available resources to counter attacks from an adversary in two different fronts. The Lanchester attrition model is used to develop the dynamical equations governing the variation in force strength. Three different allocation schemes - Time-Zero-Allocation (TZA), Allocate-Assess-Reallocate (AAR), and Continuous Constant Allocation (CCA) - are considered and the optimal solutions are obtained in each case. Numerical examples are given to support the analytical results.

Delay optimal control algorithm for a multiaccess fading channel with peak power constraint

We consider an optimal power and rate scheduling problem for a multiaccess fading wireless channel with the objective of minimising a weighted sum of mean packet transmission delay subject to a peak power constraint. The base station acts as a controller which, depending upon the buffer lengths and the channel state of each user, allocates transmission rate and power to individual users. We assume perfect channel state information at the transmitter and the receiver. We also assume a Markov model for the fading and packet arrival processes. The policy obtained represents a form of Indexability.