waashk/dblp huggingface dataset:
network sketching or: "how much geometry hides in connectivity?--part ii". wireless sensor networks typically consist of small, very simple network nodes without any positioning device like gps. after an initialization phase, the nodes know with whom they can talk directly, but have no idea about their relative geographic locations. we examine how much geometry information is nevertheless hidden in the communication graph of the network: assuming that the connectivity is determined by the well-known unit-disk graph model, we show that using a very simple distributed algorithm we can identify a large, provably planar subgraph of the communication graph that faithfully reflects the topology of the network. this planar subgraph can then be embedded using a simple distributed rubber-banding procedure, finally obtaining virtual coordinates for the nodes of the subgraph which can be instrumented for various protocols based on geographic location information. that is, there is enough geometry information hidden in the connectivity structure not only to identify topological features like network holes (as it was also exhibited in the predecessor paper [7]) but even enough information to compute a sketch of the network layout. our simulation results indicate that the algorithm works very well even for very sparse network deployments and produces network sketches that come close to the original layout.
torpid mixing of local markov chains on 3-colorings of the discrete torus. we study local markov chains for sampling 3-colorings of the discrete torus tl, d = {0, ..., l--1}d. we show that there is a constant &rho; &ap; .22 such that for all even l &ge; 4 and d sufficiently large, certain local markov chains require exponential time to converge to equilibrium. more precisely, if m is a markov chain on the set of proper 3-colorings of tl, d that updates the color of at most &rho;ld vertices at each step and whose stationary distribution is uniform, then the convergence to stationarity of m is exponential in ld-1. our proof is based on a conductance argument that builds on sensitive new combinatorial enumeration techniques.
correlation decay and deterministic fptas for counting list-colorings of a graph. we propose a deterministic algorithm for approximately counting the number of list colorings of a graph. under the assumption that the graph is triangle free, the size of every list is at least &alpha;&delta;, where &alpha; is an arbitrary constant bigger than &alpha; = 2.8432 ..., the solution of &alpha;e-1/&alpha; = 2, and &alpha; is the maximum degree of the graph, we obtain the following results. for the case when the size of the each list is a large constant, we show the existence of a deterministic fptas for computing the total number of list colorings. the same deterministic algorithm has complexity 2o(log2 n) without any assumptions on the sizes of the lists, where n is the size of the instance. our results are not based on the most powerful existing counting technique - rapidly mixing markov chain method. rather we build upon concepts from statistical physics, in particular, the decay of correlation phenomena and its implication for the uniqueness of gibbs measures in infinite graphs. this approach was proposed in two recent papers [bg06] and [wei05]. the principle insight of the present work is that the correlation decay property can be established with respect to certain computation tree, as opposed to the conventional correlation decay property which is typically established with respect to graph theoretic neighborhoods of a given node. this allows truncation of computation at a logarithmic depth in order to obtain polynomial accuracy in polynomial time. while the analysis conducted in this paper is limited to the problem of counting list colorings, the proposed algorithm can be extended to an arbitrary constraint satisfaction problem in a straightforward way.
optimal dynamic vertical ray shooting in rectilinear planar subdivisions. we consider the dynamic vertical ray shooting problem against horizontal disjoint segments, that is, the task of maintaining a dynamic set s of n nonintersecting horizontal line segments in the plane under a query that reports the first segment in s intersecting a vertical ray from a query point. we develop a linear-size structure that supports queries, insertions, and deletion in o(log n) worst-case time. our structure works in the comparison model on a random access machine.
model-driven optimization using adaptive probes. in several applications such as databases, planning, and sensor networks, parameters such as selectivity, load, or sensed values are known only with some associated uncertainty. the performance of such a system (as captured by some objective function over the parameters) is significantly improved if some of these parameters can be probed or observed. in a resource constrained situation, deciding which parameters to observe in order to optimize system performance itself becomes an interesting and important optimization problem. this problem is the focus of this paper. unfortunately designing optimal observation schemes is np-hard even for the simplest objective functions, leading to the study of approximation algorithms. in this paper we present general techniques for designing non-adaptive probing algorithms which are at most a constant factor worse than optimal adaptive probing schemes. interestingly, this shows that for several problems of interest, while probing yields significant improvement in the objective function, being adaptive about the probing is not beneficial beyond constant factors.
competitive queue management for latency sensitive packets. we consider the online problem of non-preemptive queue management. an online sequence of packets arrive, each of which has an associated intrinsic value. packets can be accepted to a fifo queue, or discarded. the profit gained by transmitting a packet diminishes over time and is equal to its value minus the delay. this corresponds to the well known and strongly motivated naor's model in operations research. we give a queue management algorithm with a competitive ratio equal to the golden ratio (&phi; &ap; 1.618) in the case that all packets have the same value, along with a matching lower bound. we also derive &theta;(1) upper and lower bounds on the competitive ratio when packets have different intrinsic values (in the case of differentiated services). we can extend our results to deal with more general models for loss of value over time. finally, we re-interpret our online algorithms in the context of selfish agents, producing an online mechanism that approximates the optimal social welfare to within a constant factor.
improved bounds for the symmetric rendezvous value on the line. a notorious open problem in the field of rendezvous search is to decide the rendezvous value of the symmetric rendezvous search problem on the line, when the initial distance between the two players is two. we show that the symmetric rendezvous value is within the interval (4.1520, 4.2574), which considerably improves the previous best-known result (3.9546, 4.3931). to achieve the improved bounds, we call upon results from absorbing markov chain theory and mathematical programming theory---particularly fractional quadratic programming and semidefinite programming. moreover, we also establish some important properties of this problem, which could be of independent interest and useful for resolving this problem completely. finally, we conjecture that the symmetric rendezvous value is asymptotically equal to 4.25 based on our numerical calculations.
efficient algorithms for computing all low edge connectivities and related problems. given an undirected unweighted graph g = (v, e) and an integer k &ge; 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. we present an algorithm with expected running time &otilde;(m + nk3) for this problem, where |v| = n and |e| = m. our output is a weighted tree t whose nodes are the sets v1, v2,..., v l of a partition of v, with the property that the edge connectivity in g between any two vertices s &epsilon; vi and t &epsilon; vj, for i &ne; j, is equal to the weight of the lightest edge on the path between vi and vj in t. also, two vertices s and t belong to the same vi for any i if and only if they have an edge connectivity greater than k. currently, the best algorithm for this problem needs to compute all-pairs min-cuts in an o(nk) edge graph; this takes &otilde;(m + n5/2kmin{k1/2, n1/6}) time. our algorithm is much faster for small values of k; in fact, it is faster whenever k is o(n5/6). our algorithm yields the useful corollary that in &otilde;(m + nc3) time, where c is the size of the global min-cut, we can compute the edge connectivities of all those pairs of vertices whose edge connectivity is at most &alpha;c for some constant &alpha;. we also present an &otilde;(m + n) monte carlo algorithm for the approximate version of this problem. this algorithm is applicable to weighted graphs as well. our algorithm, with some modifications, also solves another problem called the minimum t-cut problem. given t &sube; v of even cardinality, we present an &otilde;(m + nk3) algorithm to compute a minimum cut that splits t into two odd cardinality components, where k is the size of this cut.
maximum -flow with crossings in ( log ) time. there is a large body of results on planar graph algorithms that are more efficient than the best known algorithm for general graphs [13]. maximum flow [1] is but one example. more drastically, the maximum cut problem is polynomially solvable for planar instances but np-complete in general [12, 8, 5]. however, little is known about nearly planar graphs. this is unsatisfactory since the nearly planar case is particularly important in practice. think for example of road networks with bridges and tunnels. we present a preflow push algorithm that solves the maximum s-t-flow problem in a network with n vertices and m edges and embedded with k crossings in time o(k3n log n) worst case. to our knowledge there is only one previous result that relates asymptotic running time to a topological parameter of the graph such that the running time is polynomial in this parameter. compared with the currently fastest maximum flow algorithms this reduces the worst case running time by a factor of m/k3 ignoring logarithmic factors. therefore, it is particularly favorable for very sparse or nearly planar graphs.
digraph measures: kelly decompositions, games, and orderings. we consider various well-known, equivalent complexity measures for graphs such as elimination orderings, k-trees and cops and robber games and study their natural translations to digraphs. we show that on digraphs the translations of these measures are also equivalent and induce a natural connectivity measure. we introduce a decomposition for digraphs and an associated width, kelly-width, which is equivalent to the aforementioned measure. we demonstrate its usefulness by exhibiting potential applications including polynomial-time algorithms for np-complete problems on graphs of bounded kelly-width, and complexity analysis of asymmetric matrix factorization. finally, we compare the new width to other known decompositions of digraphs.
a 1.875: approximation algorithm for the stable marriage problem. we consider the problem of finding a stable matching of maximum size when both ties and unacceptable partners are allowed in preference lists. this problem is known to be apx-hard, and the current best known approximation algorithm achieves the approximation ratio 2-c 1/&radic;n, where c is some positive constant. in this paper, we give a 1.875-approximation algorithm, which is the first result on the approximation ratio better than two.
the independent even factor problem. this paper deals with the independent even factor problem, which generalizes both of the matching problem and the matroid intersection problem. for odd-cycle-symmetric digraphs, in which each arc in any odd dicycle has the reverse arc, a min-max formula is established as a common generalization of the tutte-berge formula for matchings and the min-max formula of edmonds (1970) for matroid intersection. we devise a combinatorial efficient algorithm to find a maximum independent even factor in an odd-cycle-symmetric digraph, which commonly extends two of the alternating-path type algorithms, the even factor algorithm of pap (2005) and the matroid intersection algorithms. this algorithm gives a constructive proof of the min-max formula, and contains a new operation on matroids, which corresponds to shrinking factor-critical components in the matching algorithm of edmonds (1965). the running time of the algorithm is o(n4q), where n is the number of vertices and q is the time for an independence test. the algorithm also gives a common generalization of the edmonds-gallai decomposition for matchings and the principal partition for matroid intersection.
ultra-succinct representation of ordered trees. there exist two well-known succinct representations of ordered trees: bp (balanced parenthesis) [munro, raman 2001] and dfuds (depth first unary degree sequence) [benoit et al. 2005]. both have size 2n + o(n) bits for n-node trees, which asymptotically matches the information-theoretic lower bound. many fundamental operations on trees can be done in constant time on word ram, for example finding the parent, the first child, the next sibling, the number of descendants, etc. however there has been no single representation supporting every existing operation in constant time; bp does not support i-th child, while dfuds does not support lca (lowest common ancestor). in this paper, we give the first succinct tree representation supporting every one of the fundamental operations previously proposed for bp or dfuds along with some new operations in constant time. moreover, its size surpasses the information-theoretic lower bound and matches the entropy of the tree based on the distribution of node degrees. we call this an ultra-succinct data structure. as a consequence, a tree in which every internal node has exactly two children can be represented in n + o(n) bits. we also show applications for ultra-succinct compressed suffix trees and labeled trees.
efficient aggregation algorithms for probabilistic data. we study the problem of computing aggregation operators on probabilistic data in an i/o efficient manner. algorithms for aggregation operators such as sum, count, avg, and min/max are crucial to applications on probabilistic databases. we give a generalization of the classical data stream model to handle probabilistic data, called probabilistic streams, in order to analyze the i/o-requirements of our algorithms. whereas the algorithms for sum and count turn out to be simple, the problem is harder for both avg and min/max. although data stream algorithms typically use randomness, all of the algorithms we present are deterministic. for min and max, we obtain efficient one-pass data stream algorithms for estimating each of these quantities with relative accuracy (1 + &epsilon;), using constant update time per element and o(1/&epsilon; lg r) space, where each element has a value between 1 and r. for avg, we present a new data stream algorithm for estimating its value to a relative accuracy (1 + &epsilon;) in o(log n) passes over the data with o(1/&epsilon; log2 n) space and update time o(1/&epsilon; log n) per element. on the other hand, we prove a space lower bound of &omega;(n) for any exact one-pass deterministic data stream algorithm. complementing this result, we also present an o(n log2 n)-time exact deterministic algorithm which uses o(n) space (thus removing the data-streaming restriction), improving dramatically on the previous o(n3)-time algorithm. our algorithms for avg involve a novel technique based on generating functions and numerical integration, which may be of independent interest. finally, we provide an experimental analysis and show that our algorithms, coupled with additional heuristics, have excellent performance over large data sets.
games of fixed rank: a hierarchy of bimatrix games. we propose and investigate bimatrix games, whose (entry-wise) sum of the pay-off matrices of the two players is of rank k, where k is a constant. we will say the rank of such a game is k. for every fixed k, the class of rank k-games strictly generalizes the class of zero-sum games, but is a very special case of general bimatrix games. we show that even for k = 1 the set of nash equilibria of these games can consist of an arbitrarily large number of connected components. while the question of exact polynomial time algorithms to find a nash equilibrium remains open for games of fixed rank, we can provide a deterministic polynomial time algorithm for finding an &epsilon;-approximation (whose running time is polynomial in 1\&epsilon;) as well as a randomized polynomial time approximation algorithm (whose running time is similar), but which offers the possibility of finding an exact solution in polynomial time if a conjecture is valid. the latter algorithm is based on a new application of random sampling methods to quadratic optimization problems of fixed rank.
recognizing partial cubes in quadratic time. we show how to test whether a graph with n vertices and m edges is a partial cube, and if so how to find a distance-preserving embedding of the graph into a hypercube, in the near-optimal time bound o(n2), improving previous o(nm)-time solutions.
noisy binary search and its applications. we study a noisy version of the classic binary search problem of inserting an element into its proper place within an ordered sequence by comparing it with elements of the sequence. in the noisy version we can not compare elements directly. instead we are given a coin corresponding to each element of the sequence, such that as one goes through the ordered sequence the probability of observing heads when tossing the corresponding coin increases. we design online algorithms which adaptively choose a sequence of experiments, each consisting of tossing a single coin, with the goal of identifying the highest-numbered coin in the ordered sequence whose heads probability is less than some specified target value. possible applications of such algorithms include investment planning, sponsored search advertising, admission control in queueing networks, college admissions, and admitting new members into an organization ranked by ability, such as a tennis ladder.
optimal scale-free compact routing schemes in networks of low doubling dimension. we present optimal-stretch scale-free compact routing schemes for networks of low doubling dimension, in both the name-independent and name-dependent models. our name-independent algorithm is the first scale-free name-independent compact routing scheme to achieve asymptotically optimal stretch, closing the gaps left by the work of abraham et al. (icdcs'06) and konjevod et al. (podc'06). our name-dependent algorithm is the first scale-free optimal-stretch name-dependent compact routing scheme that uses optimal [log n]-bit routing labels, in spite of the limited routing label information. we define a simple hierarchical decomposition technique based on ball-packings. our algorithms rely on a novel combination of ball-packings and hierarchical r-nets, which we see as a contribution in its own right.
better online buffer management. as the internet becomes more mature, there is a realization that improving the performance of routers has the potential to substantially improve internet performance in general. currently, most routers forward packets in a first-in-first-out (fifo) order. however, the diversity of applications supported by modern ip-based networks has resulted in unpredictable packet flows, and heterogeneous network traffic. thus, it is becoming more reasonable to consider differentiating between different types of packets, and perhaps to consider allowing packets to specify a deadline by which it must be processed. these issues have made buffer management at routers a critical issue in providing effective quality of service to the various applications that use the network. in this paper, we study an online problem in which each packet is described by its discrete arrival time, non-negative weight and discrete deadline; arriving packets are buffered for delivery and all packets have the same processing time. the packets arrive online, and our objective is to maximize the sum of weights of those packets that are sent by their deadlines. we describe an online deterministic algorithm with a competitive ratio of 1.854, improving the best previous known competitive ratio of 1.939 (bartal et al. stacs 2004). the algorithmic framework we use has several interesting features. first, we do not use a potential function. instead, after each step we modify the adversary's buffer. second, we introduce "dummy packets" to facilitate the decision making.
online vertex colorings of random graphs without monochromatic subgraphs. consider the following generalized notion of graph colorings: a vertex coloring of graph g is valid w.r.t. some fixed nonempty graph f if no color class induces a copy of f in g, i.e., there is no monochromatic copy of f in g. we propose and analyze an algorithm for computing valid colorings of a random graph gn, p on n vertices with edge probability p in an online fashion. for a large family of graphs f including cliques and cycles of arbitrary size, the proposed algorithm is optimal in the following sense: for any integer r &ge; 1, there is a constant &beta; = &beta;(f, r) such that the algorithm a.a.s. (asymptotically almost surely) computes a valid r-coloring of gn, p w.r.t. f online if p &lt; n-&beta;, and any online algorithm will a.a.s. fail to do so if p &gt; n-&beta;. that is, we observe a threshold phenomenon determined by the function n-&beta;.
counting good truth assignments of random -sat formulae. we present a deterministic approximation algorithm to compute logarithm of the number of 'good' truth assignments for a random k-satisfiability (k-sat) formula in polynomial time (by 'good' we mean that violates a small fraction of clauses). the relative error is bounded above by an arbitrarily small constant &epsilon; with high probability1 as long as the clause density (ratio of clauses to variables) &alpha; < &alpha;u(k) = 2k-1logk(1 + o(1)). the algorithm is based on computation of marginal distribution via belief propagation and use of an interpolation procedure. this scheme substitutes the traditional one based on approximation of marginal probabilities via mcmc, in conjunction with self-reduction, which is not easy to extend to the present problem. our results are expected hold for a reasonable non-random setup with locally tree-like sparse k-sat formulas. we derive 2k-1 log k(1+o(1)) as threshold for uniqueness of the gibbs distribution on satisfying assignment of random infinite tree k-sat formulae to establish our results, which is of interest in its own right.