A winner determination algorithm for multi-unit combinatorial auctions with reserve prices

Combinatorial auction mechanisms have been used in many applications such as resource and task allocation, planning and time scheduling in multi-agent systems, in which the items to be allocated are complementary or substitutable. The winner determination in combinatorial auction itself is a NP-complete problem, and has attracted many attentions of researchers world wide. Some outstanding achievements have been made including CPLEX and CABOB algorithms on this topic. To our knowledge, the research into multi-unit combinatorial auctions with reserve prices considered is more or less ignored. To this end, we present a new algorithm for multi-unit combinatorial auctions with reserve prices, which is based on Sandholm's work. An efficient heuristic function is developed for the new algorithm. Experiments have been conducted. The experimental results show that auctioneer agent can find the optimal solution efficiently for a reasonable problem scale with our algorithm.

GRASP with Hybrid Path Relinking for Bi-Objective Winner Determination in Combinatorial Transportation Auctions

The procurement of transportation services via large-scale combinatorial auctions involves a couple of complex decisions whose outcome highly influences the performance of the tender process. This paper examines the shipper's task of selecting a subset of the submitted bids which efficiently trades off total procurement cost against expected carrier performance. To solve this bi-objective winner determination problem, we propose a Pareto-based greedy randomized adaptive search procedure (GRASP). As a post-optimizer we use a path relinking procedure which is hybridized with branch-and-bound. Several variants of this algorithm are evaluated by means of artificial test instances which comply with important real-world characteristics. The two best variants prove superior to a previously published Pareto-based evolutionary algorithm.

A new ambiguity acceptance test threshold determination method with controllable failure rate

The ambiguity acceptance test is an important quality control procedure in high precision GNSS data processing. Although the ambiguity acceptance test methods have been extensively investigated, its threshold determine method is still not well understood. Currently, the threshold is determined with the empirical approach or the fixed failure rate (FF-) approach. The empirical approach is simple but lacking in theoretical basis, while the FF-approach is theoretical rigorous but computationally demanding. Hence, the key of the threshold determination problem is how to efficiently determine the threshold in a reasonable way. In this study, a new threshold determination method named threshold function method is proposed to reduce the complexity of the FF-approach. The threshold function method simplifies the FF-approach by a modeling procedure and an approximation procedure. The modeling procedure uses a rational function model to describe the relationship between the FF-difference test threshold and the integer least-squares (ILS) success rate. The approximation procedure replaces the ILS success rate with the easy-to-calculate integer bootstrapping (IB) success rate. Corresponding modeling error and approximation error are analysed with simulation data to avoid nuisance biases and unrealistic stochastic model impact. The results indicate the proposed method can greatly simplify the FF-approach without introducing significant modeling error. The threshold function method makes the fixed failure rate threshold determination method feasible for real-time applications.

A truthful double auction for device-to-device communications in cellular networks

Data traffic in cellular networks has dramatically increased in recent years as the emergence of various new wireless applications, which imposes an immediate requirement for large network capacity. Although many efforts have been made to enhance wireless channel capacity, they are far from solving the network capacity enhancement problem. Device-to-Device (D2D) communication is recently proposed as a promising technique to increase network capacity. However, most existing work on D2D communications focuses on optimizing throughput or energy efficiency, without considering economic issues. In this paper, we propose a truthful double auction for D2D communications (TAD) in multi-cell cellular networks for trading resources in frequencytime domain, where cellular users with D2D communication capability act as sellers, and other users waiting to access the network act as buyers. Both intra-cell and inter-cell D2D sellers are accommodated in TAD while the competitive space in each cell is extensively exploited to achieve a high auction efficiency. With a sophisticated seller-buyer matching, winner determination and pricing, TAD guarantees individual rationality, budget balance, and truthfulness. Furthermore, we extend our TAD design to handle a more general case that each seller and buyer ask/bid multiple resource units. Extensive simulation results show that TAD can achieve truthfulness as well as high performance in terms of seller/buyer sanctification ratio, auctioneer profit and network throughput.

A new approach to the design of electronic exchanges

Electronic Exchanges are double-sided marketplaces that allows multiple buyers to trade with multiple sellers, with aggregation of demand and supply across the bids to maximize the revenue in the market. In this paper, we propose a new design approach for an one-shot exchange that collects bids from buyers and sellers and clears the market at the end of the bidding period. The main principle of the approach is to decouple the allocation from pricing. It is well known that it is impossible for an exchange with voluntary participation to be efficient and budget-balanced. Budget-balance is a mandatory requirement for an exchange to operate in profit. Our approach is to allocate the trade to maximize the reported values of the agents. The pricing is posed as payoff determination problem that distributes the total payoff fairly to all agents with budget-balance imposed as a constraint. We devise an arbitration scheme by axiomatic approach to solve the payoff determination problem using the added-value concept of game theory.

