BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Monika Henzinger

Monika Henzinger appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputer Science and Game TheoryLogic in Computer Sciencemath.COComputational Geometrycs.CYDiscrete MathematicsFormal Languages and Automata TheoryNetworking and Internet Architecture

Catalog footprint

What is connected

42works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

42 published item(s)

preprint2026arXiv

Dynamic Hierarchical $j$-Tree Decomposition and Its Applications

We develop a new algorithmic framework for designing approximation algorithms for cut-based optimization problems on capacitated undirected graphs that undergo edge insertions and deletions. Specifically, our framework dynamically maintains a variant of the hierarchical $j$-tree decomposition of [Madry FOCS'10], achieving a poly-logarithmic approximation factor to the graph's cut structure and supporting edge updates in $O(n^ε)$ amortized update time, for any arbitrarily small constant $ε\in (0,1)$. Consequently, we obtain new trade-offs between approximation and update/query time for fundamental cut-based optimization problems in the fully dynamic setting, including all-pairs minimum cuts, sparsest cut, multi-way cut, and multi-cut. For the last three problems, these trade-offs give the first fully-dynamic algorithms achieving poly-logarithmic approximation in sub-linear time per operation. The main technical ingredient behind our dynamic hierarchy is a dynamic cut-sparsifier algorithm that can handle vertex splits with low recourse. This is achieved by white-boxing the dynamic cut sparsifier construction of [Abraham et al. FOCS'16], based on forest packing, together with new structural insights about the maintenance of these forests under vertex splits. Given the versatility of cut sparsification in both the static and dynamic graph algorithms literature, we believe this construction may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Dynamic Maintenance of Monotone Dynamic Programs and Applications

Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or total monotonicity. In this paper, we consider a new condition which assumes (among some other technical assumptions) that the rows of the DP table are monotone. Under this assumption, we introduce a novel data structure for computing $(1+\varepsilon)$-approximate DP solutions in near-linear time and space in the static setting, and with polylogarithmic update times when the DP entries change dynamically. To the best of our knowledge, our new condition is incomparable to previous conditions and is the first which allows to derive dynamic algorithms based on existing DPs. Instead of using two-dimensional arrays to store the DP tables, we store the rows of the DP tables using monotone piecewise constant functions. This allows us to store length-$n$ DP table rows with entries in $[0,W]$ using only polylog$(n,W)$ bits, and to perform operations, such as $(\min,+)$-convolution or rounding, on these functions in polylogarithmic time. We further present several applications of our data structure. For bicriteria versions of $k$-balanced graph partitioning and simultaneous source location, we obtain the first dynamic algorithms with subpolynomial update times, as well as the first static algorithms using only near-linear time and space. Additionally, we obtain the currently fastest algorithm for fully dynamic knapsack.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter Topologies

Reconfigurable optical topologies promise to improve the performance in datacenters by dynamically optimizing the physical network in a demand-aware manner. State-of-the-art optical technologies allow to establish and update direct connectivity (in the form of edge-disjoint matchings) between top-of-rack switches within microseconds or less. However, to fully exploit temporal structure in the demand, such fine-grained reconfigurations also require fast algorithms for optimizing the interconnecting matchings. Motivated by the desire to offload a maximum amount of demand to the reconfigurable network, this paper initiates the study of fast algorithms to find k disjoint heavy matchings in graphs. We present and analyze six algorithms, based on iterative matchings, b-matching, edge coloring, and node-rankings. We show that the problem is generally NP-hard and study the achievable approximation ratios. An extensive empirical evaluation of our algorithms on both real-world and synthetic traces (88 in total), including traces collected in Facebook datacenters and in HPC clusters reveals that all our algorithms provide high-quality matchings, and also very fast ones come within 95% or more of the best solution. However, the running times differ significantly and what is the best algorithm depends on k and the acceptable runtime-quality tradeoff.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Fully Dynamic Four-Vertex Subgraph Counting

This paper presents a comprehensive study of algorithms for maintaining the number of all connected four-vertex subgraphs in a dynamic graph. Specifically, our algorithms maintain the number of paths of length three in deterministic amortized $\mathcal{O}(m^\frac{1}{2})$ update time, and any other connected four-vertex subgraph which is not a clique in deterministic amortized update time $\mathcal{O}(m^\frac{2}{3})$. Queries can be answered in constant time. We also study the query times for subgraphs containing an arbitrary edge that is supplied only with the query as well as the case where only subgraphs containing a vertex $s$ that is fixed beforehand are considered. For length-3 paths, paws, $4$-cycles, and diamonds our bounds match or are not far from (conditional) lower bounds: Based on the OMv conjecture we show that any dynamic algorithm that detects the existence of paws, diamonds, or $4$-cycles or that counts length-$3$ paths takes update time $Ω(m^{1/2-δ})$. Additionally, for $4$-cliques and all connected induced subgraphs, we show a lower bound of $Ω(m^{1-δ})$ for any small constant $δ> 0$ for the amortized update time, assuming the static combinatorial $4$-clique conjecture holds. This shows that the $\mathcal{O}(m)$ algorithm by Eppstein at al. for these subgraphs cannot be improved by a polynomial factor.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Leximax Approximations and Representative Cohort Selection

Finding a representative cohort from a broad pool of candidates is a goal that arises in many contexts such as choosing governing committees and consumer panels. While there are many ways to define the degree to which a cohort represents a population, a very appealing solution concept is lexicographic maximality (leximax) which offers a natural (pareto-optimal like) interpretation that the utility of no population can be increased without decreasing the utility of a population that is already worse off. However, finding a leximax solution can be highly dependent on small variations in the utility of certain groups. In this work, we explore new notions of approximate leximax solutions with three distinct motivations: better algorithmic efficiency, exploiting significant utility improvements, and robustness to noise. Among other definitional contributions, we give a new notion of an approximate leximax that satisfies a similarly appealing semantic interpretation and relate it to algorithmically-feasible approximate leximax notions. When group utilities are linear over cohort candidates, we give an efficient polynomial-time algorithm for finding a leximax distribution over cohort candidates in the exact as well as in the approximate setting. Furthermore, we show that finding an integer solution to leximax cohort selection with linear utilities is NP-Hard.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Practical Fully Dynamic Minimum Cut Algorithms

We present a practically efficient algorithm for maintaining a global minimum cut in large dynamic graphs under both edge insertions and deletions. While there has been theoretical work on this problem, our algorithm is the first implementation of a fully-dynamic algorithm. The algorithm uses the theoretical foundation and combines it with efficient and finely-tuned implementations to give an algorithm that can maintain the global minimum cut of a graph with rapid update times. We show that our algorithm gives up to multiple orders of magnitude speedup compared to static approaches both on edge insertions and deletions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles

Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there are approximation algorithms known in the offline setting. These graph classes include interval graphs and geometric intersection graphs, where vertices correspond to intervals/geometric objects and an edge indicates that the two corresponding objects intersect. We present dynamic approximation algorithms for independent set of intervals, hypercubes and hyperrectangles in $d$ dimensions. They work in the fully dynamic model where each update inserts or deletes a geometric object. All our algorithms are deterministic and have worst-case update times that are polylogarithmic for constant $d$ and $ε> 0$, assuming that the coordinates of all input objects are in $[0, N]^d$ and each of their edges has length at least 1. We obtain the following results: $\bullet$ For weighted intervals, we maintain a $(1+ε)$-approximate solution. $\bullet$ For $d$-dimensional hypercubes we maintain a $(1+ε)2^{d}$-approximate solution in the unweighted case and a $O(2^{d})$-approximate solution in the weighted case. Also, we show that for maintaining an unweighted $(1+ε)$-approximate solution one needs polynomial update time for $d\ge2$ if the ETH holds. $\bullet$ For weighted $d$-dimensional hyperrectangles we present a dynamic algorithm with approximation ratio $(1+ε)\log^{d-1}N$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications

We give the first non-trivial fully dynamic probabilistic tree embedding algorithm for weighted graphs undergoing edge insertions and deletions. We obtain a trade-off between amortized update time and expected stretch against an oblivious adversary. At the two extremes of this trade-off, we can maintain a tree of expected stretch $ O (\log^4 n) $ with update time $ m^{1/2 + o(1)} $ or a tree of expected stretch $ n^{o(1)} $ with update time $ n^{o(1)} $ (for edge weights polynomial in $ n $). A guarantee of the latter type has so far only been known for maintaining tree embeddings with average (instead of expected) stretch [Chechik/Zhang, SODA '20]. Our main result has direct implications to fully dynamic approximate distance oracles and fully dynamic buy-at-bulk network design. For dynamic distance oracles, our result is the first to break the $ O (\sqrt{m}) $ update-time barrier. For buy-at-bulk network design, a problem which also in the static setting heavily relies on probabilistic tree embeddings, we give the first non-trivial dynamic algorithm. As probabilistic tree embeddings are an important tool in static approximation algorithms, further applications of our result in dynamic approximation algorithms are conceivable. From a technical perspective, we obtain our main result by first designing a decremental algorithm for probabilistic low-diameter decompositions via a careful combination of Bartal's ball-growing approach [FOCS '96] with the pruning framework of Chechik and Zhang [SODA '20]. We then extend this to a fully dynamic algorithm by enriching a well-known 'decremental to fully dynamic' reduction with a new bootstrapping idea to recursively employ a fully dynamic algorithm instead of a static one in this reduction.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dynamic Matching Algorithms in Practice

In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dynamic Set Cover: Improved Amortized and Worst-Case Update Time

In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal $\min(O(\log n), f)$ approximation factor. (Throughout, $m$, $n$, $f$, and $C$ are parameters denoting the maximum number of sets, number of elements, frequency, and the cost range.) In the high-frequency range, when $f=Ω(\log n)$, this was achieved by a deterministic $O(\log n)$-approximation algorithm with $O(f \log n)$ amortized update time [Gupta et al. STOC'17]. In the low-frequency range, the line of work by Gupta et al. [STOC'17], Abboud et al. [STOC'19], and Bhattacharya et al. [ICALP'15, IPCO'17, FOCS'19] led to a deterministic $(1+ε)f$-approximation algorithm with $O(f \log (Cn)/ε^2)$ amortized update time. In this paper we improve the latter update time and provide the first bounds that subsume (and sometimes improve) the state-of-the-art dynamic vertex cover algorithms. We obtain: 1. $(1+ε)f$-approximation ratio in $O(f\log^2 (Cn)/ε^3)$ worst-case update time: No non-trivial worst-case update time was previously known for dynamic set cover. Our bound subsumes and improves by a logarithmic factor the $O(\log^3 n/\text{poly}(ε))$ worst-case update time for unweighted dynamic vertex cover (i.e., when $f=2$ and $C=1$) by Bhattacharya et al. [SODA'17]. 2. $(1+ε)f$-approximation ratio in $O\left((f^2/ε^3)+(f/ε^2) \log C\right)$ amortized update time: This result improves the previous $O(f \log (Cn)/ε^2)$ update time bound for most values of $f$ in the low-frequency range, i.e. whenever $f=o(\log n)$. It is the first that is independent of $m$ and $n$. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [SODA'19] for unweighted dynamic vertex cover (i.e., when $f = 2$ and $C = 1$).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity

Graph coloring is a fundamental problem in computer science. We study the fully dynamic version of the problem in which the graph is undergoing edge insertions and deletions and we wish to maintain a vertex-coloring with small update time after each insertion and deletion. We show how to maintain an $O(α\lg n)$-coloring with polylogarithmic update time, where $n$ is the number of vertices in the graph and $α$ is the current arboricity of the graph. This improves upon a result by Solomon and Wein (ESA'18) who maintained an $O(α_{\max}\lg^2 n)$-coloring, where $α_{\max}$ is the maximum arboricity of the graph over all updates. Furthermore, motivated by a lower bound by Barba et al. (Algorithmica'19), we initiate the study of implicit dynamic colorings. Barba et al. showed that dynamic algorithms with polylogarithmic update time cannot maintain an $f(α)$-coloring for any function $f$ when the vertex colors are stored explicitly, i.e., for each vertex the color is stored explicitly in the memory. Previously, all dynamic algorithms maintained explicit colorings. Therefore, we propose to study implicit colorings, i.e., the data structure only needs to offer an efficient query procedure to return the color of a vertex (instead of storing its color explicitly). We provide an algorithm which breaks the lower bound and maintains an implicit $2^{O(α)}$-coloring with polylogarithmic update time. In particular, this yields the first dynamic $O(1)$-coloring for graphs with constant arboricity such as planar graphs or graphs with bounded tree-width, which is impossible using explicit colorings. We also show how to dynamically maintain a partition of the graph's edges into $O(α)$ forests with polylogarithmic update time. We believe this data structure is of independent interest and might have more applications in the future.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers

We present a general framework of designing efficient dynamic approximate algorithms for optimization on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1) A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in $\tilde{O}(n^{2/3})$ amortized time against an oblivious adversary, and $\tilde{O}(m^{3/4})$ time against an adaptive adversary. (2) An incremental data structure that maintains $O(1)$-approximate shortest path in $n^{o(1)}$ time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in $\tilde{O}(n^{2/3+o(1)})$ amortized time per operation. (3) A fully-dynamic algorithm that approximates all-pair effective resistance up to an $(1+ε)$ factor in $\tilde{O}(n^{2/3+o(1)} ε^{-O(1)})$ amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as j-trees) and approximately captures the cut-flow and metric structure of the graph. The $O(1)$-approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM `05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC `19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Faster Fully Dynamic Transitive Closure in Practice

The fully dynamic transitive closure problem asks to maintain reachability information in a directed graph between arbitrary pairs of vertices, while the graph undergoes a sequence of edge insertions and deletions. The problem has been thoroughly investigated in theory and many specialized algorithms for solving it have been proposed in the last decades. In two large studies [Frigioni ea, 2001; Krommidas and Zaroliagis, 2008], a number of these algorithms have been evaluated experimentally against simple static algorithms for graph traversal, showing the competitiveness and even superiority of the simple algorithms in practice, except for very dense random graphs or very high ratios of queries. A major drawback of those studies is that only small and mostly randomly generated graphs are considered. In this paper, we engineer new algorithms to maintain all-pairs reachability information which are simple and space-efficient. Moreover, we perform an extensive experimental evaluation on both generated and real-world instances that are several orders of magnitude larger than those in the previous studies. Our results indicate that our new algorithms outperform all state-of-the-art algorithms on all types of input considerably in practice.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Faster Parallel Multiterminal Cuts

We give an improved branch-and-bound solver for the multiterminal cut problem, based on the recent work of Henzinger et al.. We contribute new, highly effective data reduction rules to transform the graph into a smaller equivalent instance. In addition, we present a local search algorithm that can significantly improve a given solution to the multiterminal cut problem. Our exact algorithm is able to give exact solutions to more and harder problems compared to the state-of-the-art algorithm by Henzinger et al.; and give better solutions for more than two third of the problems that are too large to be solved to optimality. Additionally, we give an inexact heuristic algorithm that computes high-quality solutions for very hard instances in reasonable time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finding All Global Minimum Cuts In Practice

We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fully Dynamic k-Center Clustering in Doubling Metrics

Clustering is one of the most fundamental problems in unsupervised learning with a large number of applications. However, classical clustering algorithms assume that the data is static, thus failing to capture many real-world applications where data is constantly changing and evolving. Driven by this, we study the metric $k$-center clustering problem in the fully dynamic setting, where the goal is to efficiently maintain a clustering while supporting an intermixed sequence of insertions and deletions of points. This model also supports queries of the form (1) report whether a given point is a center or (2) determine the cluster a point is assigned to. We present a deterministic dynamic algorithm for the $k$-center clustering problem that provably achieves a $(2+ε)$-approximation in poly-logarithmic update and query time, if the underlying metric has bounded doubling dimension, its aspect ratio is bounded by a polynomial and $ε$ is a constant. An important feature of our algorithm is that the update and query times are independent of $k$. We confirm the practical relevance of this feature via an extensive experimental study which shows that for values of $k$ and $ε$ suggested by theory, our algorithmic construction outperforms the state-of-the-art algorithm in terms of solution quality and running time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fully Dynamic Single-Source Reachability in Practice: An Experimental Study

Given a directed graph and a source vertex, the fully dynamic single-source reachability problem is to maintain the set of vertices that are reachable from the given vertex, subject to edge deletions and insertions. It is one of the most fundamental problems on graphs and appears directly or indirectly in many and varied applications. While there has been theoretical work on this problem, showing both linear conditional lower bounds for the fully dynamic problem and insertions-only and deletions-only upper bounds beating these conditional lower bounds, there has been no experimental study that compares the performance of fully dynamic reachability algorithms in practice. Previous experimental studies in this area concentrated only on the more general all-pairs reachability or transitive closure problem and did not use real-world dynamic graphs. In this paper, we bridge this gap by empirically studying an extensive set of algorithms for the single-source reachability problem in the fully dynamic setting. In particular, we design several fully dynamic variants of well-known approaches to obtain and maintain reachability information with respect to a distinguished source. Moreover, we extend the existing insertions-only or deletions-only upper bounds into fully dynamic algorithms. Even though the worst-case time per operation of all the fully dynamic algorithms we evaluate is at least linear in the number of edges in the graph (as is to be expected given the conditional lower bounds) we show in our extensive experimental evaluation that their performance differs greatly, both on generated as well as on real-world instances.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Ad Exchange: Envy-Free Auctions with Mediators

Ad exchanges are an emerging platform for trading advertisement slots on the web with billions of dollars revenue per year. Every time a user visits a web page, the publisher of that web page can ask an ad exchange to auction off the ad slots on this page to determine which advertisements are shown at which price. Due to the high volume of traffic, ad networks typically act as mediators for individual advertisers at ad exchanges. If multiple advertisers in an ad network are interested in the ad slots of the same auction, the ad network might use a "local" auction to resell the obtained ad slots among its advertisers. In this work we want to deepen the theoretical understanding of these new markets by analyzing them from the viewpoint of combinatorial auctions. Prior work studied mostly single-item auctions, while we allow the advertisers to express richer preferences over multiple items. We develop a game-theoretic model for the entanglement of the central auction at the ad exchange with the local auctions at the ad networks. We consider the incentives of all three involved parties and suggest a three-party competitive equilibrium, an extension of the Walrasian equilibrium that ensures envy-freeness for all participants. We show the existence of a three-party competitive equilibrium and a polynomial-time algorithm to find one for gross-substitute bidder valuations.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Conditionally Optimal Algorithms for Generalized Büchi Games

Games on graphs provide the appropriate framework to study several central problems in computer science, such as the verification and synthesis of reactive systems. One of the most basic objectives for games on graphs is the liveness (or Büchi) objective that given a target set of vertices requires that some vertex in the target set is visited infinitely often. We study generalized Büchi objectives (i.e., conjunction of liveness objectives), and implications between two generalized Büchi objectives (known as GR(1) objectives), that arise in numerous applications in computer-aided verification. We present improved algorithms and conditional super-linear lower bounds based on widely believed assumptions about the complexity of (A1) combinatorial Boolean matrix multiplication and (A2) CNF-SAT. We consider graph games with $n$ vertices, $m$ edges, and generalized Büchi objectives with $k$ conjunctions. First, we present an algorithm with running time $O(k \cdot n^2)$, improving the previously known $O(k \cdot n \cdot m)$ and $O(k^2 \cdot n^2)$ worst-case bounds. Our algorithm is optimal for dense graphs under (A1). Second, we show that the basic algorithm for the problem is optimal for sparse graphs when the target sets have constant size under (A2). Finally, we consider GR(1) objectives, with $k_1$ conjunctions in the antecedent and $k_2$ conjunctions in the consequent, and present an $O(k_1 \cdot k_2 \cdot n^{2.5})$-time algorithm, improving the previously known $O(k_1 \cdot k_2 \cdot n \cdot m)$-time algorithm for $m > n^{1.5}$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Design of Dynamic Algorithms via Primal-Dual Method

We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an $O(f^2)$-approximately optimal solution in $O(f \cdot \log (m+n))$ amortized update time, where $f$ is the maximum "frequency" of an element, $n$ is the number of sets, and $m$ is the maximum number of elements in the universe at any point in time. (2) For the dynamic $b$-matching problem, we maintain an $O(1)$-approximately optimal solution in $O(\log^3 n)$ amortized update time, where $n$ is the number of nodes in the graph.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in $O(1)$ Amortized Update Time

We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. Very recently, extending the framework of Baswana, Gupta and Sen [FOCS 2011], Solomon [FOCS 2016] gave a randomized dynamic algorithm for this problem that has an approximation ratio of $2$ and an amortised update time of $O(1)$ with high probability. This algorithm requires the assumption of an {\em oblivious adversary}, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm's past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in $O(1)$ update time. In this paper, we resolve this question. We present a new {\em deterministic} fully dynamic algorithm that maintains a $O(1)$-approximate minimum vertex cover and maximum fractional matching, with an amortised update time of $O(1)$. Previously, the best deterministic algorithm for this problem was due to Bhattacharya, Henzinger and Italiano [SODA 2015]; it had an approximation ratio of $(2+ε)$ and an amortised update time of $O(\log n/ε^2)$. Our results also extend to a fully dynamic $O(f^3)$-approximate algorithm with $O(f^2)$ amortized update time for the hypergraph vertex cover and fractional hypergraph matching problems, where every hyperedge has at most $f$ vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds

Given a graph where vertices are partitioned into $k$ terminals and non-terminals, the goal is to compress the graph (i.e., reduce the number of non-terminals) using minor operations while preserving terminal distances approximately.The distortion of a compressed graph is the maximum multiplicative blow-up of distances between all pairs of terminals. We study the trade-off between the number of non-terminals and the distortion. This problem generalizes the Steiner Point Removal (SPR) problem, in which all non-terminals must be removed. We introduce a novel black-box reduction to convert any lower bound on distortion for the SPR problem into a super-linear lower bound on the number of non-terminals, with the same distortion, for our problem. This allows us to show that there exist graphs such that every minor with distortion less than $2~/~2.5~/~3$ must have $Ω(k^2)~/~Ω(k^{5/4})~/~Ω(k^{6/5})$ non-terminals, plus more trade-offs in between. The black-box reduction has an interesting consequence: if the tight lower bound on distortion for the SPR problem is super-constant, then allowing any $O(k)$ non-terminals will not help improving the lower bound to a constant. We also build on the existing results on spanners, distance oracles and connected 0-extensions to show a number of upper bounds for general graphs, planar graphs, graphs that exclude a fixed minor and bounded treewidth graphs. Among others, we show that any graph admits a minor with $O(\log k)$ distortion and $O(k^{2})$ non-terminals, and any planar graph admits a minor with $1+\varepsilon$ distortion and $\widetilde{O}((k/\varepsilon)^{2})$ non-terminals.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs

Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with $o(mn)$ total update time, where $m$ is the number of edges and $n$ is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different $m$ vs. $n$ trade-off. For the case of $m = Θ(n^{1.5})$ the running time is $O(n^{2.47})$, just barely below $mn = Θ(n^{2.5})$. In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of $\tilde O(\min(m^{7/6} n^{2/3}, m^{3/4} n^{5/4 + o(1)}, m^{2/3} n^{4/3+o(1)} + m^{3/7} n^{12/7+o(1)}))$. This gives, e.g., $O(n^{2.36})$ for the notorious case $m = Θ(n^{1.5})$. We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning

During the last 10 years it has become popular to study dynamic graph problems in a emergency planning or sensitivity setting: Instead of considering the general fully dynamic problem, we only have to process a single batch update of size $d$; after the update we have to answer queries. In this paper, we consider the dynamic subgraph connectivity problem with sensitivity $d$: We are given a graph of which some vertices are activated and some are deactivated. After that we get a single update in which the states of up to d vertices are changed. Then we get a sequence of connectivity queries in the subgraph of activated vertices. We present the first fully dynamic algorithm for this problem which has an update and query time only slightly worse than the best decremental algorithm. In addition, we present the first incremental algorithm which is tight with respect to the best known conditional lower bound; moreover, the algorithm is simple and we believe it is implementable and efficient in practice.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time

We present a deterministic incremental algorithm for \textit{exactly} maintaining the size of a minimum cut with $\widetilde{O}(1)$ amortized time per edge insertion and $O(1)$ query time. This result partially answers an open question posed by Thorup [Combinatorica 2007]. It also stays in sharp contrast to a polynomial conditional lower-bound for the fully-dynamic weighted minimum cut problem. Our algorithm is obtained by combining a recent sparsification technique of Kawarabayashi and Thorup [STOC 2015] and an exact incremental algorithm of Henzinger [J. of Algorithm 1997]. We also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an ${O}(n\log n/\varepsilon^2)$ space Monte-Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a $(1+\varepsilon)$-approximation to the minimum cut. The algorithm has $\widetilde{O}(1)$ amortized update-time and constant query-time.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Maximizing a Submodular Function with Viability Constraints

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 algorithms. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is $(1-\frac{1}{\sqrt{e}})$. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Model and Objective Separation with Conditional Lower Bounds: Disjunction is Harder than Conjunction

Given a model of a system and an objective, the model-checking question asks whether the model satisfies the objective. We study polynomial-time problems in two classical models, graphs and Markov Decision Processes (MDPs), with respect to several fundamental $ω$-regular objectives, e.g., Rabin and Streett objectives. For many of these problems the best-known upper bounds are quadratic or cubic, yet no super-linear lower bounds are known. In this work our contributions are two-fold: First, we present several improved algorithms, and second, we present the first conditional super-linear lower bounds based on widely believed assumptions about the complexity of CNF-SAT and combinatorial Boolean matrix multiplication. A separation result for two models with respect to an objective means a conditional lower bound for one model that is strictly higher than the existing upper bound for the other model, and similarly for two objectives with respect to a model. Our results establish the following separation results: (1) A separation of models (graphs and MDPs) for disjunctive queries of reachability and Büchi objectives. (2) Two kinds of separations of objectives, both for graphs and MDPs, namely, (2a) the separation of dual objectives such as reachability/safety (for disjunctive questions) and Streett/Rabin objectives, and (2b) the separation of conjunction and disjunction of multiple objectives of the same type such as safety, Büchi, and coBüchi. In summary, our results establish the first model and objective separation results for graphs and MDPs for various classical $ω$-regular objectives. Quite strikingly, we establish conditional lower bounds for the disjunction of objectives that are strictly higher than the existing upper bounds for the conjunction of the same objectives.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

New Deterministic Approximation Algorithms for Fully Dynamic Matching

We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a $(2+ε)$-approximate maximum matching in general graphs with $O(\text{poly}(\log n, 1/ε))$ update time. (2) An algorithm that maintains an $α_K$ approximation of the {\em value} of the maximum matching with $O(n^{2/K})$ update time in bipartite graphs, for every sufficiently large constant positive integer $K$. Here, $1\leq α_K < 2$ is a constant determined by the value of $K$. Result (1) is the first deterministic algorithm that can maintain an $o(\log n)$-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best {\em randomized} polylogarithmic update time algorithm [Baswana et al. FOCS 2011]. Result (2) achieves a better-than-two approximation with {\em arbitrarily small polynomial} update time on bipartite graphs. Previously the best update time for this problem was $O(m^{1/4})$ [Bernstein et al. ICALP 2015], where $m$ is the current number of edges in the graph.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Online Ad Assignment with an Ad Exchange

Ad exchanges are becoming an increasingly popular way to sell advertisement slots on the internet. An ad exchange is basically a spot market for ad impressions. A publisher who has already signed contracts reserving advertisement impressions on his pages can choose between assigning a new ad impression for a new page view to a contracted advertiser or to sell it at an ad exchange. This leads to an online revenue maximization problem for the publisher. Given a new impression to sell decide whether (a) to assign it to a contracted advertiser and if so to which one or (b) to sell it at the ad exchange and if so at which reserve price. We make no assumptions about the distribution of the advertiser valuations that participate in the ad exchange and show that there exists a simple primal-dual based online algorithm, whose lower bound for the revenue converges to $R_{ADX} + R_A (1 - 1/e)$, where $R_{ADX}$ is the revenue that the optimum algorithm achieves from the ad exchange and $R_A$ is the revenue that the optimum algorithm achieves from the contracted advertisers.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Combinatorial Auctions with Conflict-Based Externalities

Combinatorial auctions (CA) are a well-studied area in algorithmic mechanism design. However, contrary to the standard model, empirical studies suggest that a bidder's valuation often does not depend solely on the goods assigned to him. For instance, in adwords auctions an advertiser might not want his ads to be displayed next to his competitors' ads. In this paper, we propose and analyze several natural graph-theoretic models that incorporate such negative externalities, in which bidders form a directed conflict graph with maximum out-degree $Δ$. We design algorithms and truthful mechanisms for social welfare maximization that attain approximation ratios depending on $Δ$. For CA, our results are twofold: (1) A lottery that eliminates conflicts by discarding bidders/items independent of the bids. It allows to apply any truthful $α$-approximation mechanism for conflict-free valuations and yields an $\mathcal{O}(αΔ)$-approximation mechanism. (2) For fractionally sub-additive valuations, we design a rounding algorithm via a novel combination of a semi-definite program and a linear program, resulting in a cone program; the approximation ratio is $\mathcal{O}((Δ\log \log Δ)/\log Δ)$. The ratios are almost optimal given existing hardness results. For the prominent application of adwords auctions, we present several algorithms for the most relevant scenario when the number of items is small. In particular, we design a truthful mechanism with approximation ratio $o(Δ)$ when the number of items is only logarithmic in the number of bidders.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams

While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of {\em both} time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called {\em densest subgraph problem}. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge. In a graph $G = (V, E)$, the "density" of a subgraph induced by a subset of nodes $S \subseteq V$ is defined as $|E(S)|/|S|$, where $E(S)$ is the set of edges in $E$ with both endpoints in $S$. In the densest subgraph problem, the goal is to find a subset of nodes that maximizes the density of the corresponding induced subgraph. For any $ε>0$, we present a dynamic algorithm that, with high probability, maintains a $(4+ε)$-approximation to the densest subgraph problem under a sequence of edge insertions and deletions in a graph with $n$ nodes. It uses $\tilde O(n)$ space, and has an amortized update time of $\tilde O(1)$ and a query time of $\tilde O(1)$. Here, $\tilde O$ hides a $O(\poly\log_{1+ε} n)$ term. The approximation ratio can be improved to $(2+ε)$ at the cost of increasing the query time to $\tilde O(n)$. It can be extended to a $(2+ε)$-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in {\em one pass}. The previously best algorithm in this setting required $O(\log n)$ passes [Bahmani, Kumar and Vassilvitskii, VLDB'12]. The space required by our algorithm is tight up to a polylogarithmic factor.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an $n\times n$ matrix $M$ and will receive $n$ column-vectors of size $n$, denoted by $v_1,\ldots,v_n$, one by one. After seeing each vector $v_i$, we have to output the product $Mv_i$ before we can see the next vector. A naive algorithm can solve this problem using $O(n^3)$ time in total, and its running time can be slightly improved to $O(n^3/\log^2 n)$ [Williams SODA'07]. We show that a conjecture that there is no truly subcubic ($O(n^{3-ε})$) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, $d$-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term "combinatorial algorithms" is interpreted as "non-Strassen-like algorithms" [Ballard et al. SPAA'11]. The conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures, such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase, thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching

We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph $G = (V,E)$, with $|V| = n$ and $|E| =m$, in $o(\sqrt{m}\,)$ time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a $(2+\eps)$ approximation in $O(\log n/\eps^2)$ amortized time per update. For maximum matching, we show how to maintain a $(3+\eps)$ approximation in $O(\min(\sqrt{n}/ε, m^{1/3}/\eps^2))$ {\em amortized} time per update, and a $(4+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em worst-case} time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld from STOC' 2010.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Online Bipartite Matching with Decomposable Weights

We study a weighted online bipartite matching problem: $G(V_1, V_2, E)$ is a weighted bipartite graph where $V_1$ is known beforehand and the vertices of $V_2$ arrive online. The goal is to match vertices of $V_2$ as they arrive to vertices in $V_1$, so as to maximize the sum of weights of edges in the matching. If assignments to $V_1$ cannot be changed, no bounded competitive ratio is achievable. We study the weighted online matching problem with {\em free disposal}, where vertices in $V_1$ can be assigned multiple times, but only get credit for the maximum weight edge assigned to them over the course of the algorithm. For this problem, the greedy algorithm is $0.5$-competitive and determining whether a better competitive ratio is achievable is a well known open problem. We identify an interesting special case where the edge weights are decomposable as the product of two factors, one corresponding to each end point of the edge. This is analogous to the well studied related machines model in the scheduling literature, although the objective functions are different. For this case of decomposable edge weights, we design a 0.5664 competitive randomized algorithm in complete bipartite graphs. We show that such instances with decomposable weights are non-trivial by establishing upper bounds of 0.618 for deterministic and $0.8$ for randomized algorithms. A tight competitive ratio of $1-1/e \approx 0.632$ was known previously for both the 0-1 case as well as the case where edge weights depend on the offline vertices only, but for these cases, reassignments cannot change the quality of the solution. Beating 0.5 for weighted matching where reassignments are necessary has been a significant challenge. We thus give the first online algorithm with competitive ratio strictly better than 0.5 for a non-trivial case of weighted matching with free disposal.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives

We consider Markov decision processes (MDPs) with ω-regular specifications given as parity objectives. We consider the problem of computing the set of almost-sure winning states from where the objective can be ensured with probability 1. The algorithms for the computation of the almost-sure winning set for parity objectives iteratively use the solutions for the almost-sure winning set for Büchi objectives (a special case of parity objectives). Our contributions are as follows: First, we present the first subquadratic symbolic algorithm to compute the almost-sure winning set for MDPs with Büchi objectives; our algorithm takes O(n \sqrt{m}) symbolic steps as compared to the previous known algorithm that takes O(n^2) symbolic steps, where $n$ is the number of states and $m$ is the number of edges of the MDP. In practice MDPs have constant out-degree, and then our symbolic algorithm takes O(n \sqrt{n}) symbolic steps, as compared to the previous known $O(n^2)$ symbolic steps algorithm. Second, we present a new algorithm, namely win-lose algorithm, with the following two properties: (a) the algorithm iteratively computes subsets of the almost-sure winning set and its complement, as compared to all previous algorithms that discover the almost-sure winning set upon termination; and (b) requires O(n \sqrt{K}) symbolic steps, where K is the maximal number of edges of strongly connected components (scc's) of the MDP. The win-lose algorithm requires symbolic computation of scc's. Third, we improve the algorithm for symbolic scc computation; the previous known algorithm takes linear symbolic steps, and our new algorithm improves the constants associated with the linear number of steps. In the worst case the previous known algorithm takes 5n symbolic steps, whereas our new algorithm takes 4n symbolic steps.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Approximating the minimum cycle mean

We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean weight. Our contributions are twofold: (1) First we show that the algorithmic question is reducible in O(n^2) time to the problem of a logarithmic number of min-plus matrix multiplications of n-by-n matrices, where n is the number of vertices of the graph. (2) Second, when the weights are nonnegative, we present the first (1 + ε)-approximation algorithm for the problem and the running time of our algorithm is \tilde(O)(n^ωlog^3(nW/ε) / ε), where O(n^ω) is the time required for the classic n-by-n matrix multiplication and W is the maximum value of the weights.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Valuation Compressions in VCG-Based Combinatorial Auctions

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Auctions with Heterogeneous Items and Budget Limits

We study individual rational, Pareto optimal, and incentive compatible mechanisms for auctions with heterogeneous items and budget limits. For multi-dimensional valuations we show that there can be no deterministic mechanism with these properties for divisible items. We use this to show that there can also be no randomized mechanism that achieves this for either divisible or indivisible items. For single-dimensional valuations we show that there can be no deterministic mechanism with these properties for indivisible items, but that there is a randomized mechanism that achieves this for either divisible or indivisible items. The impossibility results hold for public budgets, while the mechanism allows private budgets, which is in both cases the harder variant to show. While all positive results are polynomial-time algorithms, all negative results hold independent of complexity considerations.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Sponsored Search, Market Equilibria, and the Hungarian Method

Matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market. Here, as in other markets of that kind, market equilibria correspond to feasible, envy free, and bidder optimal outcomes. For settings without budgets such an outcome always exists and can be computed in polynomial-time by the so-called Hungarian Method. Moreover, every mechanism that computes such an outcome is incentive compatible. We show that the Hungarian Method can be modified so that it finds a feasible, envy free, and bidder optimal outcome for settings with budgets. We also show that in settings with budgets no mechanism that computes such an outcome can be incentive compatible for all inputs. For inputs in general position, however, the presented mechanism---as any other mechanism that computes such an outcome for settings with budgets---is incentive compatible.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

An O(n^2) Time Algorithm for Alternating Büchi Games

Computing the winning set for B{ü}chi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is $\tilde{O}(n \cdot m)$, where $n$ is the number of vertices and $m$ is the number of edges in the graph. We are the first to break the $\tilde{O}(n\cdot m)$ bound by presenting a new technique that reduces the running time to $O(n^2)$. This bound also leads to an $O(n^2)$ algorithm time for computing the set of almost-sure winning vertices in alternating games with probabilistic transitions (improving an earlier bound of $\tilde{O}(n\cdot m)$) and in concurrent graph games with constant actions (improving an earlier bound of $O(n^3)$). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time $O(n^2)$. Finally, we show how to maintain the winning set for B{ü}chi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On Multiple Round Sponsored Search Auctions with Budgets

In a sponsored search auction the advertisement slots on a search result page are generally ordered by click-through rate. Bidders have a valuation, which is usually assumed to be linear in the click-through rate, a budget constraint, and receive at most one slot per search result page (round). We study multi-round sponsored search auctions, where the different rounds are linked through the budget constraints of the bidders and the valuation of a bidder for all rounds is the sum of the valuations for the individual rounds. All mechanisms published so far either study one-round sponsored search auctions or the setting where every round has only one slot and all slots have the same click-through rate, which is identical to a multi-item auction. This paper contains the following three results: (1) We give the first mechanism for the multi-round sponsored search problem where different slots have different click-through rates. Our mechanism is incentive compatible in expectation, individually rational in expectation, Pareto optimal in expectation, and also ex-post Pareto optimal for each realized outcome. (2) Additionally we study the combinatorial setting, where each bidder is only interested in a subset of the rounds. We give a deterministic, incentive compatible, individually rational, and Pareto optimal mechanism for the setting where all slots have the same click-through rate. (3) We present an impossibility result for auctions where bidders have diminishing marginal valuations. Specifically, we show that even for the multi-unit (one slot per round) setting there is no incentive compatible, individually rational, and Pareto optimal mechanism for private diminishing marginal valuations and public budgets.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Online Stochastic Packing Applied to Display Ad Allocation

Inspired by online ad allocation, we study online stochastic packing linear programs from theoretical and practical standpoints. We first present a near-optimal online algorithm for a general class of packing linear programs which model various online resource allocation problems including online variants of routing, ad allocations, generalized assignment, and combinatorial auctions. As our main theoretical result, we prove that a simple primal-dual training-based algorithm achieves a (1 - o(1))-approximation guarantee in the random order stochastic model. This is a significant improvement over logarithmic or constant-factor approximations for the adversarial variants of the same problems (e.g. factor 1 - 1/e for online ad allocation, and \log m for online routing). We then focus on the online display ad allocation problem and study the efficiency and fairness of various training-based and online allocation algorithms on data sets collected from real-life display ad allocation system. Our experimental evaluation confirms the effectiveness of training-based primal-dual algorithms on real data sets, and also indicate an intrinsic trade-off between fairness and efficiency.

0 citations0 reviewsNo code linkedOpen access