waashk/dblp huggingface dataset:
multiple source shortest paths in a genus g graph. we give an o(g2nlog n) algorithm to represent the shortest path tree from all the vertices on a single specified face f in a genus g graph. from this representation, any query distance from a vertex in f can be obtained in o(log n) time. the algorithm uses a kinetic data structure, where the source of the tree iteratively moves across edges in f. in addition, we give applications using these shortest path trees in order to compute the shortest non-contractible cycle and the shortest non-separating cycle embedded on an orientable 2-manifold in o(g3nlog n) time.
obnoxious centers in graphs. we consider the problem of finding obnoxious centers in graphs. for arbitrary graphs with n vertices and m edges, we give a randomized algorithm with o(n log2 n + m log n) expected time. for planar graphs, we give algorithms with o(n log n) expected time and o(n log3 n) worst-case time. for graphs with bounded treewidth, we give an algorithm taking o(n log n) worst-case time. the algorithms make use of parametric search and several results for computing distances on graphs of bounded treewidth and planar graphs.
declaring independence via the sketching of sketches. we consider the problem of identifying correlations in data streams. surprisingly, our work seems to be the first to consider this natural problem. in the centralized model, we consider a stream of pairs (i,j) &isin; [n]2 whose frequencies define a joint distribution (x,y). in the distributed model, each coordinate of the pair may appear separately in the stream. we present a range of algorithms for approximating to what extent x and y are independent, i.e., how close the joint distribution is to the product of the marginals. we consider various measures of closeness including &ell;1, &ell;2, and the mutual information between x and y. our algorithms are based on "sketching sketches", i.e., composing small-space linear synopses of the distributions. perhaps ironically, the biggest technical challenges that arise relate to ensuring that different components of our estimates are sufficiently independent.
fast asynchronous byzantine agreement and leader election with full information. we resolve two long-standing open problems in distributed computation by describing polylogarithmic protocols for byzantine agreement and leader election in the asynchronous full information model with a non-adaptive malicious adversary. all past protocols for asynchronous byzantine agreement had been exponential, and no protocol for asynchronous leader election had been known. our protocols tolerate up to n/6+&epsilon; faulty processors, for any positive constant &epsilon;. they are monte carlo, succeeding with probability 1 - o(1) for byzantine agreement, and constant probability for leader election. a key technical contribution of our paper is a new approach for emulating feige's lightest bin protocol, even with adversarial message scheduling.
energy efficient online deadline scheduling. this paper extends the study of online algorithms for energy-efficient deadline scheduling to the overloaded setting. specifically, we consider a processor that can vary its speed between 0 and a maximum speed t to minimize its energy usage (of which the rate is roughly a cubic function of the speed). as the speed is upper bounded, the system may be overloaded with jobs and no scheduling algorithms can meet the deadlines of all jobs. an optimal schedule is expected to maximize the throughput, and furthermore, its energy usage should be the smallest among all schedules that achieve the maximum throughput. in designing a scheduling algorithm, one has to face the dilemma of selecting more jobs and being conservative in energy usage. even if we ignore energy usage, the best possible online algorithm is 4-competitive on throughput [12]. on the other hand, existing work on energy-efficient scheduling focuses on minimizing the energy to complete all jobs on a processor with unbounded speed, giving several o(1)-competitive algorithms with respect to the energy usage [2, 20]. this paper presents the first online algorithm for the more realistic setting where processor speed is bounded and the system may be overloaded; the algorithm is o(1)-competitive on both throughput and energy usage. if the maximum speed of the online scheduler is relaxed slightly to (1 + &epsilon;)t for some &epsilon; > 0, we can improve the competitive ratio on throughput to arbitrarily close to one, while maintaining o(1)-competitive on energy usage.
near-optimal algorithms for maximum constraint satisfaction problems. in this article, we present two approximation algorithms for the maximum constraint satisfaction problem with k variables in each constraint (max k-csp). given a (1 &minus; &epsiv;) satisfiable 2csp our first algorithm finds an assignment of variables satisfying a 1 &minus; o(&sqrt;&epsiv;) fraction of all constraints. the best previously known result, due to zwick, was 1 &minus; o(&epsiv;1/3). the second algorithm finds a ck/2k approximation for the max k-csp problem (where c > 0.44 is an absolute constant). this result improves the previously best known algorithm by hast, which had an approximation guarantee of &omega;(k/(2k log k)). both results are optimal assuming the unique games conjecture and are based on rounding natural semidefinite programming relaxations. we also believe that our algorithms and their analysis are simpler than those previously known.
a divide and conquer algorithm for -dimensional arrangement. we give an o(&radic;log n)-approximation algorithm for d-dimensional arrangement - the problem of mapping a graph to a d-dimensional grid (for constant d &ge; 2) to minimize the sum of edge lengths. this improves the previous best o(log n log log n) approximation of even, naor, rao and schieber. the d = 1 case is the well studied minimum linear arrangement problem. the problem is equivalent to the question of mapping a graph to integer points on a line so as to minimize the sum of edge costs, where edge costs are measured by edge lengths raised to the exponent &alpha; = 1/d. we give a simple recursive partitioning algorithm for this variant of linear arrangement for any exponent &alpha; &epsilon; (0, 1). our analysis also applies to a directed version of the problem: given a directed graph, the goal is to map vertices to the line so as to minimize the sum of costs of forward edges. as before, edge costs are edge lengths raised to the exponent &alpha;. the &alpha; = 0 case is the well known minimum feedback arc set problem, and the &alpha; = 1 case is essentially the minimum storage-time product problem. we analyze an extremely simple divide and conquer algorithm that uses a balanced cut subroutine with approximation ratio &beta; to recursively partition the graph. our analysis shows that this approach gives an approximation ratio of o(&beta;) for the minimum linear arrangement problem with exponent &alpha; for any fixed &alpha; &epsilon; (0, 1).
approximation algorithms for node-weighted buy-at-bulk network design. we present algorithms with poly-logarithmic approximation ratios for the buy-at-bulk network design problem in the node-weighted setting. we obtain the following results where h is the number of pairs in the input. &bull; on o(log h) approximation for the single-sink non-uniform buy-at-bulk network design. unless p = np this ratio is tight up to constant factors. &bull; an o(log4 h) approximation for the multi-commodity non-uniform buy-at-bulk network design problem.
approximate shortest paths in anisotropic regions. our goal is to find an approximate shortest path for a point robot moving in a planar subdivision with n vertices. let &rho; &ge; 1 be a real number. distances in each face of this subdivision are measured by a convex distance function whose unit disk is contained in a concentric unit euclidean disk, and contains a concentric euclidean disk with radius 1/&rho;. different convex distance functions may be used for different faces, and obstacles are allowed. these convex distance functions may be asymmetric. for all &epsilon; &isin; (0, 1), and for any two points vs and vd, we give an algorithm that finds a path from vs to vd whose cost is at most (1 + &epsilon;) times the minimum cost. our algorithm runs in o (&rho;2log&rho;/&epsilon;2n3 log (&rho;n/&epsilon;)) time. this bound does not depend on any other parameters; in particular, it does not depend on the minimum angle in the subdivision. we give applications to two special cases that have been considered before: the weighted region problem and motion planning in the presence of uniform flows. for the weighted region problem with weights in [1, &rho;] &cup; {&infin;}, the time bound of our algorithm improves to o (&rho;2log&rho;/&epsilon;n3 log (&rho;n/&epsilon;)).
convergence to approximate nash equilibria in congestion games. we study the ability of decentralized, local dynamics in non-cooperative games to rapidly reach an approximate nash equilibrium. for symmetric congestion games in which the edge delays satisfy a "bounded jump" condition, we show that convergence to an &epsilon;-nash equilibrium occurs within a number of steps that is polynomial in the number of players and &epsilon;-1. this appears to be the first such result for a class of games that includes examples for which finding an exact nash equilibrium is pls-complete, and in which shortest paths to an exact equilibrium are exponentially long. we show moreover that rapid convergence holds even under only the apparently minimal assumption that no player is excluded from moving for arbitrarily many steps. we also prove that, in a generalized setting where players have different "tolerances" &epsilon;i that specify their thresholds in the approximate nash equilibrium, the number of moves made by a player before equilibrium is reached depends only on his associated &epsilon;i, and not on those of the other players. finally, we show that polynomial time convergence still holds even when a bounded number of edges are allowed to have arbitrary delay functions.
a lower bound for scheduling mechanisms. we study the mechanism design problem of scheduling tasks on n unrelated machines in which the machines are the players of the mechanism. the problem was proposed and studied in the seminal paper of nisan and ronen on algorithmic mechanism design, where it was shown that the approximation ratio of mechanisms is between 2 and n. we improve the lower bound to $1+\sqrt{2}$for 3 or more machines.
testing for a theta. in this paper we survey some known results on the question of testing whether a given graph contains certain induced subgraphs. we also present a new algorithm, to test if a graph contains a special kind of an induced subgraph, called a "theta"
on testable properties in bounded degree graphs. we study graph properties which are testable for bounded degree graphs in time independent of the input size. our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. it is believed that almost all, even very simple graph properties require a large complexity to be tested for arbitrary (bounded degree) graphs. therefore in this paper we focus our attention on testing graph properties for special classes of graphs. we call a graph family non-expanding if every graph in this family is not a weak expander (its expansion is o(1/log2 n), where n is the graph size). a graph family is hereditary if it is closed under vertex removal. similarly, a graph property is hereditary if it is closed under vertex removal. next, we call a graph property &pi; to be testable for a graph family f if for every graph g &epsilon; f, in time independent of the size of g we can distinguish between the case when g satisfies property &pi; and when it is far from every graph satisfying property &pi;. in this paper we prove that in the bounded degree graph model, any hereditary property is testable if the input graph belongs to a hereditary and non-expanding family of graphs. as an application, our result implies that, for example, any hereditary property (e.g., k-colorability, h-freeness, etc.) is testable in the bounded degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. no such results have been known before and prior to our work, in the bounded degree graph model very few graph properties have been known to be testable for any graph classes.
spectral clustering with limited independence. this paper considers the well-studied problem of clustering a set of objects under a probabilistic model of data in which each object is represented as a vector over the set of features, and there are only k different types of objects. in general, earlier results (mixture models and "planted" problems on graphs) often assumed that all coordinates of all objects are independent random variables. they then appeal to the theory of random matrices in order to infer spectral properties of the feature x object matrix. however, in most practical applications, assuming full independence is not realistic. instead, we only assume that the objects are independent, but the coordinates of each object may not be. we first generalize the required results for random matrices to this case of limited independence using some new techniques developed in functional analysis. surprisingly, we are able to prove results that are quite similar to the fully independent case modulo an extra logarithmic factor. using these bounds, we develop clustering algorithms for the more general mixture models. our clustering algorithms have a substantially different and perhaps simpler "clean-up" phase than known algorithms. we show that our model subsumes not only the planted partition random graph models, but also another set of models under which there is a body of clustering algorithms, namely the gaussian and log-concave mixture models.
probabilistic analysis of linear programming decoding. we initiate the probabilistic analysis of linear programming (lp) decoding of low-density parity-check (ldpc) codes. specifically, we show that for a random ldpc code ensemble, the linear programming decoder of feld-man et al. succeeds in correcting a constant fraction of errors with high probability. the fraction of correctable errors guaranteed by our analysis surpasses all prior non-asymptotic results for ldpc codes, and in particular exceeds the best previous finite-length result on lp decoding by a factor greater than ten. this improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. at the core of our analysis is a novel combinatorial characterization of lp decoding success, based on the notion of a generalized matching. an interesting by-product of our analysis is to establish the existence of "almost expansion" in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, with expansion coefficients much larger than the classical case.
approximation algorithms via contraction decomposition. we prove that the edges of every graph of bounded (euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth (where the bound depends on k). this decomposition result parallels an analogous, simpler result for edge deletions instead of contractions, obtained in [bak94, epp00, ddo+04, dhk05], and it generalizes a similar result for "compression" (a variant of contraction) in planar graphs [kle05]. our decomposition result is a powerful tool for obtaining ptass for contraction-closed problems (whose optimal solution only improves under contraction), a much more general class than minor-closed problems. we prove that any contraction-closed problem satisfying just a few simple conditions has a ptas in bounded-genus graphs. in particular, our framework yields ptass for the weighted traveling salesman problem and for minimum-weight c-edge-connected submultigraph on bounded-genus graphs, improving and generalizing previous algorithms of [gkp95, agk+98, kle05, gri00, cgsz04, bcgz05]. we also highlight the only main difficulty in extending our results to general h-minor-free graphs.
multiple choice tries and distributed hash tables. in this article we consider tries built from n strings such that each string can be chosen from a pool of k strings, each of them generated by a discrete i.i.d. source. three cases are considered: k = 2, k is large but fixed, and k ~ clog n. the goal in each case is to obtain tries as balanced as possible. various parameters such as height and fill-up level are analyzed. it is shown that for two-choice tries a 50% reduction in height is achieved when compared with ordinary tries. in a greedy online construction when the string that minimizes the depth of insertion for every pair is inserted, the height is only reduced by 25&percnt;. to further reduce the height by another 25%, we design a more refined online algorithm. the total computation time of the algorithm is o(nlog n). furthermore, when we choose the best among k &ge; 2 strings, then for large but fixed k the height is asymptotically equal to the typical depth in a trie. finally, we show that further improvement can be achieved if the number of choices for each string is proportional to log n. in this case highly balanced trees can be constructed by a simple greedy algorithm for which the difference between the height and the fill-up level is bounded by a constant with high probability. this, in turn, has implications for distributed hash tables, leading to a randomized id management algorithm in peer-to-peer networks such that, with high probability, the ratio between the maximum and the minimum load of a processor is o(1). &copy; 2008 wiley periodicals, inc. random struct. alg., 2009
equilibria in online games. we initiate the study of scenarios that combine online decision making with interaction between non-cooperative agents. to this end we introduce online games that model such scenarios as non-cooperative games, and lay the foundations for studying this model. roughly speaking, an online game captures systems in which independent agents serve requests in a common environment. the requests arrive in an online fashion and each is designated to be served by a different agent. the cost incurred by serving a request is paid for by the serving agent, and naturally, the agents seek to minimize the total cost they pay. since the agents are independent, it is unlikely that some central authority can enforce a policy or an algorithm (centralized or distributed) on them, and thus, the agents can be viewed as selfish players in a non-cooperative game. in this game, the players have to choose as a strategy an online algorithm according to which requests are served. to further facilitate the game theoretic approach, we suggest the measure of competitive analysis as the players' decision criterion. as the expected result of non-cooperative games is an equilibrium, the question of finding the equilibria of a game is of central importance, and thus, it is the central issue we concentrate on in this paper. we study some natural examples for online games; in order to obtain general insights and develop generic techniques, we present an abstract model for the study of online games generalizing metrical task systems. we suggest a method for constructing equilibria in this model and further devise techniques for implementing it.
considering suppressed packets improves buffer management in qos switches. the following buffer management problem arises in network switches providing differentiated services: at the beginning of each time step, one packet can be sent, and afterwards an arbitrary number of new packets arrive. packets that are not sent can be stored in a buffer. each packet is attributed by a deadline, and a packet is automatically deleted from the buffer if it is still stored in the buffer by the end of its deadline. the differentiated service model is abstracted by attributing each packet with a value according to its service level. a buffer management strategy determines the packet to be sent in each time step. the goal of a buffer management strategy is to maximize the sum of the values of sent packets. we introduce the concept of suppressed packets and present a deterministic strategy that is based on this concept. we show that this strategy achieves a competitive ratio of 2&radic;2--1 &ap; 1.828, which is the best known competitive ratio in the deterministic case. further, we present a memoryless version of this strategy that achieves a competitive ratio of &ap; 1.893. this is the first memoryless strategy that achieves a competitive ratio less than 2, and the competitive ratio of this strategy is even better than the ratios of all previously known deterministic strategies. this demonstrates the potential of the concept of suppressed packets. in addition, we present a simple strategy that achieves the optimal competitive ratio of min{(1 + &alpha;)/&alpha;, 2&alpha;/(&alpha;+1)} &le; &radic;2, if only two packet values 1 and &alpha; > 1 are possible.
graph balancing: a special case of scheduling unrelated parallel machines. we design a 1.75-approximation algorithm for a special case of scheduling parallel machines to minimize the makespan, namely the case where each job can be assigned to at most two machines with the same processing time on either machine. (this is a special case of so-called restricted assignment, where the set of eligible machines can be arbitrary for each job.) we also show that even for this special case it is np-hart to compute better than 1.5 approximation. this is the first improvement of the approximation ratio 2 of lenstra, shmoys, and tardos [approximation algorithms for scheduling unrelated parallel machines, math. program. 46:259--271, 1990], for any special case with unbounded number of machines. our lower bound yields the same ratio as their bound which works for restricted assignment, and which is still the state-of-the-art lower bound even for the most general case.
resilient search trees. we investigate the problem of computing in a reliable fashion in the presence of faults that may arbitrarily corrupt memory locations. in this framework, we focus on the design of resilient data structures, i.e., data structures that, despite the corruption of some memory values during their lifetime, are nevertheless able to operate correctly (at least) on the set of uncorrupted values. in particular, we present resilient search trees which achieve optimal time and space bounds while tolerating up to o(&radic;log n) memory faults, where n is the current number of items in the search tree. in more detail, our resilient search trees are able to insert, delete and search for a key in o(log n + &delta;2) amortized time, where &delta; is an upper bound on the total number of faults. the space required is o(n + &delta;).
analytic combinatorics: a calculus of discrete structures. the efficiency of many discrete algorithms crucially depends on quantifying properties of large structured combinatorial configurations. we survey methods of analytic combinatorics that are simply based on the idea of associating numbers to atomic elements that compose combinatorial structures, then examining the geometry of the resulting functions. in this way, an operational calculus of discrete structures emerges. applications to basic algorithms, data structures, and the theory of random discrete structures are outlined.