uu.seUppsala University Publications
Change search
Refine search result
1 - 28 of 28
CiteExportLink to result list
Permanent link
Cite
Citation style
• apa
• ieee
• modern-language-association
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
Rows per page
• 5
• 10
• 20
• 50
• 100
• 250
Sort
• Standard (Relevance)
• Author A-Ö
• Author Ö-A
• Title A-Ö
• Title Ö-A
• Publication type A-Ö
• Publication type Ö-A
• Issued (Oldest first)
• Issued (Newest first)
• Created (Oldest first)
• Created (Newest first)
• Last updated (Oldest first)
• Last updated (Newest first)
• Disputation date (earliest first)
• Disputation date (latest first)
• Standard (Relevance)
• Author A-Ö
• Author Ö-A
• Title A-Ö
• Title Ö-A
• Publication type A-Ö
• Publication type Ö-A
• Issued (Oldest first)
• Issued (Newest first)
• Created (Oldest first)
• Created (Newest first)
• Last updated (Oldest first)
• Last updated (Newest first)
• Disputation date (earliest first)
• Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
• 1.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Computing science.
Efficient Resource Allocation with Noisy Functions2001In: Algorithm Engineering: 5th international workshop; proceedings/WAE2001; Lecture notes in computer science, 2001, p. 91-105Conference paper (Refereed)
• 2.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Computing science.
Resource Allocation With Noisy Functions2001Conference paper (Refereed)
• 3.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
Balanced Binary Search Trees2005In: Handbook of Data Structures and Applications, CRC Press , 2005, p. 1392-Chapter in book (Other scientific)
• 4.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
General balanced trees1999In: Journal of Algorithms, Vol. 30, p. 1-28Article in journal (Refereed)

We show that, in order to achieve efficient maintenance of a balanced binary search tree, no shape restriction other than a logarithmic height is required. The obtained class of trees, general balanced trees, may be maintained at a logarithmic amortized cost with no balance information stored in the nodes. Thus, in the case when amortized bounds are sufficient, there is no need for sophisticated balance criteria.

The maintenance algorithms use partial rebuilding. This is important for certain applications, and has previously been used with weight-balanced trees. We show that the amortized cost incurred by general balanced trees is lower than what has been shown for weight-balanced trees.

• 5.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
Searching and Priority Queues in o(log n) Time2005In: Handbook of Data Structures and Applications, CRC Press , 2005, p. 1392-Chapter in book (Other (popular scientific, debate etc.))
• 6.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
Resource Allocation with Wobbly Functions2002In: Computational Optimization and Applications, ISSN 0926-6003, Vol. 23, no 2, p. 171-200Article in journal (Other scientific)
• 7.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
Measure-based performance evaluation1999In: Pattern Recognition Letters, Vol. 28Article in journal (Refereed)

The concept of measure functions for generalization performance is suggested. This concept provides an alternative way of selecting and evaluating learned classifiers, and it allows us to define the learning problem as a computational problem.

• 8.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology. Computing science.
Tight bounds for searching a sorted array of strings2000In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 30, no 5, p. 1552-1578Article in journal (Refereed)

Given a k-character query string and an array of n strings arranged in lexicographical order, computing the rank of the query string among the n strings or deciding whether it occurs in the array requires the inspection of $$\Theta\left( \frac {k\log {\log n}} {\log {\log {(4+\frac{k \log{\log n}}{\log n})}}}+k+\log n\right)$$ characters in the worst case.Read More: http://epubs.siam.org/doi/abs/10.1137/S0097539797329889

• 9.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
Sorting in linear time?1998In: Journal of Computer and System Sciences, Vol. 57, p. 74-93Article in journal (Refereed)

We show that a unit-cost RAM with a word length of w bits can sort n integers in the range 0 .. 2^(w-1) in O(n loglog n) time, for arbitrary w >= log n, a significant improvement over the bound of O(n sqrt(log n)) achieved by the fusion trees of Fredman and Willard. Provided that w >= (log n)^(2+epsilon) for some fixed epsilon>0, the sorting can even be accomplished in linear expected time with a randomized algorithm.

Both of our algorithms parallelize without loss on a unit-cost PRAM with a word length of w bits. The first one yields an algorithm that uses O(log n) time and O(n loglog n) operations on a deterministic CRCW PRAM. The second one yields an algorithm that uses O(log n) expected time and O(n) expected operations on a randomized EREW PRAM, provided that w >= (log n)^(2+epsilon) for some fixed epsilon>0.

Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting problem of sorting multiple-precision integers represented in several words.

• 10.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
An Auction Mechanism for Polynomial-time Execution with Combinatorial Constraints2005In: Proc. 7th International Conference on E-Commerce Technology, Piscataway, NJ: IEEE , 2005, p. 17-24Conference paper (Refereed)
• 11.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
Suffix trees on words1999In: Algorithmica, Vol. 23Article in journal (Refereed)

