6198667
CABOB: A Fast Optimal Algorithm for Combinatorial Auctions
Combinatorial auctions where bidders can bid on bundles of items can lead to more economical allocations, but determining the winners is NP-complete and inapproximable. We present CABOB, a sophisticated search algorithm for the problem. It uses decomposition techniques, upper and lower bounding (also across components), elaborate and dynamically chosen bid ordering heuristics, and a host of structural observations. Experiments against CPLEX 7.0 show that CABOB is usually faster, never drastically slower, and in many cases drastically faster. We also uncover interesting aspects of the problem itself. First, the problems with short bids that were hard for the first-generation of specialized algorithms are easy. Second, almost all of the CATS distributions are easy, and become easier with more bids. Third, we test a number of random restart strategies, and show that they do not help on this problem because the run-time distribution does not have a heavy tail (at least not for CABOB).
666127
Changing the Game in Strategic Sourcing at Procter & Gamble: Expressive Competition Enabled by Optimization
Procter & Gamble put into practice CombineNets approach to building sourcing networks, called expressive competition. At its heart is a vision that looks past lowest-price reverse auctions and combinatorial package bidding toward a highly expressive commerce relationship with suppliers. It enables suppliers to make electronic offers that express rich forms of capabilities and efficiencies. As the buyer, P&G also uses an expressive language to state constraints and preferences. The detailed expressions of supply and demand are brought together via an advanced optimization engine to decide the optimal allocation of business to the suppliers. By March 2005, over a period of two and a half years, P&G had sourced over 3 billion through expressive commerce and seen 294.8 million (9.6 percent) in recommended savings. In the process, P&Gs suppliers benefited from the win-win approach: expressive competition matched demand to the most efficient means of production (rather than squeezing suppliers profit margins) and removed the exposure risks in making offers. Beyond direct monetary savings, the benefits included the redesign of supply networks with quantitative understanding of the trade-offs and the ability to implement in weeks instead of months.
206967153
Iterative Joint Source-Channel Decoding of H.264 Compressed Video
This paper proposes an iterative joint source-channel decoding (IJSCD) scheme for the transmission of H.264 compressed video over a noisy channel. It uses channel coding along with H.264 semantic verification. The structure, selection of design parameters, and performance of the proposed IJSCD based on a rate-% recursive systematic convolutional (RSC) code over an AWGN channel are described and discussed as an illustrative example. In the example, for the same PSNR, the proposed IJSCD scheme offers a significant saving of 2.1dB in required channel SNR as compared to a system using the same RSC code alone. Furthermore, the performance can be improved by iterative decoding at the cost of increased delay. Hence, a tradeoff can be made between performance improvement and delay
59728652
Practical Grid Computing for Massively Multiplayer Games
14446925
Indexing and Searching XML Documents Based on Content and Structure Synopses
We present a novel framework for indexing and searching schema-less XML documents based on concise summaries of their structural and textual content. Our search query language is XPath extended with full-text search. We introduce two novel data synopsis structures that correlate textual with positional information in an XML document and improves query precision. In addition, we present a two-phase containment filtering algorithm based on these synopses that improves the searching process. Our experimental evaluation shows that our data synopses indexing scheme outperforms the standard XML indexing scheme based on inverted lists; the query evaluation based on our data synopses is more accurate than related approximate approaches that do not consider positional information; our two-phase containment filtering algorithm is more efficient than a single-phase brute force algorithm.
15239156
Application of a hybrid genetic algorithm to airline crew scheduling
This paper discusses the development and application of a hybrid genetic algorithm to airline crew scheduling problems. The hybrid algorithm consists of a steady-state genetic algorithm and a local search heuristic. The hybrid algorithm was tested on a set of 40 real-world problems. It found the optimal solution for half the problems, and good solutions for 9 others. The results were compared to those obtained with branch-and-cut and branch-and-bound algorithms. The branch-and-cut algorithm was significantly more successful than the hybrid algorithm, and the branch-and-bound algorithm slightly better.
13161865
On the Reliability and Additional Overhead of Reliable On-Demand Multicast Routing Protocol for Mobile Ad Hoc Networks
Multicasting is the transmission of datagrams to a group of hosts identified by a single destination address, providing simple and efficient communication for group-oriented applications. Many applications currently envisioned for mobile ad hoc networks require multicasting. Several multicasting protocols have been proposed for mobile ad hoc networks, one of the most popular being the On Demand Multicast Routing Protocol. This paper provides a review of ad hoc multicast routing protocols, focusing on MAODV, ODMRP and a variation of ODMRP called reliable-ODMRP. NS-2 simulations are used to compare the reliability and overhead of MAODV, ODMRP, and R-ODMRP.