TY - CONF AB - We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We show (1 + ε)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network. This breaks the Θ(D) time bound of recomputing “from scratch”. Our technique also leads to a (1 + ε)-approximate incremental algorithm for single-source shortest paths (SSSP) in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of [9] that is optimal under some assumptions [27]. Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if a small approximation is allowed. AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Nanongkai, Danupon ID - 11793 SN - 1611-3349 T2 - 40th International Colloquium on Automata, Languages, and Programming TI - Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks VL - 7966 ER - TY - CONF AB - The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions the truthful direct-revelation mechanism that maximizes social welfare is the VCG mechanism. For many valuation spaces computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that the welfare loss increases in expressiveness. All our bounds apply to equilibrium concepts that can be computed in polynomial time as well as to learning outcomes. AU - Dütting, Paul AU - Henzinger, Monika H AU - Starnberger, Martin ID - 11791 SN - 1611-3349 T2 - 9th International Conference on Web and Internet Economics TI - Valuation compressions in VCG-based combinatorial auctions VL - 8289 ER - TY - CONF AB - We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant depth. The goal is to select a subset of k species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithm. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is (1−1𝑒√). This algorithm not only applies to phylogenetic trees with viability constraints but for arbitrary monotone submodular set functions with viability constraints. Second, we show that there is no (1 − 1/e + ε)-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting. AU - Dvořák, Wolfgang AU - Henzinger, Monika H AU - Williamson, David P. ID - 11792 SN - 1611-3349 T2 - 21st Annual European Symposium on Algorithms TI - Maximizing a submodular function with viability constraints VL - 8125 ER - TY - CONF AB - We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of Ȏ(mn) and constant query time by Roditty and Zwick (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach (JACM 1981); it has a total update time of O(mn 2 ) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of Ȏ(n 5/2 ) and constant query time that has an additive error of two in addition to the 1 + ϵ multiplicative error. This beats the previous Ȏ(mn) time when m = Ω(n 3/2 ). Note that the additive error is unavoidable since, even in the static case, an O(n 3-δ )-time (a so-called truly sub cubic) combinatorial algorithm with 1 + ϵ multiplicative error cannot have an additive error less than 2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor, Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 + ϵ)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + ϵ)-approximation algorithm with Ȏ(n 5/2+O(1√(log n)) ) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of Ȏ(mn) and a query time of O(log log n). The algorithm has a multiplicative error of 1 + ϵ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper. In order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called locally persevering emulator. (2) A derandomization technique based on moving Even-Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest. AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Nanongkai, Danupon ID - 11856 SN - 0272-5428 T2 - 54th Annual Symposium on Foundations of Computer Science TI - Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization ER - TY - JOUR AB - We study the problem of matching bidders to items where each bidder i has general, strictly monotonic utility functions ui,j(pj) expressing his utility of being matched to item j at price pj. For this setting we prove that a bidder optimal outcome always exists, even when the utility functions are non-linear and non-continuous. We give sufficient conditions under which every mechanism that finds a bidder optimal outcome is incentive compatible. We also give a mechanism that finds a bidder optimal outcome if the conditions for incentive compatibility are satisfied. The running time of this mechanism is exponential in the number of items, but polynomial in the number of bidders. AU - Dütting, Paul AU - Henzinger, Monika H AU - Weber, Ingmar ID - 11902 IS - 3 JF - Theoretical Computer Science SN - 0304-3975 TI - Bidder optimal assignments for general utilities VL - 478 ER -