Search

We study a central problem in algorithmic mechanism design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski, Nisan, and Schapira provided the first mechanism that guarantees a nontrivial approximation ratio of O(log²m) [STOC'06, ACM, New York, 2006, pp. 644-652], where m is the number of items. This approximation ratio was subsequently improved to O(logmlog logm) [S. Dobzinski, APPROX'07, Springer, Berlin, 2007, pp. 89-103] and then to O(logm) [P. Krysta and B. Vöcking, ICALP'12, Springer, Heidelberg, 2012, pp. 636-647]. In this paper we develop the first mechanism that breaks the logarithmic barrier. Specifically, the mechanism provides an approximation ratio of O(√logm). Similarly to previous constructions, our mechanism uses polynomially many value and demand queries and, in fact, provides the same approximation ratio for the larger class of XOS (also known as fractionally subadditive) valuations. We also develop a computationally efficient implementation of the mechanism for combinatorial auctions with budget additive bidders. Although, in general, computing a demand query is NP-hard for budget additive valuations, we observe that the specific form of demand queries that our mechanism uses can be efficiently computed when bidders are budget additive. [ABSTRACT FROM AUTHOR]

We present a 7 4 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a reduction of any given MAP instance to a collection of well-structured MAP instances such that the approximation guarantee is preserved. Then we present a 7 4 approximation algorithm for a well-structured MAP instance. The algorithm starts with a min-cost 2-edge cover and then applies ear-augmentation steps. We analyze the cost of the ear-augmentations using an approach similar to the one proposed by Vempala and Vetta for the (unweighted) min-size 2-ECSS problem (in: Jansen and Khuller (eds.) Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Proceedings, LNCS 1913, pp.262–273, Springer, Berlin, 2000). [ABSTRACT FROM AUTHOR]

In 1994, Klapper and Goresky (Proceedings of the 1993 Cambridge Security Workshop, Lecture Notes in Computer Science, vol 809, Cambridge, pp 174–178, 1994) proposed a new device called feedback with carry shift register to generate pseudo-random sequences instead of using the traditional device linear feedback shift register. They raised an algorithm called as rational approximation algorithm to recover the device for a given sequence (Klapper and Goresky, Advances in Cryptology, Crypto'95, Lecture Notes in Computer Science, vol 963, Springer, Berlin, pp 262–274, 1995). In this paper, we propose a new algorithm by introducing a new parameter and get the best rational approximation of the sequence much more quickly, especially when the size of the sequence increases dramatically. Unlike most of known algorithms, we can solve the minimal lattice basis instead of one shortest vector. Besides, we can prove that the solution of each step is optimal regardless of the length of the input sequence theoretically. [ABSTRACT FROM AUTHOR]