Efficient Algorithms for Combinatorial Auctions with Volume Discounts Arising in Web Service Composition

Web services are now a key ingredient of software services offered by software enterprises. Many standardized web services are now available as commodity offerings from web service providers. An important problem for a web service requester is the web service composition problem which involves selecting the right mix of web service offerings to execute an end-to-end business process. Web service offerings are now available in bundled form as composite web services and more recently, volume discounts are also on offer, based on the number of executions of web services requested. In this paper, we develop efficient algorithms for the web service composition problem in the presence of composite web service offerings and volume discounts. We model this problem as a combinatorial auction with volume discounts. We first develop efficient polynomial time algorithms when the end-to-end service involves a linear workflow of web services. Next we develop efficient polynomial time algorithms when the end-to-end service involves a tree workflow of web services.

A Combinatorial Family of Near Regular LDPC Codes

An elementary combinatorial Tanner graph construction for a family of near-regular low density parity check (LDPC) codes achieving high girth is presented. These codes are near regular in the sense that the degree of a left/right vertex is allowed to differ by at most one from the average. The construction yields in quadratic time complexity an asymptotic code family with provable lower bounds on the rate and the girth for a given choice of block length and average degree. The construction gives flexibility in the choice of design parameters of the code like rate, girth and average degree. Performance simulations of iterative decoding algorithm for the AWGN channel on codes designed using the method demonstrate that these codes perform better than regular PEG codes and MacKay codes of similar length for all values of Signal to noise ratio.

Combinatorial Representations of Block Codes

We look at graphical descriptions of block codes known as trellises, which illustrate connections between algebra and graph theory, and can be used to develop powerful decoding algorithms. Trellis sizes for linear block codes are known to grow exponentially with the code parameters. Of considerable interest to coding theorists therefore, are more compact descriptions called tail-biting trellises which in some cases can be much smaller than any conventional trellis for the same code . We derive some interesting properties of tail-biting trellises and present a new decoding algorithm.

Renewable energy and energy conservation technologies

Energy systems should be consistent with environmental, economic and social sustainability in order to ensure regional sustainable development. This enhances both current and future potential to meet the human needs and aspirations. Sustainable development, a process of change, in which, the exploitation of resources, the direction of investments , the orientation of technological development and institutional change are in harmony. National energy programme should prioritize the development of renewable energy sources, which offer the potentially huge sources of primary energy. The path for sustainability in the next millennium is the low energy path through wise use of energy. Energy conservation and energy efficiency measures would certainly result in meeting the energy demand with as little as half the primary supply at current levels. This requires profound structural changes in socio-economic and institutional arrangements. Environmentally sound, technically and economically viable energy pathways will sustain human progress in the long term future giving a fair and equitable share of the underprivileged and poor of the developing countries. Renewable energy is considered by some as the only hope for the survival of planet yet by others it is viewed as a marginal resource with limited resource. All too often, however, the facts behind the role that renewable energy can, and will, play in the regional energy scene are disguised or ignored as rival camps distort the evidence to suit their own objectives. It was in the light of this confusion that the Energy Research Group at Centre for Ecological Sciences, Indian Institute of Science undertook investigation in Kolar and Uttara Kannada Districts in Karnataka State, India to identify the potential contribution of several types of renewable energy sources: Solar, Wind, Hydro, Bioenergy, etc.

Combining indentation and diffusion couple techniques for combinatorial discovery of high temperature shape memory alloys

We demonstrate the possibility of accelerated identification of potential compositions for high-temperature shape memory alloys (SMAs) through a combinatorial material synthesis and analysis approach, wherein we employ the combination of diffusion couple and indentation techniques. The former was utilized to generate smooth and compositionally graded inter-diffusion zones (IDZs) in the Ni-Ti-Pd ternary alloy system of varying IDZ thickness, depending on the annealing time at high temperature. The IDZs thus produced were then impressed with an indenter with a spherical tip so as to inscribe a predetermined indentation strain. Subsequent annealing of the indented samples at various elevated temperatures, T-a, ranging between 150 and 550 degrees C allows for partial to full relaxation of the strain imposed due to the shape memory effect. If T-a is above the austenite finish temperature, A(f), the relaxation will be complete. By measuring the depth recovery, which serves as a proxy for the shape recovery characteristic of the SMA, a three-dimensional map in the recovery temperature composition space is constructed. A comparison of the published Af data for different compositions with the Ta data shows good agreement when the depth recovery is between 70% and 80%, indicating that the methodology proposed in this paper can be utilized for the identification of promising compositions. Advantages and further possibilities of this methodology are discussed.

On stellated spheres and a tightness criterion for combinatorial manifolds

