waashk/dblp huggingface dataset:
accelerating simulated annealing for the permanent and combinatorial counting problems. we present an improved &ldquo;cooling schedule&rdquo; for simulated annealing algorithms for combinatorial counting problems. under our new schedule the rate of cooling accelerates as the temperature decreases. thus, fewer intermediate temperatures are needed as the simulated annealing algorithm moves from the high temperature (easy region) to the low temperature (difficult region). we present applications of our technique to colorings and the permanent (perfect matchings of bipartite graphs). moreover, for the permanent, we improve the analysis of the markov chain underlying the simulated annealing algorithm. this improved analysis, combined with the faster cooling schedule, results in an $o(n^7\log^4{n})$ time algorithm for approximating the permanent of a $0/1$ matrix.
torpid mixing of simulated tempering on the potts model. simulated tempering and swapping are two families of sampling algorithms in which a parameter representing temperature varies during the simulation. the hope is that this will overcome bottlenecks that cause sampling algorithms to be slow at low temperatures. madras and zheng demonstrate that the swapping and tempering algorithms allow efficient sampling from the low-temperature mean-field ising model, a model of magnetism, and a class of symmetric bimodal distributions [10]. local markov chains fail on these distributions due to the existence of bad cuts in the state space.bad cuts also arise in the q-state potts model, another fundamental model for magnetism that generalizes the ising model. glauber (local) dynamics and the swendsen-wang algorithm have been shown to be prohibitively slow for sampling from the potts model at some temperatures [1, 2, 6]. it is reasonable to ask whether tempering or swapping can overcome the bottlenecks that cause these algorithms to converge slowly on the potts model.we answer this in the negative, and give the first example demonstrating that tempering can mix slowly. we show this for the 3-state ferromagnetic potts model on the complete graph, known as the mean-field model. the slow convergence is caused by a first-order (discontinuous) phase transition in the underlying system. using this insight, we define a variant of the swapping algorithm that samples efficiently from a class of bimodal distributions, including the mean-field potts model.
tight bounds for on-line tree embeddings. tree-structured computations are relatively easy to process in parallel. as leaf processes are recursively spawned they can be assigned to independent processors in a multicomputer network. however, to achieve good performance the on-line mapping algorithm must maintain load balance, i.e., distribute processes equitably among processors. additionally, the algorithm itself must be distributed in nature, and process allocation must be completed via message-passing with minimal communication overhead.this paper investigates bounds on the performance of deterministic and randomized algorithms for on-line tree embeddings. in particular, we study trade-offs between computation overhead (load imbalance) and communication overhead (message congestion). we give a simple technique to derive lower bounds on the congestion that any on-line allocation algorithm must incur in order to guarantee load balance. this technique works for both randomized and deterministic algorithms. we prove that the advantage of randomization is limited. optimal bounds are achieved for several networks, including multidimensional grids and butterflies.
simpler algorithm for estimating frequency moments of data streams. the problem of estimating the kth frequency moment fk over a data stream by looking at the items exactly once as they arrive was posed in [1, 2]. a succession of algorithms have been proposed for this problem [1, 2, 6, 8, 7]. recently, indyk and woodruff [11] have presented the first algorithm for estimating fk, for k > 2, using space &otilde;(n1-2/k), matching the space lower bound (up to poly-logarithmic factors) for this problem [1, 2, 3, 4, 13] (n is the number of distinct items occurring in the stream.) in this paper, we present a simpler 1-pass algorithm for estimating fk.
learning deterministic finite automata from smallest counterexamples. we show in this paper (which appeared in a preliminary form as an extended abstract in [proceedings of the 9th international acm--siam symposium on discrete algorithms, acm, 1998]) that deterministic finite automata (dfas) with n states and input alphabet $\sigma$ can efficiently be learned from less than $|\sigma|n^2$ smallest counterexamples. this improves on an earlier result of ibarra and jiang who required $|\sigma|n^3$ smallest counterexamples. we present a general strategy which learns a finite concept class ${\cal f}$ from $\lfloor\log{\cal f}\rfloor$ smallest counterexamples (but not necessarily efficiently). an application to dfas with at most $n$ states shows that $(1+o(1))|\sigma|n\log n$ smallest counterexamples are sufficient (if efficiency is not an issue). we show next that the special dfas operating on input words of an arbitrary but fixed length (the so-called leveled dfas) are efficiently learnable from $(1+o(1))|\sigma|n\log n$ smallest counterexamples. this improves on an earlier result of ibarra and jiang who required $|\sigma|n^2$ smallest counterexamples. furthermore, we present a general lower bound on the number of smallest counterexamples (required by any learning algorithm). this bound can be stated in terms of a (new) combinatorial dimension associated with the target class. a computation of this dimension for leveled or arbitrary dfas leads to a lower bound of the form $(\frac{1}{4}+o(1))|\sigma|n\log n$. this bound matches the aforementioned upper bounds modulo a constant of approximately 4. finally, we present a general conversion of algorithms learning from smallest counterexamples into algorithms performing self-directed learning. for the particular classes of leveled or arbitrary dfas, this conversion leads to self-directed learners making the smallest possible number of mistakes (modulo a constant of approximately 4). a similar remark is valid for the class of multiplicity automata (mas).
compact representations of ordered sets. we consider the problem of efficiently representing sets s of size n from an ordered universe u = {0,...,m-1}. given any ordered dictionary structure (or comparison-based ordered set structure) d that uses o(n) pointers, we demonstrate a simple blocking technique that produces an ordered set structure supporting the same operations in the same time bounds but with o(n log m+n/n) bits. this is within a constant factor of the information-theoretic lower bound. we assume the unit cost ram model with word size &omega;(log |u|) and a table of size o(m&alpha; log2 m) bits, for some constant &alpha; > 0. the time bound for our operations contains a factor of 1/&alpha;.we present experimental results for the stl (c++ standard template library) implementation of red-black trees, and for an implementation of treaps. we compare the implementations with blocking and without blocking. the blocking variants use a factor of between 1.5 and 10 less space depending on the density of the set.
dictionaries using variable-length keys and data, with applications. we consider the problem of maintaining a dynamic dictionary in which both the keys and the associated data are variable-length bit-strings. we present a dictionary structure based on hashing that supports constant time lookup and expected amortized constant time insertion and deletion. to store the key-data pairs (s1, t1) ... (sn, tn), our dictionary structure uses o(m) bits where m = &sigma;(max(|si| -- log n, 1) + |ti| and |si| is the length of bit string si. we assume a word length w > log m.we present several applications, including representations for semi-dynamic graphs, ordered sets for integers in a bounded range, cardinal trees with varying cardinality, and simplicial meshes of k dimensions. these results either generalize or simplify previous results.
compact representations of separable graphs. we consider the problem of representing graphs compactly while supporting queries efficiently. in particular we describe a data structure for representing n-vertex unlabeled graphs that satisfy an o(nc)-separator theorem, c < 1. the structure uses o(n) bits, and supports adjacency and degree queries in constant time, and neighbor listing in constant time per neighbor. this generalizes previous results for graphs with constant genus, such as planar graphs.we present experimental results using many "real world" graphs including 3-dimensional finite element meshes, link graphs of the web, internet router graphs, vlsi circuits, and street map graphs. compared to adjacency lists, our approach reduces space usage by almost an order of magnitude, while supporting depthfirst traversal in about the same running time.
an 8/13-approximation algorithm for the asymmetric maximum tsp. we present a polynomial time approximation algorithm for the asymmetric maximum traveling salesperson problem that achieves performance ratio 8/13 (1 - 1/n). the running time of our algorithm is o(n3).
a new approximation algorithm for the asymmetric tsp with triangle inequality. we present a polynomial time factor 0.999 &cdot; log n approximation algorithm for the asymmetric traveling salesperson problem with triangle inequality.
space-efficient finger search on degree-balanced search trees. we show how to support the finger search operation on degree-balanced search trees in a space-efficient manner that retains a worst-case time bound of o(log d), where d is the difference in rank between successive search targets. while most existing tree-based designs allocate linear extra storage in the nodes (e.g., for side links and parent pointers), our design maintains a compact auxiliary data structure called the "hand" during the lifetime of the tree and imposes no other storage requirement within the tree.the hand requires o(log n) space for an n-node tree and has a relatively simple structure. it can be updated synchronously during insertions and deletions with time proportional to the number of structural changes in the tree. the auxiliary nature of the hand also makes it possible to introduce finger searches into any existing implementation without modifying the underlying data representation (e.g., any implementation of red-black trees can be used). together these factors make finger searches more appealing in practice.our design also yields a simple yet optimal in-order walk algorithm with worst-case o(1) work per increment (again without any extra storage requirement in the nodes), and we believe our algorithm can be used in database applications when the overall performance is very sensitive to retrieval latency.
static optimality and dynamic search-optimality in lists and trees. adaptive data structures form a central topic of on-line algorithms research, beginning with the results of sleator and tarjan showing that splay trees achieve static optimality for search trees, and that move-to-front is constant competitive for the list update problem [st85a, st85b]. this paper is inspired by the observation that one can in fact achieve a 1 + &epsilon; ratio against the best static object in hindsight for a wide range of data structure problems via "weighted experts" techniques from machine learning, if computational decision-making costs are not considered.in this paper, we give two results. first, we show that for the case of lists, we can achieve a 1 + &epsilon; ratio with respect to the best static list in hindsight, by a simple efficient algorithm. this algorithm can then be combined with existing results to simultaneously achieve good static and dynamic bounds. second, for trees, we show a (computationally inefficient) algorithm that achieves what we call "dynamic search optimality": dynamic optimality if we allow the online algorithm to make free rotations after each request. we hope this to be a step towards solving the longstanding open problem of achieving true dynamic optimality for trees.
smoothed analysis of the perceptron algorithm for linear programming. the smoothed complexity [1] of an algorithm is the expected running time of the algorithm on an arbitrary instance under a random perturbation. it was shown recently that the simplex algorithm has polynomial smoothed complexity. we show that a simple greedy algorithm for linear programming, the perceptron algorithm, also has polynomial smoothed complexity, in a high probability sense; that is, the running time is polynomial with high probability over the random perturbation.
near-optimal online auctions. we consider the online auction problem proposed by bar-yossef, hildrum, and wu [4] in which an auctioneer is selling identical items to bidders arriving one at a time. we give an auction that achieves a constant factor of the optimal profit less an o(h) additive loss term, where h is the value of the highest bid. furthermore, this auction does not require foreknowledge of the range of bidders' valuations. on both counts, this answers open questions from [4, 5]. we further improve on the results from [5] for the online posted-price problem by reducing their additive loss term from o(h log h log log h) to o(h log log h). finally, we define the notion of an (offline) attribute auction for modeling the problem of auctioning items to consumers who are not a-priori indistinguishable. we apply our online auction solution to achieve good bounds for the attribute auction problem with 1-dimensional attributes.
online learning in online auctions. we consider the problem of revenue maximization in online auctions, that is, auctions in which bids are received and dealt with one-by-one. in this paper, we demonstrate that results from online learning can be usefully applied in this context, and we derive a new auction for digital goods that achieves a constant competitive ratio with respect to the optimal (offline) fixed price revenue. this substantially improves upon the best previously known competitive ratio for this problem of o(exp(√log log h)). we also apply our techniques to the related problem of designing online posted price mechanisms, in which the seller declares a price for each of a series of buyers, and each buyer either accepts or rejects the good at that price. despite the relative lack of information in this setting, we show that online learning techniques can be used to obtain results for online posted price mechanisms which are similar to those obtained for online auctions.
online algorithms for market clearing. in this article, we study the problem of online market clearing where there is one commodity in the market being bought and sold by multiple buyers and sellers whose bids arrive and expire at different times. the auctioneer is faced with an online clearing problem of deciding which buy and sell bids to match without knowing what bids will arrive in the future. for maximizing profit, we present a (randomized) online algorithm with a competitive ratio of ln(pmax &minus; pmin) &plus; 1, when bids are in a range [pmin, pmax], which we show is the best possible. a simpler algorithm has a ratio twice this, and can be used even if expiration times are not known. for maximizing the number of trades, we present a simple greedy algorithm that achieves a factor of 2 competitive ratio if no money-losing trades are allowed. we also show that if the online algorithm is allowed to subsidize matches---match money-losing pairs if it has already collected enough money from previous pairs to pay for them---then it can actually be 1-competitive with respect to the optimal offline algorithm that is not allowed subsidy. that is, for maximizing the number of trades, the ability to subsidize is at least as valuable as knowing the future. we also consider objectives of maximizing buy or sell volume and social welfare. we present all of these results as corollaries of theorems on online matching in an incomplete interval graph.we also consider the issue of incentive compatibility, and develop a nearly optimal incentive-compatible algorithm for maximizing social welfare. for maximizing profit, we show that no incentive-compatible algorithm can achieve a sublinear competitive ratio, even if only one buy bid and one sell bid are alive at a time. however, we provide an algorithm that, under certain mild assumptions on the bids, performs nearly as well as the best fixed pair of buy and sell prices, a weaker but still natural performance measure. this latter result uses online learning methods, and we also show how such methods can be used to improve our &ldquo;optimal&rdquo; algorithms to a broader notion of optimality. finally, we show how some of our results can be generalized to settings in which the buyers and sellers themselves have online bidding strategies, rather than just each having individual bids.
a new algorithm for normal dominance constraints. dominance constraints are logical descriptions of trees. efficient algorithms for the subclass of normal dominance constraints were recently proposed. we present a new and simpler graph algorithm solving these constraints more efficiently, in quadratic time per solved form. it also applies to weakly normal dominance constraints as needed for an application to computational linguistics. subquadratic running time can be achieved employing decremental graph biconnectivity algorithms.
on the combinatorial complexity of euclidean voronoi cells and convex hulls of d-dimensional spheres. in this paper we show an equivalence relationship between additively weighted voronoi cells in rd, power diagrams in rd and convex hulls of spheres in rd. an immediate consequence of this equivalence relationship is a tight bound on the complexity of: (1) a single additively weighted voronoi cell in dimension d; (2) the convex hull of a set of d-dimensional spheres. in particular, given a set of n spheres in dimension d, we show that the worst case complexity of both a single additively weighted voronoi cell and the convex hull of the set of spheres is &theta;(n[d/2]). the equivalence between additively weighted voronoi cells and convex hulls of spheres permits us to compute a single additively weighted voronoi cel1 in dimension d in worst case optimal time o(n log n+n[d/2]).
directed scale-free graphs. we introduce a model for directed scale-free graphs that grow with preferential attachment depending in a natural way on the in- and out-degrees. we show that the resulting in- and out-degree distributions are power laws with different exponents, reproducing observed properties of the worldwide web. we also derive exponents for the distribution of in- (out-) degrees among vertices with fixed out- (in-) degree. we conclude by suggesting a corresponding model with hidden variables.
sparse distance preservers and additive spanners. for an unweighted graph $g = (v,e)$, $g' = (v,e')$ is a subgraph if $e' \subseteq e$, and $g'' = (v'',e'',\omega)$ is a steiner graph if $v \subseteq v''$, and for any pair of vertices $u,w \in v$, the distance between them in $g''$ (denoted $d_{g''}(u,w)$) is at least the distance between them in $g$ (denoted $d_g(u,w)$).in this paper we introduce the notion of distance preserver. a subgraph (resp., steiner graph) $g'$ of a graph $g$ is a subgraph (resp., steiner) $d$-preserver of $g$ if for every pair of vertices $u,w \in v$ with $d_g(u,w) \ge d$, $d_{g'}(u,w) = d_g(u,w)$. we show that any graph (resp., digraph) has a subgraph $d$-preserver with at most $o(n^2/d)$ edges (resp., arcs), and there are graphs and digraphs for which any undirected steiner $d$-preserver contains $\omega(n^2/d)$ edges. however, we show that if one allows a directed steiner (disteiner) $d$-preserver, then these bounds can be improved. specifically, we show that for any graph or digraph there exists a disteiner $d$-preserver with $o({{n^2 \cdot \log d} \over {d \cdot \log n}})$ arcs, and that this result is tight up to a constant factor.we also study $d$-preserving distance labeling schemes, that are labeling schemes that guarantee precise calculation of distances between pairs of vertices that are at a distance of at least $d$ one from another. we show that there exists a $d$-preserving labeling scheme with labels of size $o({{n} \over {d}} \log^2 n)$, and that labels of size $\omega({{n} \over {d}} \log d)$ are required for any $d$-preserving labeling scheme.
(incremental) priority algorithms. we study the question of what optimization problems can be optimally or approximately solved by "greedy-like" algorithms. for definiteness, we will limit the present discussion to some well-studied scheduling problems although the underlying issues apply in a much more general setting. of course, the main benefit of greedy algorithms lies in both their conceptual simplicity and their computational efficiency. based on the experience from online competitive analysis, it seems plausible that we should be able to derive approximation bounds for "greedy-like" algorithms exploiting only the conceptual simplicity of these algorithms. to this end, we will provide a precise definition of what we mean by greedy and greedy-like. a full version of this paper is available at http://www.cs.toronto.edu/~ bor/priority.ps.
stability preserving transformations: packet routing networks with edge capacities and speeds. in the context of an adversarial input model, we consider the effect on stability results when edges in packet routing networks can have capacities and speeds/slowdowns. in traditional packet routing networks, every edge is considered to have the same unit capacity and unit speed. we consider both static modifications (i.e. where the capacity or speed of an edge is fixed) and dynamic modifications where either the capacity or the speed of an edge can be dynamically changing over time. amongst our results, we show that the universal stability of lis is not preserved when either the capacity or the speed is changing dynamically whereas many other common scheduling protocols do maintain their universal stability. in terms of universal stability of networks, stability is preserved for dynamically changing capacities and speeds. the situation for static modifications, is not as clear but we are able to show that (in contrast to the dynamic case) that any &ldquo;well defined&rdquo; universally stable scheduling rule maintains its universality under static capacities, and common scheduling rules also maintain their universal stability under static speeds.
an algorithm for maximum -flow in a directed planar graph. we give the first correct o(n log n) algorithm for finding a maximum st-flow in a directed planar graph. after a preprocessing step that consists in finding single-source shortest-path distances in the dual, the algorithm consists of repeatedly saturating the leftmost residual s-to-t path.