waashk/dblp huggingface dataset:
lower bounds for collusion-secure fingerprinting. collusion-secure fingerprinting codes are an important primitive used by many digital watermarking schemes [1, 10, 9]. boneh and shaw [3] define a model for these types of codes and present an explicit construction. their code has length o(c3 log(l/&epsilon;)) and attains security against coalitions of size c with &epsilon; error. boneh and shaw also present a lower bound of &omega; (c3log(1/c&epsilon;)) on the length of any collusion-secure code.we give new lower bounds on the length of collusion-secure codes by analyzing a weighted coinflipping strategy for the coalition. as an illustration of our methods, we give a simple proof that the boneh-shaw construction cannot be asymptotically improved. next, we prove a general lower bound: no secure code can have length o(c21og(1/c&epsilon;)), which improves the previous known bound by a factor of c. in particular, we show that any secure code will have length &omega;(c2 log(1/c&epsilon;)) as long as log(l/&epsilon;) &ge; k k log c, where k is a constant and k is the number of columns in the code (in some sense, a measure of the code's complexity). finally, we describe a general paradigm for constructing fingerprinting codes which encompasses the construction of [3], and show that no secure code that follows this paradigm can have length o((c3/log c) log(1/c&epsilon;)) follows this (again, by showing a lower bound for large values of ln(1/&epsilon;)). this suggests that any attempts at improvement should be directed toward techniques that lie outside our paradigm.
randomizing combinatorial algorithms for linear programming when the dimension is moderately high. in the last decade researchers in computational geometry have produced a series of algorithms for linear programming, based on a randomized combinatorial approach, which are tuned for linear programs where the number of variables d is small compared to the number n of constraints, although not so small to be considered a constant of the problem. one natural question is how practical are these algorithms for classes of lp instances not necessarily derived from problems in computational geometry. in this paper, building within the randomized combinatorial approach, we propose two algorithms for linear programming and we give evidence of their empirical running times on several classes of randomly generated instances. comparisons with state of the art free software (lp-solve) and state of the art commercial software (cplex) lead to the conclusion that the randomized combinatorial approach for systems with n &ap; d, at the present state of our research, can be competitive for dense systems and for sparse systems where a large fraction of the constraints are equalities. we also consider the case of dense systems where n > > d, which is typical in instances from computational geometry problems, for which we improve upon recent results of g&auml;tner and sch&ouml;nherr [13].
reconciling simplicity and realism in parallel disk models. for the design and analysis of algorithms that process huge data sets, a machine model is needed that handles parallel disks. there seems to be a dilemma between simple and flexible use of such a model and accurate modelling of details of the hardware. this paper explains how many aspects of this problem can be resolved. the programming model implements one large logical disk allowing concurrent access to arbitrary sets of variable size blocks. this model can be implemented efficienctly on multiple independent disks even if zones with different speed, communication bottlenecks and failed disks are allowed. these results not only provide useful algorithmic tools but also imply a theoretical justification for studying external memory algorithms using simple abstract models. the algorithmic approach is random redundant placement of data and optimal scheduling of accesses. the analysis generalizes a previous analysis for simple abstract external memory models in several ways (higher efficiency, variable block sizes, more detailed disk model). as a side effect, an apparently new chernoff bound for sums of weighted 0-1 random variables is derived.
an asymptotic approximation scheme for multigraph edge coloring. the edge coloring problem considers the assignment of colors from a minimum number of colors to edges of a graph such that no two edges with the same color are incident to the same node. we give polynomial time algorithms for approximate edge coloring of multigraphs, that is, parallel edges are allowed. the best previous algorithms achieve a fixed constant approximation factor plus a small additive offset. one of our algorithms achieves solution quality opt &plus; &sqrt;9opt/2 and has execution time polynomial in the number of nodes and the logarithm of the maximum edge multiplicity.
an experimental study of lp-based approximation algorithms for scheduling problems. recently there has been much progress on the design of approximation algorithms for a variety of scheduling problems in which the goal is to minimize the average weighted completion time of the jobs scheduled. many of these approximation algorithms have been inspired by polyhedral formulations of the scheduling problems and their use in computing optimal solutions to small instances. in this paper we demonstrate that the progress in the design and analysis of approximation algorithms for these problems also yields techniques with improved computational efficacy. specifically, we give a comprehensive experimental study of a number of these approximation algorithms for 1|rj|âwjcj, the problem of scheduling jobs with release dates on one machine so as to minimize the average weighted completion time of the jobs scheduled. we study both the quality of lower bounds given for this problem by different linear-programming relaxations and combinatorial relaxations, and the quality of upper bounds delivered by a number of approximation algorithms based on them. the best algorithms, on almost all instances, come within a few percent of the optimal average weighted completion time. furthermore, we show that this can usually be achieved with o(n log n) computation. in addition we observe that on most kinds of synthetic data used in experimental studies a simple greedy heuristic, used in successful combinatorial branch-and-bound algorithms for the problem, outperforms (on average) all of the lp-based heuristics. we identify, however, other classes of problems on which the lp-based heuristics are superior and report on experiments that give a qualitative sense of the range of dominance of each. we consider the impact of local improvement on the solutions as well. we also consider the performance of the algorithms for the average weighted flow-time criterion, which, although equivalent to average weighted completion time at optimality, is provably much harder to approximate. nonetheless, we demonstrate that for most instances we consider that the algorithms give very good results for this criterion as well. finally, we extend the techniques to a rather different and more complex problem that arises from an actual manufacturing application: resource-constrained project scheduling. in this setting as well, the techniques yield algorithms with improved performance; we give the best-known solutions for a set of instances provided by basf ag, germany.
buffer minimization using max-coloring. given a graph g = (v,e) and positive integral vertex weights w : v &rarr; n, the max-coloring problem seeks to find a proper vertex coloring of g whose color classes c1, c2,...,ck, minimize &sigma;ki = 1 max&nu;&isin;ciw(&nu;). this problem, restricted to interval graphs, arises whenever there is a need to design dedicated memory managers that provide better performance than the general purpose memory management of the operating system. specifically, companies have tried to solve this problem in the design of memory managers for wireless protocol stacks such as gprs or 3g.though this problem seems similar to the wellknown dynamic storage allocation problem, we point out fundamental differences. we make a connection between max-coloring and on-line graph coloring and use this to devise a simple 2-approximation algorithm for max-coloring on interval graphs. we also show that a simple first-fit strategy, that is a natural choice for this problem, yields a 10-approximation algorithm. we show this result by proving that the first-fit algorithm for on-line coloring an interval graph g uses no more than 10.x(g) colors, significantly improving the bound of 26.x(g) by kierstead and qin (discrete math., 144, 1995). we also show that the max-coloring problem is np-hard.
online paging with arbitrary associativity. we tackle the problem of online paging on two level memories with arbitrary associativity (including victim caches, skewed caches etc.). we show that some important classes of paging algorithms are not competitive on a wide class of associativities (even with arbitrary resource augmentation) and that although some algorithms designed for full associativity are actually competitive on any two level memory, the myopic behavior of paging algorithms designed for full associativity will generally result in very poor performance at least for some "associativity topologies". at the same time we present a simple and yet powerful technique that allows us to overcome this shortcoming, generalizing algorithms designed for full associativity into practical algorithms which are efficient on two level memories with arbitrary associativity. we identify a simple topological parameter, pseudo associativity, which characterizes the competitive ratio achievble on any two level memory, giving a lower bound on the competitiveness achievable by any paging algorithm and matching it within a factor 4 with a novel algorithm.
chernoff-hoeffding bounds for applications with limited independence. chernoff-hoeffding (ch) bounds are fundamental tools used in bounding the tail probabilities of the sums of bounded and independent random variables (r.v.'s). we present a simple technique that gives slightly better bounds than these and that more importantly requires only limited independence among the random variables, thereby importing a variety of standard results to the case of limited independence for free. additional methods are also presented, and the aggregate results are sharp and provide a better understanding of the proof techniques behind these bounds. these results also yield improved bounds for various tail probability distributions and enable improved approximation algorithms for jobshop scheduling. the limited independence result implies that a reduced amount and weaker sources of randomness are sufficient for randomized algorithms whose analyses use the ch bounds, e.g., the analysis of randomized algorithms for random sampling and oblivious packet routing.
computing shortest paths with comparisons and additions. we present an undirected all-pairs shortest paths (apsp) algorithm which runs on a pointer machine in time o(mn&alpha;(m,n)) while making o(mnlog &alpha;(m, n)) comparisons and additions, where m and n are the number of edges and vertices, respectively, and &alpha;(m, n) is tarjan's inverse-ackermann function. this improves upon all previous comparison & addition-based apsp algorithms when the graph is sparse, i.e., when m = o(n log n).at the heart of our apsp algorithm is a new single-source shortest paths algorithm which runs in time o(m&alpha;(m, n) + n log log r) on a pointer machine, where r is the ratio of the maximum-to-minimum edge length. so long as r < 2no(1) this algorithm is faster than any implementation of dijkstra's classical algorithm in the comparison-addition model.for directed graphs we give an o(m + n log r)-time comparison & addition-based sssp algorithm on a pointer machine. similar algorithms assuming integer weights or the ram model were given earlier.
minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms. there are several fundamental problems for which there are optimal randomized algorithms, but whose deterministic complexity remains unresolved. among such problems are the minimum spanning tree problem, the set maxima problem, the problem of computing connected components and (minimum) spanning trees in parallel and the problem of performing sensitivity analysis on shortest path trees and minimum spanning trees. for each of these problems there is an optimal randomized algorithm which uses a linear number of random bits. we propose new algorithms (or adapt old ones) for these problems which preserve optimality while saving an exponential number of random bits. in the case of computing minimum spanning trees and mst/sssp sensitivity analysis, we reduce the dependence on randomness to log* n random bits.we also consider the problem of selection, for which we give two algorithms which make an expected 1.5n + o(n) comparisons; one uses o(log n) random bits and is uniform, the other uses o(log log n) random bits and is non-uniform.
depth optimal sorting networks resistant to k passive faults. we study the problem of constructing a sorting network that is tolerant to faults and whose running time (i.e., depth) is as small as possible. we consider the scenario of worst-case comparator faults and follow the model of passive comparator failure proposed by yao and yao siam j. comput., 14 (1985), pp. 120--128], in which a faulty comparator outputs its inputs directly without comparison. our main result is the first construction of an n-input k-fault-tolerant sorting network with an asymptotically optimal depth $\theta$(log n + k). that improves over the result of leighton and ma [proceedings of the 5th annual acm symposium on parallel algorithms and architectures, velen, germany, 1993, acm, new york, pp. 30--41], whose network is of depth o(log n + klog\frac{log n}{log k})$.actually, we present a fault-tolerant correction network that can be added after any n-input sorting network to correct its output in the presence of at most k faulty comparators. since the depth of the network is o(log n + k) and the constants hidden behind the "o" notation are small, the construction can be of practical use.developing the techniques necessary to show the main result, we construct a fault-tolerant network for the insertion problem. as a by-product, we get an n-input o(log n)-depth insert-network that is tolerant to random faults, thereby answering a question posed by ma in his ph. d. thesis [fault-tolerant sorting network, department of mathematics, massachusetts institute of technology, cambridge, ma, 1994].the results are based on a new notion of constant delay comparator networks, that is, networks in which each register is used (compared) only in a period of time of a constant length. copies of such networks can be pipelined with only a constant increase in the total depth per copy.
new bounds for multi-dimensional packing. new upper and lower bounds are presented for a multi-dimensional generalization of bin packing called box packing.several variants of this problem, including bounded space box packing, square packing, variable sized box packing and resource augmented box packing are also studied. the main results, stated for d = 2, are as follows: a new upper bound of 2.66013 for online box packing, a new 14/9 + &epsilon; polynomial time offline approximation algorithm for square packing, a new upper bound of 2.43828 for online square packing, a new lower bound of 1.62176 for online square packing, a new lower bound of 2.28229 for bounded space online square packing and a new upper bound of 2.32571 for online two-sized box packing.
minimum moment steiner trees. for a rectilinear steiner tree t with a root, define its k-th momentmk(t)= &int;t(dt(u))kduwhere the integration is over all edges of t, dt (u) is the length of the unique path in t from the root to u, and du is the incremental edge length. given a set of points p in the plane, a k-th moment steiner minimum tree (k-smt) is a rectilinear steiner tree that has the minimum k-th moment among all rectilinear steiner trees for p, with the origin as the root. the definition is a natural extension of the traditional steiner minimum tree, and motivated by application in vlsi routing. in this paper properties of the k-smt are studied and approximation algorithms are presented.
undiscretized dynamic programming: faster algorithms for facility location and related problems on trees. in the uncapacitated facility location (ufl) problem, there is a fixed cost for opening a facility, and some distance matrix d that determines the cost of distributing commodities from any facility i to any consumer j. the problem is np-hard in general and when d consists of a distance metric in a graph [7, 12]. however, for the case where the commodity transportation costs are given by path lengths in a tree, an o(n2) dynamic programming algorithm was given by [4, 7]. we improve this dynamic programming algorithm by using the geometry of piecewise linear functions and fast merging of the binary search trees used to store these functions. we achieve the complexity bound of o(n log n) for the tree location problem and some related problems. our approach gives a general method for solving tree dynamic programming problems.
distributed online call control on general networks. we study the problem of online call admission and routing ("call control") on general networks. we give new algorithms that with high probability achieve a poly-logarithmic fraction (in the size of the network) of the optimal solution. the decisions of our algorithms do not depend on the current load of all network links, as in previous algorithms for general network topologies [aap93]. instead, their admission decisions depend only on link loads along a single path between the communicating parties, and they can thus be performed in a distributed hop-by-hop manner through the network. furthemore, our algorithms can handle concurrent requests in the network.
minimizing capacity violations in a transshipment network. the problem of minimizing capacity violation is a variation of the transshipment problem. it is equivalent to the problem of computing maximum mean surplus cuts which arises in the dual approach to the minimum cost network circulation problem. mccormick and ervolina [15] proposed an algorithm which computes a sequence of cuts with increasing mean surpluses, and stops when an optimal one is found. the mean surplus of this cut is equal to the minimum possible maximum capacity violation. mccormick and ervolina proved that the number of iterations in this algorithm is o(m). one iteration, i.e., finding the subsequent cut, amounts to computing maximum flow in an appropriate network. we prove that the number of iterations in this algorithm is &thgr;(n). this gives the best known upper bound o(n2m) for the problem. we also show a tight analysis of this algorithm for the case with integral capacities and demands, and present some improvements.
the interface between computational and combinatorial geometry. we illustrate the rich interface between computational and combinatorial geometry by a series of examples, including k-sets, randomized incremental algorithms, random sampling and partitioning, and analysis of geometric arrangements.
roundtrip spanners and roundtrip routing in directed graphs. we introduce the notion of roundtrip-spanners of weighted directed graphs and describe efficient algorithms for their construction. we show that for every integer k &ge; 1 and any &epsi; > 0, any directed graph on n vertices with edge weights in the range [1, w] has a (2k + &epsi;)-roundtrip-spanner with o(min{(k2/&epsi;) n1 + 1/k (log(nw), (k/&epsi;)2 n1 + 1/k,(log n)2&minus;1/k}) edges. we then extend these constructions and obtain compact roundtrip routing schemes. for every integer k &ge; 1 and every &epsi; > 0, we describe a roundtrip routing scheme that has stretch 4k + &epsi;, and uses at each vertex a routing table of size &otilde;((k2/&epsi;)n1/k log(nw)). we also show that any weighted directed graph with arbitrary/ positive edge weights has a 3-roundtrip-spanner with o(n3/2) edges. this result is optimal. finally, we present a stretch 3 roundtrip routing scheme that uses local routing tables of size &otilde;(n1/2). this routing scheme is essentially optimal. the roundtrip-spanner constructions and the roundtrip routing schemes for directed graphs that we describe are only slightly worse than the best available spanners and routing schemes for undirected graphs. our roundtrip routing schemes substantially improve previous results of cowen and wagner. our results are obtained by combining ideas of cohen, cowen and wagner, thorup and zwick, with some new ideas.
ray shooting amid balls, farthest point from a line, and range emptiness searching. in the range emptiness searching problem, we are given a set p of n points in rd, and wish to preprocess them into a data structure that supports efficient range emptiness queries, in which we specify a range &sigma;, which is a semi-algebraic set in rd of some fixed kind, and wish to determine whether p &cap; &sigma; = &theta;. range emptiness searching arises in many applications, and has been treated by matou&scaron;ek [15] in the special case where the ranges are halfspaces bounded by hyperplanes. in this paper we extend the analysis to the general semi-algebraic case, and show how to adapt matou&scaron;ek's technique to this case, without the need to linearize the ranges into a higher-dimensional space. this yields more efficient solutions to several interesting problems, and we demonstrate the new technique in two applications:(i) an algorithm for ray shooting amid balls in r3, which uses o* (n) storage and preprocessing, and answers a query in o* (n2/3) time, improving the previous bound of o* (n3/47).(ii) an algorithm that preprocesses, in o*(n) time, a set p of n points in r3 into a data structure with o*(n) storage, so that, for any query line l or segment e, the point of p farthest from l or from e can be computed in o* (n1/2) time.our technique is closely related to the notions of nearest- or farthest-neighbor generalized voronoi diagrams, and of the union or intersection of geometric objects, where sharper bounds on the combinatorial complexity of these structures yield faster range emptiness searching algorithms. for example, in the case of ray shooting amid balls, the structure that arises in our algorithm is the euclidean voronoi diagram of lines in 3-space, and the performance of the algorithm depends on the complexity of such diagrams (for which tight bounds are still unknown).
on the number of crossing-free matchings, (cycles, and partitions). we show that a set of $n$ points in the plane has at most $o(10.05^n)$ perfect matchings with crossing-free straight-line embedding. the expected number of perfect crossing-free matchings of a set of $n$ points drawn independently and identically distributed from an arbitrary distribution in the plane is at most $o(9.24^n)$. several related bounds are derived: (a) the number of all (not necessarily perfect) crossing-free matchings is at most $o(10.43^n)$. (b) the number of red-blue perfect crossing-free matchings (where the points are colored red or blue and each edge of the matching must connect a red point with a blue point) is at most $o(7.61^n)$. (c) the number of left-right perfect crossing-free matchings (where the points are designated as left or right endpoints of the matching edges) is at most $o(5.38^n)$. (d) the number of perfect crossing-free matchings across a line (where all the matching edges must cross a fixed halving line of the set) is at most $4^n$. these bounds are employed to infer that a set of $n$ points in the plane has at most $o(86.81^n)$ crossing-free spanning cycles (simple polygonizations) and at most $o(12.24^n)$ crossing-free partitions (these are partitions of the point set so that the convex hulls of the individual parts are pairwise disjoint). we also derive lower bounds for some of these quantities.