We introduce k-stellated spheres and consider the class W-k(d) of triangulated d-manifolds, all of whose vertex links are k-stellated, and its subclass W-k*; (d), consisting of the (k + 1)-neighbourly members of W-k(d). We introduce the mu-vector of any simplicial complex and show that, in the case of 2-neighbourly simplicial complexes, the mu-vector dominates the vector of Betti numbers componentwise; the two vectors are equal precisely for tight simplicial complexes. We are able to estimate/compute certain alternating sums of the components of the mu-vector of any 2-neighbourly member of W-k(d) for d >= 2k. As a consequence of this theory, we prove a lower bound theorem for such triangulated manifolds, and we determine the integral homology type of members of W-k*(d) for d >= 2k + 2. As another application, we prove that, when d not equal 2k + 1, all members of W-k*(d) are tight. We also characterize the tight members of W-k*(2k + 1) in terms of their kth Betti numbers. These results more or less answer a recent question of Effenberger, and also provide a uniform and conceptual tightness proof for all except two of the known tight triangulated manifolds. We also prove a lower bound theorem for homology manifolds in which the members of W-1(d) provide the equality case. This generalizes a result (the d = 4 case) due to Walkup and Kuhnel. As a consequence, it is shown that every tight member of W-1 (d) is strongly minimal, thus providing substantial evidence in favour of a conjecture of Kuhnel and Lutz asserting that tight homology manifolds should be strongly minimal. (C) 2013 Elsevier Ltd. All rights reserved.

Combinatorial Exploration of the Structural Landscape of Acid-Pyridine Cocrystals

The structural landscape of acid-pyridine cocrystals is explored by adopting a combinatorial matrix method with 4-substituted benzoic acids and 4-substituted pyridines. The choice of the system restricts the primary synthon to the robust acid-pyridine entity. This methodology accordingly provides hints toward the formation of secondary synthons. The pK(a) rule is validated in the landscape by taking all components of the matrix together and exploring it as a whole. Along with the global features, the exploration of landscapes reveals some local features. Apart from the identification of secondary synthons, it also sheds light on the propensity of hydration in cocrystals, synthon competition, and certain topological similarities. The method described here combines two approaches, namely, database analysis and high throughput crystallography, to extract more information with minimal extra experimental effort.

Combinatorial effect of rolling and carbonaceous nanoparticles on the evolution of crystallographic texture and structural properties of ultra high molecular weight polyethylene

Ultra high molecular weight polyethylene (PE) is a structural polymer widely used in biomedical implants. The mechanical properties of PE can be improved either by controlled crystalline orientation (texture) or by the addition of reinforcing agents. However, the combinatorial effect has not received much attention. The objective of this study was to characterize the structure and mechanical properties of PE composites incorporating multiwall carbon nanotubes (MWCNT) and reduced graphene oxide (RGO) subjected to hot rolling. The wide angle X-ray diffraction studies revealed that mechanical deformation resulted in a mixture of orthorhombic and monoclinic crystals. Furthermore, the presence of nanoparticles resulted in lower crystallinity in PE with smaller crystallite size, more so in RGO than in MWCNT composites. Rolling strengthened the texture of both orthorhombic and the monoclinic phases in PE. Presence of RGO weakened the texture of both phases of PE after rolling whereas MWCNT only mildly weakened the texture. This resulted in a reduction in the elastic modulus of RGO composites whereas moduli of neat polymer and the MWCNT composite increased after rolling. This study provides new insight into the role of nanoparticles in texture evolution during polymer processing with implications for processing of structural polymer composites.

Combinatorial Approach to Develop Tailored Biodegradable Poly(xylitol dicarboxylate) Polyesters

The objective of this work was to develop a versatile strategy for preparing biodegradable polymers with tunable properties for biomedical applications. A family of xylitol-based cross-linked polyesters was synthesized by melt condensation. The effect of systematic variation of chain length of the diacid, stoichiometric ratio, and postpolymerization curing time on the physicochemical properties was characterized. The degradation rate decreased as the chain length of the diacid increased. The polyesters synthesized by this approach possess a diverse spectrum of degradation (ranging from similar to 4 to 100% degradation in 7 days), mechanical strength (from 0.5 to similar to 15 MPa) and controlled release properties. The degradation was a first-order process and the rate constant of degradation decreased linearly as the hydrophobicity of the polyester increased. In controlled release studies, the order of diffusion increased with chain length and curing time. The polymers were found to be cytocompatible and are thus suitable for possible use as biodegradable polymers. This work demonstrates that this particular combinatorial approach to polymer synthesis can be used to prepare biomaterials with independently tunable properties.