We discuss an intrinsic generalization of the suffix tree, designed to index a string of length n which has a natural partitioning into m multi-character substrings or words. This word suffix tree represents only the m suffixes that start at word boundaries. These boundaries are determined by delimiters, whose definition depends on the application.

Since traditional suffix tree construction algorithms rely heavily on the fact that all suffixes are inserted, construction of a word suffix tree is nontrivial, in particular when only O(m) construction space is allowed. We solve this problem, presenting an algorithm with O(n) expected running time. In general, construction cost is Omega(n) due to the need of scanning the entire input. In applications that require strict node ordering, an additional cost of sorting O(m') characters arises, where m' is the number of distinct words. In either case, this is a significant improvement over previously known solutions.

Furthermore, when the alphabet is small, we may assume that the $n$ characters in the input string occupy o(n) machine words. We illustrate that this can allow a word suffix tree to be built in sublinear time.

• 12.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
Fusion trees can be implemented with AC0 instructions.1999In: Theoretical Computer Science, Vol. 205, p. 337-344Article in journal (Refereed)

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.

• 13.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Datalogi.
Implementing Radixsort1998In: ACM Journal of Experimental Algorithmics., Vol. 3Article in journal (Refereed)

We present and evaluate several optimization and implementation techniques for string sorting. In particular, we study a recently published radix sorting algorithm, Forward radixsort, that has a provably good worst-case behavior. Our experimental results indicate that radix sorting is considerably faster (often more than twice as fast) than comparison-based sorting methods. This is true even for small input sequences. We also show that it is possible to implement radix sorting so as to achieve good worst-case running time without sacrificing average-case performance. Our implementations are competitive with the best previously published string sorting programs.

• 14.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
Approximate Indexed Lists.1998In: Journal of Algorithms, Vol. 29, no 2Article in journal (Refereed)

Let the position of a list element in a list be the number of elements preceding it plus one. An indexed list supports the following operations on a list: Insert; delete; return the position of an element; and return the element at a certain position. The order in which the elements appear in the list is completely determined by where the insertions take place; we do not require the presence of any keys that induce the ordering.

We consider approximate indexed lists, and show that a tiny relaxation in precision of the query operations allows a considerable improvement in time complexity. The new data structure has applications in two other problems; namely, list labeling and subset rank.

• 15.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Datalogi.
Integer Programming for Combinatorial Auction Winner Determination.2000In: Proc. of the Fourth International Conference on Multiagent Systems (ICMAS-00), 2000Conference paper (Refereed)

Combinatorial auctions are important as they enable bidders to place bids on combinations of items; compared to other auction mechanisms, they often increase the efficiency of the auction, while keeping risks for bidders low. However, the determination of an optimal winner combination in combinatorial auctions is a complex computational problem.

In this paper we (i) compare recent algorithms for winner determination to traditional algorithms, (ii) present and benchmark a mixed integer progra mming approach to the problem, which enables very general auctions to be treated efficiently by standard integer programming algorithms (and hereby also by commercially available software), and (iii) discuss the impact of the probability distributions chosen for benchmarking.

• 16.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
Dynamic Ordered Sets with Exponential Search Trees2007In: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 54, no 3, p. 1236460-Article in journal (Refereed)

We introduce exponential search trees as a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. This leads to an optimal bound of O(log n/log log n) for searching and updating a dynamic set X of n integer keys in linear space. Searching X for an integer y means finding the maximum key in X which is smaller than or equal to y. This problem is equivalent to the standard text book problem of maintaining an ordered set. The best previous deterministic linear space bound was O(log n/log log n) due to Fredman and Willard from STOC 1990. No better deterministic search bound was known using polynomial space. We also get the following worst-case linear space trade-offs between the number n, the word length W, and the maximal key U < 2W: O(min log log n + log n/logW, log log n log log U/log log log U). These trade-offs are, however, not likely to be optimal. Our results are generalized to finger searching and string searching, providing optimal results for both in terms of n.

• 17.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
Dynamic String Searching2001In: ACM-SIAM symposium on Discrete algorithms, SODA, 2001Conference paper (Refereed)
• 18.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
Tight(er) Worst-case Bounds on Dynamic Searching and Priority Queues.2000In: IEEE Symposium on Theory of Computing (STOC), 2000Conference paper (Refereed)

We introduce a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. Based on this we present optimal bounds for dynamic integer searching, including finger search, and exponentially improved bounds for priority queues.

• 19.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
A New Analysis of Revenue in the Combinatorial and Simultaneous Auction2009Report (Other academic)

We prove that in many cases, a first-price sealed-bid combinatorial auction gives higher expected revenue than a sealed-bid simultaneous auction. This is the first theoretical evidence that combinatorial auctions indeed generate higher revenue, which has been a common belief for decades.

We use a model with many bidders and items, where bidders are of two types: (i) single-bidders interested in only one item and (ii) synergy-bidders, each interested in one random combination of items. We provide an upper bound on the expected revenue for simultaneous auctions and a lower bound on combinatorial auctions. Our bounds are parameterized on the number of bidders and items, combination size, and synergy.

We derive an asymptotic result, proving that as the number of bidders approach infinity, expected revenue of the combinatorial auction will be higher than that of the simultaneous auction. We also provide concrete examples where the combinatorial auction is revenue-superior.

• 20.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
Efficient resource allocation with non-concave objective functions2001In: Computational Optimization and Applications, ISSN 0926-6003, Vol. 20, no 3, p. 281-298Article in journal (Refereed)

We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximization version of) this problem can be solved efficiently if the objective functions are concave, the general

