waashk/dblp huggingface dataset:
exact and efficient 2d-arrangements of arbitrary algebraic curves. we show how to compute the planar arrangement induced by segments of arbitrary algebraic curves with the bentley-ottmann sweep-line algorithm. the necessary geometric primitives reduce to cylindrical algebraic decompositions of the plane for one or two curves. we compute them by a new and efficient method that combines adaptive-precision root finding (the bitstream descartes method of eigenwillig et al., 2005) with a small number of symbolic computations, and that delivers the exact result in all cases. thus we obtain an algorithm which produces the mathematically true arrangement, undistorted by rounding error, for any set of input segments. our algorithm is implemented in the exacus library alcix. we report on experiments; they indicate the efficiency of our approach.
arc-disjoint in-trees in directed graphs. given a directed graph d = (v, a) and a set of specified vertices s = {s1,&hellip;,sd} &sube; v with |s| = d and a function f: s &rarr; n where n denotes the set of natural numbers, we present a necessary and sufficient condition that there exist &sigma;si &epsilon; arc-disjoint in-trees denoted by ti,1,ti,2,&hellip;,tif (si) for every i = 1,&hellip;,d such that ti,1,&hellip;, ti,f(si) are rooted at si and each ti,j spans vertices from which si is reachable. this generalizes the result of edmonds [2], i.e., the necessary and sufficient condition that for a directed graph d = (v,a) with a specified vertex s &epsilon; v, there are k arc-disjoint in-trees rooted at s each of which spans v. furthermore, we extend another characterization of packing in-trees of edmonds [1] to the one in our case.
on the approximability of influence in social networks. in this paper, we study the spread of influence through a social network, in a model initially studied by kempe, kleinberg and tardos [14, 15]: we are given a graph modeling a social network, where each node v has a (fixed) threshold tv, such that the node will adopt a new product if tv of its neighbors adopt it. our goal is to find a small set s of nodes such that targeting the product to s would lead to adoption of the product by a large number of nodes in the graph. we show strong inapproximability results for several variants of this problem. our main result says that the problem of minimizing the size of s, while ensuring that targeting s would influence the whole network into adopting the product, is hard to approximate within a polylogarithmic factor. this implies similar results if only a fixed fraction of the network is ensured to adopt the product. further, the hardness of approximation result continues to hold when all nodes have majority thresholds, or have constant degree and threshold two. the latter answers a complexity question proposed in [10, 29]. we also give some positive results for more restricted cases, such as when the underlying graph is a tree.
designing networks with good equilibria. in a network with selfish users, designing and deploying a protocol determines the rules of the game by which end users interact with each other and with the network. we study the problem of designing a protocol to optimize the equilibrium behavior of the induced network game. we consider network cost-sharing games, where the set of nash equilibria depends fundamentally on the choice of an edge cost-sharing protocol. previous research focused on the shapley protocol, in which the cost of each edge is shared equally among its users. we systematically study the design of optimal cost-sharing protocols for undirected and directed graphs, single-sink and multicommodity networks, different classes of cost-sharing methods, and different measures of the inefficiency of equilibria. one of our main technical tools is a complete characterization of the uniform cost-sharing protocols---protocols that are designed without foreknowledge of or assumptions on the network in which they will be deployed. we use this characterization result to identify the optimal uniform protocol in several scenarios: for example, the shapley protocol is optimal in directed graphs, while the optimal protocol in undirected graphs, a simple priority scheme, has exponentially smaller worst-case price of anarchy than the shapley protocol. we also provide several matching upper and lower bounds on the best-possible performance of non-uniform cost-sharing protocols.
holographic algorithms with unsymmetric signatures. holographic algorithms were introduced by valiant as a new methodology to derive polynomial time algorithms. here information and computation are represented by exponential sums using the so-called signatures. these signatures express superpositions of perfect matchings, and are used to achieve exponential sized cancellations, and thereby exponential speedups. most holographic algorithms so far used symmetric signatures. in this paper we use unsymmetric signatures to give some new holographic algorithms. we also prove a characterization theorem for a class of realizable un-symmetric signatures, each of which may be used to design new holographic algorithms.
improved distance sensitivity oracles via random sampling. we present improved oracles for the distance sensitivity problem. the goal is to preprocess a graph g = (v,e) with non-negative edge weights to answer queries of the form: what is the length of the shortest path from x to y that does not go through some failed vertex or edge f. there are two state of the art algorithms for this problem. the first produces an oracle of size &otilde;(n2) that has an o(1) query time, and an &otilde;(mn2) construction time. the second oracle has size o(n2.5), but the construction time is only &otilde;(mn1.5). we present two new oracles that substantially improve upon both of these results. both oracles are constructed with randomized, monte carlo algorithms. for directed graphs with non-negative edge weights, we present an oracle of size &otilde;(n2), which has an o(1) query time, and an &otilde;(n2&radic;m) construction time. for unweighted graphs, we achieve a more general construction time of &otilde;(&radic;n3 &middot; apsp + mn), where apsp is the time it takes to compute all pairs shortest paths in an aribtrary subgraph of g.
algorithms for distributed functional monitoring. we study what we call functional monitoring problems. we have k players each tracking their inputs, say player i tracking a multiset ai(t) up until time t, and communicating with a central coordinator. the coordinator's task is to monitor a given function f computed over the union of the inputs &cup;iai(t), continuously at all times t. the goal is to minimize the number of bits communicated between the players and the coordinator. a simple example is when f is the sum, and the coordinator is required to alert when the sum of a distributed set of values exceeds a given threshold &tau;. of interest is the approximate version where the coordinator outputs 1 if f &ge; &tau; and 0 if f &le; (1 - &epsilon;)&tau;. this defines the (k, f, &tau;, &epsilon;) distributed, functional monitoring problem. functional monitoring problems are fundamental in distributed systems, in particular sensor networks, where we must minimize communication; they also connect to problems in communication complexity, communication theory, and signal processing. yet few formal bounds are known for functional monitoring. we give upper and lower bounds for the (k, f, &tau;, &epsilon;) problem for some of the basic f's. in particular, we study frequency moments (f0, f1, f2). for f0 and f1, we obtain continuously monitoring algorithms with costs almost the same as their one-shot computation algorithms. however, for f2 the monitoring problem seems much harder. we give a carefully constructed multi-round algorithm that uses "sketch summaries" at multiple levels of detail and solves the (k, f2, &tau;, &epsilon;) problem with communication &otilde;(k2/&epsilon;+ (&radic;k/&epsilon;)3). since frequency moment estimation is central to other problems, our results have immediate applications to histograms, wavelet computations, and others. our algorithmic techniques are likely to be useful for other functional monitoring problems as well.
distributed broadcast in unknown radio networks. we consider the problem of broadcasting in an unknown radio network modeled as a directed graph g = (v, e), where |v| = n. in unknown networks, every node knows only its own label, while it is unaware of any other parameter of the network, included its neighborhood and even any upper bound on the number of nodes. we show an o(n log n log log n) upper bound on the time complexity of deterministic broadcasting improving upon the time complexity of the currently best known algorithms [6, 12].
concatenated codes can achieve list-decoding capacity. we prove that binary linear concatenated codes with an outer algebraic code (specifically, a folded reed-solomon code) and independently and randomly chosen linear inner codes achieve the list-decoding capacity with high probability. in particular, for any 0 < &rho; < 1/2 and &epsilon; > 0, there exist concatenated codes of rate at least 1 -- h(&rho;) -- &epsilon; that are (combinatorially) list-decodable up to a fraction &rho; of errors. (the best possible rate, aka list-decoding capacity, for such codes is 1 -- h(&rho;), and is achieved by random codes.) a similar result, with better list size guarantees, holds when the outer code is also randomly chosen. our methods and results extend to the case when the alphabet size is any fixed prime power q &ge; 2. our result shows that despite the structural restriction imposed by code concatenation, the family of concatenated codes is rich enough to include capacity achieving list-decodable codes. this provides some encouraging news for tackling the problem of constructing explicit binary list-decodable codes with optimal rate, since code concatenation has been the preeminent method for constructing good codes over small alphabets.
sampling stable marriages: why spouse-swapping won't work. we study the behavior of random walks along the edges of the stable marriage lattice for various restricted families of allowable preference sets. in the "k-attribute model," each man is valued in each of k attributes, and each woman's ranking of the men is determined by a linear function, representing her relative ranking of those attributes; men's rankings of the women are determined similarly. we show that sampling with a random walk on the marriage lattice can take exponential time, even when k = 2. moreover, we show that the marriage lattices arising in the k-attribute model are more restrictive than in the general setting; previously such a restriction had only been shown for the sets of preference lists. the second model we consider is the "k-range model," where each person lies in a position in [i, i + k - 1], for some i, on every preference list of the opposite sex. when k = 1 there is a unique stable marriage. when k = 2 there already can be an exponential number of stable marriages, but we show that a random walk on the stable marriage lattice always converges quickly to equilibrium. however, when k &ge; 5, there are preference sets such that the random walk on the lattice will require exponential time to converge. lastly, we show that in the extreme case where each gender's rankings of the other are restricted to one of just a constant k possible preference lists, there are still instances for which the markov chain mixes exponentially slowly, even when k = 4. this oversimplification of the general model helps elucidate why markov chains based on spouse-swapping are not good approaches to sampling, even in specialized scenarios.
trace reconstruction with constant deletion probability and related results. we provide several new results for the trace reconstruction problem. in this setting, a binary string yields a collection of traces, where each trace is independently obtained by independently deleting each bit with a fixed probability &delta;. each trace therefore consists of a random subsequence of the original sequence. given the traces, we wish to reconstruct the original string with high probability. the questions are how many traces are necessary for reconstruction, and how efficiently can the reconstruction be performed. our primary result is that for some universal constant &gamma; and uniformly chosen strings of length n, for any &delta; < &gamma; reconstruction is possible with poly(n) traces in poly(n) time with high probability. we also obtain algorithms that require a number of traces exponential in &otilde; (&radic;n) for any &delta; < 1 even for worst case strings, and we derive lower bound results for simpler classes of algorithms based on summary statistics from the traces.
geodesic delaunay triangulation and witness complex in the plane. we introduce a novel feature size for bounded planar domains endowed with an intrinsic metric. given a point x in such a domain x, the homotopy feature size of x at x, or hfs(x) for short, measures half the length of the shortest loop through x that is not null-homotopic in x. the resort to an intrinsic metric makes hfs(x) rather insensitive to the local geometry of x, in contrast with its predecessors (local feature size, weak feature size, homology feature size). this leads to a reduced number of samples that still capture the topology of x. under reasonable sampling conditions involving hfs, we show that the geodesic delaunay traingulation dx (l) of a finite sampling l of x is homotopy equivalent to x. moreover, dx (l) is sandwiched between the geodesic witness complex cwx (l) and a relaxed version cwx, v (l), defined by a parameter v. taking advantage of this fact, we prove that the homology of dx (l) (and hence of x) can be retrieved by computing the persistent homology between cwx (l) and cwx, v (l). we propose algorithms for estimating hfs, selecting a landmark set of sufficient density, building its geodesic delaunay triangulation, and computing the homology of x using cwx (l). we also present some simulation results in the context of sensor networks that corroborate our theoretical statements.
dimension augmentation and combinatorial criteria for efficient error-resistant dna self-assembly. dna self-assembly has emerged as a rich and promising primitive for nano-technology. experimental and analytical evidence indicates that such systems are prone to errors, and accordingly, several error-correction mechanisms have been proposed for the tile model of self-assembly. these error-correction mechanisms suffer either from high resolution loss or a large increase in the number of tile-types. in this paper, we propose dimension augmented proof-reading, a technique that uses the third dimension to do error-correction in two dimensional self-assembling systems. this involves no resolution loss in the two dimensions of interest, results in a smaller increase in the number of tile-types than previous techniques, and appears to have the same error-correction properties. error-correcting systems need to be analyzed in the kinetic tile assembly model; such analysis involves complicated markov chains and is cumbersome. in this paper, we also present a set of completely combinatorial criteria that can be used to prove properties of error-correcting self-assembling systems. we illustrate these criteria by applying them to two known proof-reading systems, one of which was not previously known to work. we then use these criteria to prove the correctness of dimension augmented proof-reading applied to a self-assembling system that computes the parity of a string.
robust cost colorings. we consider graph coloring problems where the cost of a coloring is the sum of the costs of the colors, and the cost of a color is a monotone concave function of the total weight of the class. this models resource allocation problems where the cost of a resource depends on the use of the resource. the specific case of interval graphs is of special interest as multi-criteria interval scheduling. we give an algorithm for all perfect graphs that yields a robust coloring: a particular solution that simultaneously approximates all concave functions. for graphs with uniform weights, we show how to modify the solution to approximate any monotone cost function. we complement these results with a number of hardness results and some exact algorithms on restricted classes of graphs.
the hiring problem and lake wobegon strategies. we introduce the hiring problem, in which a growing company continuously interviews and decides whether to hire applicants. this problem is similar in spirit but quite different from the well-studied secretary problem. like the secretary problem, it captures fundamental aspects of decision making under uncertainty and has many possible applications. we analyze natural strategies of hiring above the current average, considering both the mean and the median averages; we call these lake wobegon strategies. like the hiring problem itself, our strategies are intuitive, simple to describe, and amenable to mathematically and economically significant modifications. we demonstrate several intriguing behaviors of the two strategies. specifically, we show dramatic differences between hiring above the mean and above the median. we also show that both strategies are intrinsically connected to the lognormal distribution, leading to only very weak concentration results, and the marked importance of the first few hires on the overall outcome.
online budgeted matching in random input models with applications to adwords. we study an online assignment problem, motivated by adwords allocation, in which queries are to be assigned to bidders with budget constraints. we analyze the performance of the greedy algorithm (which assigns each query to the highest bidder) in a randomized input model with queries arriving in a random permutation. our main result is a tight analysis of greedy in this model showing that it has a competitive ratio of 1 - 1/e for maximizing the value of the assignment. we also consider the more standard i.i.d. model of input, and show that our analysis holds there as well. this is to be contrasted with the worst case analysis of [msvv05] which shows that greedy has a ratio of 1/2, and that the optimal algorithm presented there has a ratio of 1 - 1/e. the analysis of greedy is important in the adwords setting because it is the natural allocation algorithm for an auction-style process. from a theoretical perspective, our result simplifies and generalizes the classic algorithm of karp, vazirani and vazirani for online bipartite matching. our results include a new proof to show that the ranking alforithm of [kvv90] has a ratio of 1 - 1/e in the worst case. it has been recently discovered [kv07] (independent of our results) that one of the crucial lemmas in [kvv90], related to a certain reduction, is incorrect. our proof is direct, in that it does not go via such a reduction, which also enables us to generalize the analysis to our online assignment problem.
spread: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems. in this paper we study the problem of designing an adaptive hash table for redundant data storage in a system of storage devices with arbitrary capacities. ideally, such a hash table should make sure that (a) a storage device with x% of the available capacity should get x% of the data, (b) the copies of each data item are distributed among the storage devices so that no two copies are stored at the same device, and (c) only a near-minimum amount of data replacements is necessary to preserve (a) and (b) under any change in the system. hash tables satisfying (a) and (c) are already known, and it is not difficult to construct hash tables satisfying (a) and (b). however, no hash table is known so far that can satisfy all three properties as long as this is in principle possible. we present a strategy called spread that solves this problem for the first time. as long as (a) and (b) can in principle be satisfied, spread preserves (a) for every storage device within a (1 &plusmn; &epsilon;) factor, with high probability, where &epsilon; > 0 can be made arbitrarily small, guarantees (b) for every data item, and only needs a constant factor more data replacements than minimum possible in order to preserve (a) and (b).
approximating geometric coverage problems. we present the first study on the approximability of geometric versions of the unique coverage problem and the minimum membership set cover problem. in the former problem, one is given a family of sets of elements from some universe and aims to select sets that maximize the number of elements contained in precisely one selected set. unique coverage has important applications in wireless networks and it is thus natural to consider it in a geometric setting. we use the well-known (unit) disk model for wireless networks and show that unique coverage remains np-hard in this case and present a polynomial-time 1/18-approximation algorithm. this algorithm is extended to the budgeted low-coverage problem, where covering can element multiple times yields less profit and we have a fixed budget to 'buy' sets. we give an asymptotic fptas in case the disks have arbitrary size, but bounded ply. for the case that the geometric objects are arbitrary fat objects, we show that these problems are as hard to approximate as in the general case. in the minimum membership set cover problem, the goal is to cover all elements while minimizing the maximum number of sets in which any element is contained. for unit squares and unit disks, we show that the problem remains np-hard and does not admit a polynomial-time approximation algorithm with ratio smaller than 2 unless p=np. for unit squares, we give a 5-approximation algorithm for instances where the optimum objective value is bounded by a constant.
real-time indexing over fixed finite alphabets. the quest for a real-time indexing algorithm is ove three decades old. to date there is no convincing understandable solution to this problem. this paper provides a real-time indexing algorithm over a constant sized alphabet. assuming the text is arriving at a constant rate, the algorithm spends o(1) time on every text symbol. whenever a length m pattern is given, the algorithm decides in time o(m) whether there is an occurrence of the pattern in the text thus far.
on the value of coordination in network design. we study network design games where n self-interested agents have to form a network by purchasing links from a given set of edges. we consider shapley cost sharing mechanisms that split the cost of an edge in a fair manner among the agents using the edge. it is well known that the price of anarchy of these games is as high as n. therefore, recent research has focused on evaluating the price of stability, i.e. the cost of the best nash equilibrium relative to the social optimum. in this paper we investigate to which extent coordination among agents can improve the quality of solutions. we resort to the concept of strong nash equilibria, which were introduced by aumann and are resilient to deviations by coalitions of agents. we analyze the price of anarchy of strong nash equilibria and develop lower and upper bounds for unweighted and weighted games in both directed and undirected graphs. these bounds are tight or nearly tight for many scenarios. it shows that using coordination, the price of anarchy drops from linear to logarithmic bounds. we complement these results by also proving the first super-constant lower bound on the price of stability of standard equilibria (without coordination) in undirected graphs. more specifically, we show a lower bound of &omega;(log w/ log log w) for weighted games, where w is the total weight of all the agents. this almost matches the known upper bound of o(log w). our results imply that, for most settings, the worst-case performance ratios of strong coordinated equilibria are essentially always as good as the performance ratios of the best equilibria achievable without coordination. these settings include unweighted games in directed graphs as well as weighted games in both directed and undirected graphs.