Advanced graph mining methods for protein analysis

As one of the primary substances in a living organism, protein defines the character of each cell by interacting with the cellular environment to promote the cell’s growth and function [1]. Previous studies on proteomics indicate that the functions of different proteins could be assigned based upon protein structures [2,3]. The knowledge on protein structures gives us an overview of protein fold space and is helpful for the understanding of the evolutionary principles behind structure. By observing the architectures and topologies of the protein families, biological processes can be investigated more directly with much higher resolution and finer detail. For this reason, the analysis of protein, its structure and the interaction with the other materials is emerging as an important problem in bioinformatics. However, the determination of protein structures is experimentally expensive and time consuming, this makes scientists largely dependent on sequence rather than more general structure to infer the function of the protein at the present time. For this reason, data mining technology is introduced into this area to provide more efficient data processing and knowledge discovery approaches.

Unlike many data mining applications which lack available data, the protein structure determination problem and its interaction study, on the contrary, could utilize a vast amount of biologically relevant information on protein and its interaction, such as the protein data bank (PDB) [4], the structural classification of proteins (SCOP) databases [5], CATH databases [6], UniProt [7], and others. The difficulty of predicting protein structures, specially its 3D structures, and the interactions between proteins as shown in Figure 6.1, lies in the computational complexity of the data. Although a large number of approaches have been developed to determine the protein structures such as ab initio modelling [8], homology modelling [9] and threading [10], more efficient and reliable methods are still greatly needed.

In this chapter, we will introduce a state-of-the-art data mining technique, graph mining, which is good at defining and discovering interesting structural patterns in graphical data sets, and take advantage of its expressive power to study protein structures, including protein structure prediction and comparison, and protein-protein interaction (PPI). The current graph pattern mining methods will be described, and typical algorithms will be presented, together with their applications in the protein structure analysis.

The rest of the chapter is organized as follows: Section 6.2 will give a brief introduction of the fundamental knowledge of protein, the publicly accessible protein data resources and the current research status of protein analysis; in Section 6.3, we will pay attention to one of the state-of-the-art data mining methods, graph mining; then Section 6.4 surveys several existing work for protein structure analysis using advanced graph mining methods in the recent decade; finally, in Section 6.5, a conclusion with potential further work will be summarized.

Efficient computation of current collection in bare electrodynamic tethers in and beyond OML regime

One key issue in the simulation of bare electrodynamic tethers (EDTs) is the accurate and fast computation of the collected current, an ambient dependent operation necessary to determine the Lorentz force for each time step. This paper introduces a novel semianalytical solution that allows researchers to compute the current distribution along the tether efficient and effectively under orbital-motion-limited (OML) and beyond OML conditions, i.e., if tether radius is greater than a certain ambient dependent threshold. The method reduces the original boundary value problem to a couple of nonlinear equations. If certain dimensionless variables are used, the beyond OML effect just makes the tether characteristic length L ∗ larger and it is decoupled from the current determination problem. A validation of the results and a comparison of the performance in terms of the time consumed is provided, with respect to a previous ad hoc solution and a conventional shooting method.

The winner takes it all? Characteristics of adolescents at-risk/problem gamblers in Switzerland

Background: Gambling has and still entertains people in almost all societies throughout the world. Western societies have faced considerable changes in the amount and accessibility of gambling possibilities during the last decades, and the rates of both adolescent gamblers and problem gamblers have increased significantly. Objective: To determine the characteristics of at-risk and problem adolescent gamblers in Switzerland. Subjects: The study population consisted of 3134 students (1669 females) attending post-mandatory education in 15 randomly chosen centres. Participants were divided into non- (n=2207), non-problematic (n=754) and at-risk/ problematic gamblers (n=176). Methods: Both gambling groups were compared to non-gamblers on socio-demographic measures, substance use and Internet use. Overall, 29.6% had gambled during the past year and 5.6% had gambled in a risky or problematic way. Compared to non-gamblers and after controlling for potential confounders, non-problem gamblers were significantly more likely to be male, apprentices and to misuse alcohol. At-risk/problematic gamblers were additionally more likely to smoke cannabis, to be problematic Internet users and to be non-Swiss than non-gamblers. Conclusion: At-risk and problematic adolescent gambling is associated with other health risk behaviours. Health practitioners should include gambling in the psycho-social screening and preventive counselling of adolescents.

Transportation disadvantage determination framework : space-time organisation measure in determining transportation disadvantage

