| 1. |
- Andersson, Arne, et al.
(författare)
-
Fusion trees can be implemented with AC0 instructions.
- 1999
-
Ingår i: Theoretical Computer Science. ; 205, s. 337-344
-
Tidskriftsartikel (refereegranskat)abstract
- Addressing a problem of Fredman and Willard, we implement fusion trees in deterministic linear space using AC^o instructions only. More precisely, we show that a subset of {0,...,2^(w-1)} of size n can be maintained using linear space under insertion, deletion, predecessor, and successor queries, with O(log n/loglog n) amortized time per operation on a RAM with word size w, where the only computational instructions allowed on the RAM are fuinctions in AC^0. The AC^0 instructions used are not all available on today's computers.
|
|
| 2. |
- Brodnik, Andrej, et al.
(författare)
-
Trans-dichotomous algorithms without multiplication : some upper and lower bounds
- 1997
-
Ingår i: Algorithms and Data Structures. - Berlin : Encyclopedia of Global Archaeology/Springer Verlag. - 9783540633075 ; , s. 426-439
-
Konferensbidrag (refereegranskat)abstract
- We show that on a RAM with addition, subtraction, bitwise Boolean operations and shifts, but no multiplication, there is a transdichotomous solution to the static dictionary problem using linear space and with query time log n(log log n)1+0(1). On the way, we show that two w-bit words can be multiplied in time (log w)1+0(1) and that time (log w) is necessary, and that (log log w) time is necessary and sufficient for identifying the least significant set bit of a word.
|
|
| 3. |
- Wilenius, Jim, 1976-
(författare)
-
Bidding in Combinatorial Auctions
- 2009
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis concerns the interdisciplinary field of combinatorial auctions, combining the fields of computer science, optimization and economics. A combinatorial auction is an auction where many items are sold simultaneously and where bidders may submit indivisible combinatorial bids on groups of items. It is commonly believed that good solutions to the allocation problem can be achieved by allowing combinatorial bidding. Determining who wins in a combinatorial auction is fundamentally different from a traditional single-item auction because we are faced with a hard and potentially intractable optimization problem. Also, unless we are limited to truthful mechanisms, game theoretic analysis of the strategic behavior of bidders is still an open problem. We have chosen primarily to study the first-price combinatorial auction, a natural auction widely used in practice. Theoretical analysis of this type of auction is difficult and little has been done previously. In this thesis we investigate and discuss three fundamental questions with significant practical implications for combinatorial auctions. First, because the number of possible bids grows exponentially with the number of items, limitations on the number of bids are typically required. This gives rise to a problem since bidders are unlikely to choose the "correct" bids that make up the globally optimal solution. We provide evidence that an expressive and compact bidding language can be more important than finding the optimal solution. Second, given a first-price (sealed-bid) combinatorial auction, the question of equilibrium bidding strategies remains an open problem. We propose a heuristic for finding such strategies and also present feasible strategies. And finally, is a first-price combinatorial auction worth pursuing compared to the simpler simultaneous (single-item) auction? We prove, through a model capturing many fundamental properties of multiple items scenarios with synergies, that the first-price combinatorial auction produces higher revenue than simultaneous single-item auctions. We provide bounds on revenue, given a significantly more general model, in contrast to previous work.
|
|