• 21.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. datalogi.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. datalogi.
A Flexible Model for Tree-Sructured Multi-Commodity Markets2005In: CEC 2005: Seventh IEEE International Conference on E-Commerce Technology, 2005, p. 50-58Conference paper (Refereed)

In this paper we study tree-structured multi-commodity, multi-unit markets. The concept is a way to handle dependencies between commodities on the market in a tractable way. The winner determination problem of a general combinatorial market is well known to be NP-hard.

It has been shown that on single-unit single-sided combinatorial auctions with tree-structured bundles the problem can be computed in polynomial time. We show that it is possible to extend this to multi-unit double-sided markets. Further it is possible to handle the commodities of a bundle not only as complements but as perfect substitutes too. Under certain conditions the computation time is still polynomial.

• 22.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
A Flexible Model for Tree-Structured Multi-Commodity Markets2007In: Electronic Commerce Research, ISSN 1389-5753, E-ISSN 1572-9362, Vol. 7, no 1, p. 69-88Article in journal (Refereed)
• 23.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. COMPUTING SCIENCE.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
A Tractable Mechanism for Time Dependent Markets2003Report (Other scientific)
• 24.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
A Tractable Mechanism for Time Dependent Markets2003In: CEC 2003, IEEE International Conference on E-Commerce, 2003, p. 31-34Conference paper (Refereed)

Markets with time dependent goods are special cases of multi commodity markets. An application area of high interest is day-ahead power markets. If these are to be opened for consumer side bidders and local production bidders, the number of actors on the

• 25.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science. Computing science.
Extending Equilibrium Markets2001In: IEEE Intelligent Systems, ISSN 1094-7167, Vol. 16, no 4, p. 18-26Article in journal (Refereed)

The article introduces a market mechanism, CONFAST, that handles non-continuous demand/supply and is well suited for distributed computing.

• 26.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
Market-based Approaches to Optimization2007In: Computational intelligence, ISSN 0824-7935, E-ISSN 1467-8640, Vol. 23, no 1, p. 92-109Article in journal (Refereed)

We present a general discussion of what constitutes a market-oriented approach to optimization. We demonstrate how a general framework can be used to conceptually improve two well-known approaches from the literature, and discuss computational properties of the different approaches. We also show how existing theory could be adjusted to be directly applicable to the theory of the two approaches, thus proving special theory unnecessary. We want to bring out the pedagogical aspects of market mechanisms, to take full advantage of its potential.

• 27.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
Discovering Equilibrium Strategies for a Combinatorial First Price Auction2007In: 9th IEEE International Conference on E-Commerce Technology/4th IEEE International Conference on Enterprise Computing, E-Commerce and E-Services, 2007, p. 13-20Conference paper (Refereed)

In this paper the unresolved and fundamental strategy problem of the first price single round sealed bid combinatorial auction is addressed. As a step toward discovering equilibrium strategies, a new heuristic based on simple and intuitive methods is presented. The heuristic is evaluated using two different independently and uniformly distributed valuation models, one very general model where bidders bid on all combinations and one restricted model where bidders bid on one specific combination and single bids on the remaining items. Results yield natural explainable strategies with good characteristics based on comparisons of payoff, revenue and allocative efficiency.

• 28. Ygge, Fredrik
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
he HomeBots System and Field Tests: A Multi-Commodity Market for Predictive Load Management1999In: Fourth International Conference and Exhibiti on on The Practical Application of Intelligent Agents and Multi-Agents (PAAM99), 1999Conference paper (Refereed)

We present a system called HOMEBOTS for agent-based energy management services, realized by networked `smart' industrial and household equipment communicating over the power line and other media. As a consequence of the deregulation of the electricity markets in many countries, energy utilities have started to pay high interest in offering value-added energy customer services rather than merely selling electricity (kWh). We discuss a number of important technical an d business issues in launching such services, and describe some advanced solutions.

First, we present a new computational market theory, implemented in the HOMEBOTS system. It shows how large numbers of electrical loads can be automatically managed by autonomous agents, that communicate and negotiate in an electronic multi-commodity market leading to optimal use of electrical power. The advantages of this agent-based approach compared to traditional methods for power load management are described. Second, we demonstrate through simulated business scenarios that significant energy cost savings can thus be achieved. Third, our approach has been tested in a field experiment in an energy distribution area in the South-East of Sweden. The performed field tests show that the real-time requirements for agent communication over the power line in energy services are well met in realistic application settings.

1 - 28 of 28
CiteExportLink to result list
Permanent link
Cite
Citation style
• apa
• ieee
• modern-language-association
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format