Transportation disadvantage has been recognised to be the key source of social exclusion. Therefore an appropriate process is required to investigate and seek to resolve this problem. Currently, determination of Transportation Disadvantage is postulate based on income, poverty and mobility level. Transportation disadvantage may best regard be based on accessibility perspectives as they represent inability of the individual to access desired activities. This paper attempts to justify a process in determining transportation disadvantage by incorporating accessibility and social transporation conflict as the essence of a framework. The framework embeds space time organisation within the dimension of accessibility to identify a rigorous definition of transportation disadvantage. In developing the framework, the definition, dimension, component and measure of accessibility were scrutinised. The findings suggest the definition and dimension are the significant approach of research to evaluate travel experience of the disadvantaged. Concurrently, location accessibility measures will be incorprated to strenghten the determination of accessibility level. Literature review in social exclusion and mobility-related exclusion identified the dimension and source of transportation disadvantage. It was revealed that the appropriate approach to justify trasnportation disadvantaged is to incorporate space-time organisation within the studied components. The suggested framework is an inter-related process consisting of component of accessibility; individual, networking (transport system) and activities (destination). The integration and correlation among the components shall determine the level of transportation disadvantage. Prior findings are used to retrieve the spatial distribution of transportation disadvantaged and appropriate policies are developed to resolve the problems.

On the statistical determination of optimal camera configurations in large scale surveillance networks

The selection of optimal camera configurations (camera locations, orientations etc.) for multi-camera networks remains an unsolved problem. Previous approaches largely focus on proposing various objective functions to achieve different tasks. Most of them, however, do not generalize well to large scale networks. To tackle this, we introduce a statistical formulation of the optimal selection of camera configurations as well as propose a Trans-Dimensional Simulated Annealing (TDSA) algorithm to effectively solve the problem. We compare our approach with a state-of-the-art method based on Binary Integer Programming (BIP) and show that our approach offers similar performance on small scale problems. However, we also demonstrate the capability of our approach in dealing with large scale problems and show that our approach produces better results than 2 alternative heuristics designed to deal with the scalability issue of BIP.

Determination of battery storage capacity in energy buffer for wind farm

Design of a battery energy storage system (BESS) in a buffer scheme is examined for the purpose of attenuating the effects of unsteady input power from wind farms. The design problem is formulated as maximization of an objective function that measures the economic benefit obtainable from the dispatched power from the wind farm against the cost of the BESS. Solution to the problem results in the determination of the capacity of the BESS to ensure constant dispatched power to the connected grid, while the voltage level across the dc-link of the buffer is kept within preset limits. A computational procedure to determine the BESS capacity and the evaluation of the dc voltage is shown. Illustrative examples using the proposed design method are included.

A micro-level investigation of the solid displacement method for porosity determination of dried food

Porosity is one of the key parameters of the macroscopic structure of porous media, generally defined as the ratio of the free spaces occupied (by the volume of air) within the material to the total volume of the material. Porosity is determined by measuring skeletal volume and the envelope volume. Solid displacement method is one of the inexpensive and easy methods to determine the envelope volume of a sample with an irregular shape. In this method, generally glass beads are used as a solid due to their uniform size, compactness and fluidity properties. The smaller size of the glass beads means that they enter into the open pores which have a larger diameter than the glass beads. Although extensive research has been carried out on porosity determination using displacement method, no study exists which adequately reports micro-level observation of the sample during measurement. This study set out with the aim of assessing the accuracy of solid displacement method of bulk density measurement of dried foods by micro-level observation. Solid displacement method of porosity determination was conducted using a cylindrical vial (cylindrical plastic container) and 57 µm glass beads in order to measure the bulk density of apple slices at different moisture contents. A scanning electron microscope (SEM), a profilometer and ImageJ software were used to investigate the penetration of glass beads into the surface pores during the determination of the porosity of dried food. A helium pycnometer was used to measure the particle density of the sample. Results show that a significant number of pores were large enough to allow the glass beads to enter into the pores, thereby causing some erroneous results. It was also found that coating the dried sample with appropriate coating material prior to measurement can resolve this problem.

Problems with the coronial determination of ‘suicide’

After over 100 years of constant dissatisfaction with the accuracy of suicide data, this paper suggests that the problem may actually lie with the category of suicide itself. In almost all previous research, ‘suicide’ is taken to be a self-evidently valid category of death, not an object of study in its own right. Instead, the focus in this paper is upon the presupposition that how a social fact like suicide is counted depends upon norms for its governmental regulation, leading to a reciprocal relationship between social norms and statistical norms. Since this relationship is centred almost entirely in the coroner’s office, this paper examines governmental, definitional and categorisational issues relating to how coroners reach findings of suicide. The intention of this paper is to contribute to international debates over how suicide can best be conceptualised and adjudged.

Determination of the optically equivalent model in three-dimensional photoelasticity

Any stressed photoelastic medium can be reduced to an optically equivalent model consisting of a linear retarder, with retardation 1 and principal axis at azimuth 1, and a pure rotator of power 2. The paper describes two simple methods to determine these quantities experimentally. Further, a method is described to overcome the problem of rotational effects in scattered-light investigations. This new method makes use of the experimentally determined characteristic parameters