waashk/dblp huggingface dataset:
robbing the bandit: less regret in online geometric optimization against an adaptive adversary. we consider "online bandit geometric optimization," a problem of iterated decision making in a largely unknown and constantly changing environment. the goal is to minimize "regret," defined as the difference between the actual loss of an online decision-making procedure and that of the best single decision in hindsight. "geometric optimization" refers to a generalization of the well-known multi-armed bandit problem, in which the decision space is some bounded subset of rd, the adversary is restricted to linear loss functions, and regret bounds should depend on the dimensionality d, rather than the total number of possible decisions. "bandit" refers to the setting in which the algorithm is only told its loss on each round, rather than the entire loss function.mcmahan and blum [10] presented the best known algorithm in this setting, and proved that its expected additive regret is o(poly(d)t3/4). we simplify and improve their analysis of this algorithm to obtain regret o(poly(d)t2/3).we also prove that, for a large class of full-information online optimization problems, the optimal regret against an adaptive adversary is the same as against a non-adaptive adversary.
maintaining stream statistics over sliding windows (extended abstract). we consider the problem of maintaining aggregates and statistics over data streams, with respect to the last n data elements seen so far. we refer to this model as the sliding window model. we consider the following basic problem: given a stream of bits, maintain a count of the number of 1's in the last n elements seen from the stream. we show that using o(1/e log2n) bits of memory, we can estimate the number of 1's to within a factor of 1 + &epsilon;. we also give a matching lower bound of &omega;(1/e log2 n) memory bits for any deterministic or randomized algorithms. we extend our scheme to maintain the sum of the last n positive integers. we provide matching upper and lower bounds for this more general problem as well. we apply our techniques to obtain efficient algorithms for the lp norms (for p &epsilon; [1, 2]) of vectors under the sliding window model. using the algorithm for the basic counting problem, one can adapt many other techniques to work for the sliding window model, with a multiplicative overhead of o(1/&epsilon;log n) in memory and a 1 + &epsilon; factor loss in accuracy. these include maintaining approximate histograms, hash tables, and statistics or aggregates such as sum and averages.
models of greedy algorithms for graph problems. borodin, nielsen, and rackoff ([5]) gave a model of greedy-like algorithms for scheduling problems and [1] extended their work to facility location and set cover problems. we generalize their notion to include other optimization problems, and apply the generalized framework to graph problems. our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems. we prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, vertex cover, and others. shortest path is an example of a problem where no algorithm in the fixed priority model can achieve any approximation ratio (even one dependent on the graph size), but for which the well-known dijkstra's algorithm shows that an adaptive priority algorithm can be optimal. we also prove that the approximation ratio for vertex cover achievable by adaptive priority algorithms is exactly 2. here, a new lower bound matches the known upper bounds ([8]).
adaptivity and approximation for stochastic packing problems. we study stochastic variants of packing integer programs (pip) --- the problems of finding a maximum-value 0/1 vector x satisfying ax &le; b, with a and b nonnegative. many combinatorial problems belong to this broad class, including the knapsack problem, maximum clique, stable set, matching, hypergraph matching (a.k.a. set packing), b-matching, and others. pip can also be seen as a "multidimensional" knapsack problem where we wish to pack a maximum-value collection of items with vector-valued sizes. in our stochastic setting, the vector-valued sizes of each item is known to us apriori only as a probability distribution, and the size of an item is instantiated once we commit to including the item in our solution.following the framework of [3], we consider both adaptive and non-adaptive policies for solving such problems, adaptive policies having the flexibility of being able to make decisions based on the instantiated sizes of items already included in the solution. we investigate the adaptivity gap for these problems: the maximum ratio between the expected values achieved by optimal adaptive and non-adaptive policies. we show tight bounds on the adaptivity gap for set packing and b-matching, and we also show how to find efficiently non-adaptive policies approximating the adaptive optimum. for instance, we can approximate the adaptive optimum for stochastic set packing to within o(d1/2), which is not only optimal with respect to the adaptivity gap, but it is also the best known approximation factor in the deterministic case. it is known that there is no polynomial-time d1/2-&epsilon; approximation for set packing, unless np = zpp. similarly, for b-matching, we obtain algorithmically a tight bound on the adaptivity gap of o(&lambda;) where &lambda; satisfies &sigma; &lambda;bj+1 = 1.for general stochastic packing, we prove that a simple greedy algorithm provides an o(d)-approximation to the adaptive optimum. for a &isin; [0, 1]dxn, we provide an o(&lambda;) approximation where &sigma; 1/&lambda;bj = 1. (for b = (b, b,..., b), we get &lambda; = d1/b.) we also improve the hardness results for deterministic pip: in the general case, we prove that a polynomial-time d1-&epsilon;-approximation algorithm would imply np = zpp. in the special case when a &isin; [0,1]dxn and b = (b,b,...,b), we show that a d1/b-&isin;-approximation would imply np = zpp. finally, we prove that it is pspace-hard to find the optimal adaptive policy for stochastic packing in any fixed dimension d &ge; 2.
four point conditions and exponential neighborhoods for symmetric tsp. in most of the known polynomially solvable cases of the symmetric travelling salesman problem (tsp) which result from restrictions on the underlying distance matrices, the restrictions have the form of so-called four-point conditions (the inequalities involve four cities). in this paper we treat all possible (symmetric) four-point conditions and investigate whether the corresponding tsp can be solved in polynomial time. as a by-product of our classification we obtain new families of exponential neighborhoods for the tsp which can be searched in polynomial time and for which conditions on the distance matrix can be formulated so that the search for an optimal tsp solution can be restricted to these exponential neighborhoods.
an algorithmic friedman--pippenger theorem on tree embeddings and applications to routing. an (n, d)-expander is a graph g = (v, e) such that for every x &sube; v with |x| &le; 2n &minus; 2 we have |&gamma;g(x)| &ge; (d + 1)|x|. a tree t is small if it has at most n vertices and has maximum degree at most d. friedman and pippenger (1987) proved that any (n, d)-expander contains every small tree. the elegant proof discovered by those authors does not yield an efficient algorithm for obtaining the tree. in this extended abstract, we give an alternative, polynomial formulation for a key concept in their proof, and thus obtain an efficient algorithm for the friedman---pippenger theorem.as an application, we offer a polynomial time algorithm for routing connection requests in wide-sense non-blocking networks of constant depth, following an approach put forward in a seminal paper of feldman, friedman, and pippenger (1988). we thus provide a simple, efficient companion routing scheme for the explicitly described networks of essentially optimal size given by wigderson and zuckerman (1999). the applicability of our methods to deterministically constructible networks is in contrast with some previous work of aggarwal et al. (1996).
subexponential parameterized algorithms on graphs of bounded-genus and -minor-free graphs. we introduce a new framework for designing fixed-parameter algorithms with subexponential running time---2o(&radic;k)no(1). our results apply to a broad family of graph problems, called bidimensional problems, which includes many domination and covering problems such as vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, clique-transversal set, and many others restricted to bounded-genus graphs. furthermore, it is fairly straightforward to prove that a problem is bidimensional. in particular, our framework includes as special cases all previously known problems to have such subexponential algorithms. previously, these algorithms applied to planar graphs, single-crossing-minor-free graphs, and map graphs; we extend these results to apply to bounded-genus graphs as well. in a parallel development of combinatorial results, we establish an upper bound on the treewidth (or branchwidth) of a bounded-genus graph that excludes some planar graph h as a minor. this bound depends linearly on the size |v (h)| of the excluded graph h and the genus g(g) of the graph g, and applies and extends the graphminors work of robertson & seymour.building on these results, we develop subexponential fixedparameter algorithms for dominating set, vertex cover, and set cover in any class of graphs excluding a fixed graph h as a minor. in particular, this general category of graphs includes planar graphs, bounded-genus graphs, single-crossing-minor-free graphs, and any class of graphs that is closed under taking minors. specifically, the running time is 2o(&radic;k)nh, where h is a constant depending only on h, which is polynomial for k = o(log2n). we introduce a general approach for developing algorithms on h-minor-free graphs, based on structural results about h-minor-free graphs at the heart of robertson & seymour's graph-minors work. we believe this approach opens the way to further development for problems on h-minor-free graphs.
equivalence of local treewidth and linear local treewidth and its algorithmic applications. we solve an open problem posed by eppstein in 1995 [14, 15] and re-enforced by grohe [16, 17] concerning locally bounded treewidth in minor-closed families of graphs. a graph has bounded local treewidth if the subgraph induced by vertices within distance r of any vertex has treewidth bounded by a function of r (not n). eppstein characterized minor-closed families of graphs with bounded local treewidth as precisely minor-closed families that minor-exclude an apex graph, where an apex graph has one vertex whose removal leaves a planar graph. in particular, eppstein showed that all apex-minor-free graphs have bounded local treewidth, but his bound is doubly exponential in r, leaving open whether a tighter bound could be obtained. we improve this doubly exponential bound to a linear bound, which is optimal. in particular, any minor-closed graph family with bounded local treewidth has linear local treewidth. our bound generalizes previously known linear bounds for special classes of graphs proved by several authors. as a consequence of our result, we obtain substantially faster polynomial-time approximation schemes for a broad class of problems in apex-minor-free graphs, improving the running time from 222o(1/ε) no(1) to 2o(1/ε)no(1).
bidimensionality: new connections between fpt algorithms and ptass. we demonstrate a new connection between fixed-parameter tractability and approximation algorithms for combinatorial optimization problems on planar graphs and their generalizations. specifically, we extend the theory of so-called "bidimensional" problems to show that essentially all such problems have both subexponential fixed-parameter algorithms and ptass. bidimensional problems include e.g. feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex-removal problems, dominating set, edge dominating set, r-dominating set, diameter, connected dominating set, connected edge dominating set, and connected r-dominating set. we obtain ptass for all of these problems in planar graphs and certain generalizations; of particular interest are our results for the two well-known problems of connected dominating set and general feedback vertex set for planar graphs and their generalizations, for which ptass were not known to exist. our techniques generalize and in some sense unify the two main previous approaches for designing ptass in planar graphs, namely, the lipton-tarjan separator approach [focs'77] and the baker layerwise decomposition approach [focs'83]. in particular, we replace the notion of separators with a more powerful tool from the bidimensionality theory, enabling the first approach to apply to a much broader class of minimization problems than previously possible; and through the use of a structural backbone and thickening of layers we demonstrate how the second approach can be applied to problems with a "nonlocal" structure.
graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. we prove that any h-minor-free graph, for a fixed graph h, of treewidth &omega; has an &omega;(&omega;) &times; &omega;(&omega;) grid graph as a minor. thus grid minors suffice to certify that h-minor-free graphs have large treewidth, up to constant factors. this strong relationship was previously known for the special cases of planar graphs and bounded-genus graphs, and is known not to hold for general graphs. the approach of this paper can be viewed more generally as a framework for extending combinatorial results on planar graphs to hold on h-minor-free graphs for any fixed h. our result has many combinatorial con-sequences on bidimensionality theory, parameter-treewidth bounds, separator theorems, and bounded local treewidth; each of these combinatorial results has several algorithmic consequences including subexponential fixed-parameter algorithms and approximation algorithms.
combination can be hard: approximability of the unique coverage problem. we prove semi-logarithmic inapproximability for a maximization problem called unique coverage: given a collection of sets, find a subcollection that maximizes the number of elements covered exactly once. specifically, we prove o(1/ log&sigma;(&epsilon;)n) inapproximability assuming that np &nsube; bptime(2n&epsilon;) for some &epsilon; > 0. we also prove o(1/log1/3-&epsilon; n) inapproximability, for any &epsilon; > 0, assuming that refuting random instances of 3sat is hard on average; and prove o(1/log n) inapproximability under a plausible hypothesis concerning the hardness of another problem, balanced bipartite independent set. we establish matching upper bounds up to exponents, even for a more general (budgeted) setting, giving an &omega;(1/log n)-approximation algorithm as well as an &omega;(1/log b)-approximation algorithm when every set has at most b elements. we also show that our inapproximability results extend to envy-free pricing, an important problem in computational economics. we describe how the (budgeted) unique coverage problem, motivated by real-world applications, has close connections to other theoretical problems including max cut, maximum coverage, and radio broad-casting.
retroactive data structures. we introduce a new data structuring paradigm in which operations can be performed on a data structure not only in the present but also in the past. in this new paradigm, called retroactive data structures, the historical sequence of operations performed on the data structure is not fixed. the data structure allows arbitrary insertion and deletion of operations at arbitrary times, subject only to consistency requirements. we initiate the study of retroactive data structures by formally defining the model and its variants. we prove that, unlike persistence, efficient retroactivity is not always achievable, so we go on to present several specific retroactive data structures.
interpolation search for non-independent data. we define a deterministic metric of "well-behaved data" that enables searching along the lines of interpolation search. specifically, define &delta; to be the ratio of distances between the farthest and nearest pair of adjacent elements. we develop a data structure that stores a dynamic set of n integers subject to insertions, deletions, and predecessor/successor queries in o(lg &delta;) time per operation. this result generalizes interpolation search and interpolation search trees smoothly to nonrandom (in particular, non-independent) input data. in this sense, we capture the amount of "pseudorandomness" required for effective interpolation search.
a linear lower bound on index size for text retrieval. most information-retrieval systems preprocess the data to produce an auxiliary index structure. empirically, it has been observed that there is a tradeoff between query response time and the size of the index. when indexing a large corpus, such as the web, the size of the index is an important consideration. in this case it would be ideal to produce an index that is substantially smaller than the text. in this work we prove a linear worst-case lower bound on the size of any index that reports the location (if any) of a substring in the text in time proportional to the length of the pattern. in other words, an index supporting linear-time substring searches requires about as much space as the original text. here "time" is measured in the number of bit probes to the text; an arbitrary amount of computation may be done on an arbitrary amount of the index. our lower bound applies to inverted word indices as well.
on universally easy classes for np-complete problems. we explore the natural question of whether all np-complete problems have a common restriction under which they are polynomially solvable. more precisely, we study what languages are universally easy in that their intersection with any np-complete problem is in p. in particular, we give a polynomial-time algorithm to determine whether a regular language is universally easy. while our approach is language-theoretic, the results bear directly on finding polynomial-time solutions to very broad and useful classes of problems.
experimental analysis of dynamic all pairs shortest path algorithms. we present the results of an extensive computational study on dynamic algorithms for all pairs shortest path problems. we describe our implementations of the recent dynamic algorithms of king [18] and of demetrescu and italiano [7], and compare them to the dynamic algorithm of ramalingam and reps [25] and to static algorithms on random, real-world and hard instances. our experimental data suggest that some of the dynamic algorithms and their algorithmic techniques can be really of practical value in many situations.
trading off space for passes in graph streaming problems. data stream processing has recently received increasing attention as a computational paradigm for dealing with massive data sets. surprisingly, no algorithm with both sublinear space and passes is known for natural graph problems in classical read-only streaming. motivated by technological factors of modern storage systems, some authors have recently started to investigate the computational power of less restrictive models where writing streams is allowed. in this article, we show that the use of intermediate temporary streams is powerful enough to provide effective space-passes tradeoffs for natural graph problems. in particular, for any space restriction of s bits, we show that single-source shortest paths in directed graphs with small positive integer edge weights can be solved in o((n log3/2 n)/&sqrt;s) passes. the result can be generalized to deal with multiple sources within the same bounds. this is the first known streaming algorithm for shortest paths in directed graphs. for undirected connectivity, we devise an o((n log n)/s) passes algorithm. both problems require &omega;(n/s) passes under the restrictions we consider. we also show that the model where intermediate temporary streams are allowed can be strictly more powerful than classical streaming for some problems, while maintaining all of its hardness for others.
oracles for distances avoiding a link-failure. for a directed graph g we consider queries of the form: "what is the shortest path distance from vertex x to vertex y in g avoiding a failed link (u, v), and what edge leaving x should we use to get on a such a shortest path?" we show that an oracle for such queries can be stored in o(n2 log n) space with a query time of o(log n). no non-trivial solution was known for this problem.
finding nucleolus of flow game. we study the algorithmic issues of finding the nucleolus of a flow game. the flow game is a cooperative game defined on a network d = (v, e; &omega;). the player set is e and the value of a coalition s &sube; e is defined as the value of the maximum flow from source to sink in the subnetwork induced by s. we show that the nucleolus of the flow game defined on a simple network (&omega;(e) = 1 for each e &isin; e) can be computed in polynomial time by a linear program duality approach, settling a twenty-three years old conjecture by kalai and zemel. in contrast, we prove that both computation and recognition of the nucleolus are np-hard for flow games with general capacity.
preemptive scheduling of parallel jobs on multiprocessors. we study the problem of processor scheduling for n parallel jobs applying the method of competitive analysis. we prove that for jobs with a single phase of parallelism, a preemptive scheduling algorithm without information about job execution time can achieve a mean completion time within $2-{2\over n+1}$ times the optimum. in other words, we prove a competitive ratio of $2-{2\over n+1}$. the result is extended to jobs with multiple phases of parallelism (which can be used to model jobs with sublinear speedup) and to interactive jobs (with phases during which the job has no cpu requirements) to derive solutions guaranteed to be within $4-{4\over n+1}$ times the optimum. in comparison with previous work, our assumption that job execution times are unknown prior to their completion is more realistic, our multiphased job model is more general, and our approximation ratio (for jobs with a single phase of parallelism) is tighter and cannot be improved. while this work presents theoretical results obtained using competitive analysis, we believe that the results provide insight into the performance of practical multiprocessor scheduling algorithms that operate in the absence of complete information.
matrix approximation and projective clustering via volume sampling. frieze et al. [17] proved that a small sample of rows of a given matrix a contains a low-rank approximation d that minimizes ||a - d||f to within small additive error, and the sampling can be done efficiently using just two passes over the matrix [12]. in this paper, we generalize this result in two ways. first, we prove that the additive error drops exponentially by iterating the sampling in an adaptive manner. using this result, we give a pass-efficient algorithm for computing low-rank approximation with reduced additive error. our second result is that using a natural distribution on subsets of rows (called volume sampling), there exists a subset of k rows whose span contains a factor (k + 1) relative approximation and a subset of k + k(k + 1)/&epsilon; rows whose span contains a 1+&epsilon; relative approximation. the existence of such a small certificate for multiplicative low-rank approximation leads to a ptas for the following projective clustering problem: given a set of points p in rd, and integers k, j, find a set of j subspaces f1, . . ., fj, each of dimension at most k, that minimize &sigma;p&isin;pmini d(p, fi)2.