waashk/dblp huggingface dataset:
inverse auctions: injecting unique minima into random sets. we consider auctions in which the winning bid is the smallest bid that is unique. only the upper-price limit is given. neither the number of participants nor the distribution of the offers are known, so that the problem of placing a bid to win with maximum probability looks, a priori, ill-posed. indeed, the essence of the problem is to inject a (final) minimum into a random subset (of unique offers) of a larger random set. we will see, however, that here no more than two external (and almost compelling) arguments make the problem meaningful. by appropriately modeling the relationship between the number of participants and the distribution of the bids, we can then maximize our chances of winning the auction and propose a computable algorithm for placing our bid.
resilient dictionaries. we address the problem of designing data structures in the presence of faults that may arbitrarily corrupt memory locations. more precisely, we assume that an adaptive adversary can arbitrarily overwrite the content of up to &delta; memory locations, that corrupted locations cannot be detected, and that only o(1) memory locations are safe. in this framework, we call a data structure resilient if it is able to operate correctly (at least) on the set of uncorrupted values. we present a resilient dictionary, implementing search, insert, and delete operations. our dictionary has o(log n + &delta;) expected amortized time per operation, and o(n) space complexity, where n denotes the current number of keys in the dictionary. we also describe a deterministic resilient dictionary, with the same amortized cost per operation over a sequence of at least &delta;&epsis; operations, where &epsis; > 0 is an arbitrary constant. finally, we show that any resilient comparison-based dictionary must take &omega;(log n + &delta;) expected time per search. our results are achieved by means of simple, new techniques which might be of independent interest for the design of other resilient algorithms.
optimizing throughput and energy in online deadline scheduling. this article extends the study of online algorithms for energy-efficient deadline scheduling to the overloaded setting. specifically, we consider a processor that can vary its speed between 0 and a maximum speed t to minimize its energy usage (the rate is believed to be a cubic function of the speed). as the speed is upper bounded, the processor may be overloaded with jobs and no scheduling algorithms can guarantee to meet the deadlines of all jobs. an optimal schedule is expected to maximize the throughput, and furthermore, its energy usage should be the smallest among all schedules that achieve the maximum throughput. in designing a scheduling algorithm, one has to face the dilemma of selecting more jobs and being conservative in energy usage. if we ignore energy usage, the best possible online algorithm is 4-competitive on throughput [koren and shasha 1995]. on the other hand, existing work on energy-efficient scheduling focuses on a setting where the processor speed is unbounded and the concern is on minimizing the energy to complete all jobs; o(1)-competitive online algorithms with respect to energy usage have been known [yao et al. 1995; bansal et al. 2007a; li et al. 2006]. this article presents the first online algorithm for the more realistic setting where processor speed is bounded and the system may be overloaded; the algorithm is o(1)-competitive on both throughput and energy usage. if the maximum speed of the online scheduler is relaxed slightly to (1+&epsis;)t for some &epsis; > 0, we can improve the competitive ratio on throughput to arbitrarily close to one, while maintaining o(1)-competitiveness on energy usage.
periodicity testing with sublinear samples and space. in this work, we are interested in periodic trends in long data streams in the presence of computational constraints. to this end; we present algorithms for discovering periodic trends in the combinatorial property testing model in a data stream s of length n using o(n) samples and space. in accordance with the property testing model, we first explore the notion of being &ldquo;close&rdquo; to periodic by defining three different notions of self-distance through relaxing different notions of exact periodicity. an input s is then called approximately periodic if it exhibits a small self-distance (with respect to any one self-distance defined). we show that even though the different definitions of exact periodicity are equivalent, the resulting definitions of self-distance and approximate periodicity are not; we also show that these self-distances are constant approximations of each other. afterwards, we present algorithms which distinguish between the two cases where s is exactly periodic and s is far from periodic with only a constant probability of error. our algorithms sample only o(&sqrt;nlog2 n) (or o(&sqrt;nlog4 n), depending on the self-distance) positions and use as much space. they can also find, using o(n) samples and space, the largest/smallest period, and/or all of the approximate periods of s. these algorithms can also be viewed as working on streaming inputs where each data item is seen once and in order, storing only a sublinear (o(&sqrt;nlog2 n) or o(&sqrt;nlog4 n)) size sample from which periodicities are identified.
facility location with hierarchical facility costs. we consider the facility location problem with hierarchical facility costs, and give a (4.236 + &epsilon;)-approximation algorithm using local search. the hierarchical facility location problem models multilevel service installation costs. shmoys, swamy and levi [13] gave an approximation algorithm for a two-level version of the problem. here we consider a multilevel problem, and give a constant factor approximation algorithm, independent of the number of levels, for the case of identical costs on all facilities.
a 4 kernel for feedback vertex set. we prove that given an undirected graph g on n vertices and an integer k, one can compute, in polynomial time in n, a graph g&prime; with at most 4k2 vertices and an integer k&prime; such that g has a feedback vertex set of size at most k iff g&prime; has a feedback vertex set of size at most k&prime;. this result improves a previous o(k11) kernel of burrage et al., and a more recent cubic kernel of bodlaender. this problem was communicated by fellows.
a fast algorithm to generate open meandric systems and meanders. an open meandric system is a planar configuration of acyclic curves crossing an infinite horizontal line in the plane such that the curves may extend in both horizontal directions. we present a fast, recursive algorithm to exhaustively generate open meandric systems with n crossings. we then illustrate how to modify the algorithm to generate unidirectional open meandric systems (the curves extend only to the right) and nonisomorphic open meandric systems where equivalence is taken under horizontal reflection. each algorithm can be modified to generate systems with exactly k curves. in the unidirectional case when k &equals; 1, we can apply a minor modification along with some additional optimization steps to yield the first fast and simple algorithm to generate open meanders.
a linear-time algorithm to find a separator in a graph excluding a minor. let g be an n-vertex m-edge graph with weighted vertices. a pair of vertex sets a, b &sube; v(g) is a 2/3-separation of order &verbar;a &cap; b&verbar; if a &cup; b &equals; v(g), there is no edge between a &minus; b and b &minus; a, and both a &minus; b and b &minus; a have weight at most 2/3 the total weight of g. let &ell; &isin; z+ be fixed. alon et al. [1990] presented an algorithm that in o(n1/2m) time, outputs either a k&ell;-minor of g, or a separation of g of order o(n1/2). whether there is a o(n + m)-time algorithm for this theorem was left as an open problem. in this article, we obtain a o(n + m)-time algorithm at the expense of a o(n2/3) separator. moreover, our algorithm exhibits a trade-off between time complexity and the order of the separator. in particular, for any given &epsi; &isin; [0,1/2], our algorithm outputs either a k&ell;-minor of g, or a separation of g with order o(n(2&minus;&epsi;)/3 in o(n1 + &epsi;+m) time. as an application we give a fast approximation algorithm for finding an independent set in a graph with no k&ell;-minor.
approximating the distance to monotonicity in high dimensions. in this article we study the problem of approximating the distance of a function f: [n]d &rarr; r to monotonicity where [n] &equals; {1,&ldots;,n} and r is some fully ordered range. namely, we are interested in randomized sublinear algorithms that approximate the hamming distance between a given function and the closest monotone function. we allow both an additive error, parameterized by &delta;, and a multiplicative error. previous work on distance approximation to monotonicity focused on the one-dimensional case and the only explicit extension to higher dimensions was with a multiplicative approximation factor exponential in the dimension d. building on goldreich et al. [2000] and dodis et al. [1999], in which there are better implicit results for the case n&equals;2, we describe a reduction from the case of functions over the d-dimensional hypercube [n]d to the case of functions over the k-dimensional hypercube [n]k, where 1&le; k&le; d. the quality of estimation that this reduction provides is linear in &lceil; d/k &rceil; and logarithmic in the size of the range &vert; r &vert; (if the range is infinite or just very large, then log &vert; r &vert; can be replaced by d log n). using this reduction and a known distance approximation algorithm for the one-dimensional case, we obtain a distance approximation algorithm for functions over the d-dimensional hypercube, with any range r, which has a multiplicative approximation factor of o(dlog &vert; r &vert;). for the case of a binary range, we present algorithms for distance approximation to monotonicity of functions over one dimension, two dimensions, and the k-dimensional hypercube (for any k&ge; 1). applying these algorithms and the reduction described before, we obtain a variety of distance approximation algorithms for boolean functions over the d-dimensional hypercube which suggest a trade-off between quality of estimation and efficiency of computation. in particular, the multiplicative error ranges between o(d) and o(1).
a near-optimal algorithm for estimating the entropy of a stream. we describe a simple algorithm for approximating the empirical entropy of a stream of m values up to a multiplicative factor of (1+&epsi;) using a single pass, o(&epsi;&minus;2 log (&delta;&minus;1) log m) words of space, and o(log &epsi;&minus;1 + log log &delta;&minus;1 + log log m) processing time per item in the stream. our algorithm is based upon a novel extension of a method introduced by alon et al. [1999]. this improves over previous work on this problem. we show a space lower bound of &omega;(&epsi;&minus;2/log2 (&epsi;&minus;1)), demonstrating that our algorithm is near-optimal in terms of its dependency on &epsi;. we show that generalizing to multiplicative-approximation of the kth-order entropy requires close to linear space for k&ge;1. in contrast we show that additive-approximation is possible in a single pass using only poly-logarithmic space. lastly, we show how to compute a multiplicative approximation to the entropy of a random walk on an undirected graph.
approximating corridors and tours via restriction and relaxation techniques. given a rectangular boundary partitioned into rectangles, the minimum-length corridor (mlc-r) problem consists of finding a corridor of least total length. a corridor is a set of connected line segments, each of which must lie along the line segments that form the rectangular boundary and/or the boundary of the rectangles, and must include at least one point from the boundary of every rectangle and from the rectangular boundary. the mlc-r problem is known to be np-hard. we present the first polynomial-time constant ratio approximation algorithm for the mlc-r and mlck problems. the mlck problem is a generalization of the mlc-r problem where the rectangles are rectilinear c-gons, for c &le; k and k is a constant. we also present the first polynomial-time constant ratio approximation algorithm for the group traveling salesperson problem (gtsp) for a rectangular boundary partitioned into rectilinear c-gons as in the mlck problem. our algorithms are based on the restriction and relaxation approximation techniques.
an approximation algorithm for the maximum leaf spanning arborescence problem. we present an o(&sqrt;opt)-approximation algorithm for the maximum leaf spanning arborescence problem, where opt is the number of leaves in an optimal spanning arborescence. the result is based upon an o(1)-approximation algorithm for a special class of directed graphs called willows. incorporating the method for willow graphs as a subroutine in a local improvement algorithm gives the bound for general directed graphs.
adaptive sampling strategies for quickselects. quickselect with median-of-3 is largely used in practice and its behavior is fairly well understood. however, the following natural adaptive variant, which we call proportion-from-3, had not been previously analyzed: &ldquo;choose as pivot the smallest of the sample if the relative rank of the sought element is below 1/3, the largest if the relative rank is above 2/3, and the median if the relative rank is between 1/3 and 2/3.&rdquo; we first analyze the average number of comparisons made when using proportion-from-2 and then for proportion-from-3. we also analyze &nu;-find, a generalization of proportion-from-3 with interval breakpoints at &nu; and 1-&nu;. we show that there exists an optimal value of &nu; and we also provide the range of values of &nu; where &nu;-find outperforms median-of-3. then, we consider the average total cost of these strategies, which takes into account the cost of both comparisons and exchanges. our results strongly suggest that a suitable implementation of &nu;-find could be the method of choice in a practical setting. we also study the behavior of proportion-from-s with s>3 and in particular we show that proportion-from-s-like strategies are optimal when s&rarr;&infin;.
achieving anonymity via clustering. publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. the traditional approach of deidentifying records is to remove identifying fields such as social security number, name, etc. however, recent research has shown that a large fraction of the u.s. population can be identified using nonkey attributes (called quasi-identifiers) such as date of birth, gender, and zip code. the k-anonymity model protects privacy via requiring that nonkey attributes that leak information are suppressed or generalized so that, for every record in the modified table, there are at least k&minus;1 other records having exactly the same values for quasi-identifiers. we propose a new method for anonymizing data records, where quasi-identifiers of data records are first clustered and then cluster centers are published. to ensure privacy of the data records, we impose the constraint that each cluster must contain no fewer than a prespecified number of data records. this technique is more general since we have a much larger choice for cluster centers than k-anonymity. in many cases, it lets us release a lot more information without compromising privacy. we also provide constant factor approximation algorithms to come up with such a clustering. this is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k. we further observe that a few outlier points can significantly increase the cost of anonymization. hence, we extend our algorithms to allow an &epsi; fraction of points to remain unclustered, that is, deleted from the anonymized publication. thus, by not releasing a small fraction of the database records, we can ensure that the data published for analysis has less distortion and hence is more useful. our approximation algorithms for new clustering objectives are of independent interest and could be applicable in other clustering scenarios as well.
clustering for metric and nonmetric distance measures. we study a generalization of the k-median problem with respect to an arbitrary dissimilarity measure d. given a finite set p of size n, our goal is to find a set c of size k such that the sum of errors d(p,c) &equals; &sum;p &in; p minc &in; c {d(p,c)} is minimized. the main result in this article can be stated as follows: there exists a (1+&epsis;)-approximation algorithm for the k-median problem with respect to d, if the 1-median problem can be approximated within a factor of (1+&epsis;) by taking a random sample of constant size and solving the 1-median problem on the sample exactly. this algorithm requires time n2o(mklog(mk/&epsis;)), where m is a constant that depends only on &epsis; and d. using this characterization, we obtain the first linear time (1+&epsis;)-approximation algorithms for the k-median problem in an arbitrary metric space with bounded doubling dimension, for the kullback-leibler divergence (relative entropy), for the itakura-saito divergence, for mahalanobis distances, and for some special cases of bregman divergences. moreover, we obtain previously known results for the euclidean k-median problem and the euclidean k-means problem in a simplified manner. our results are based on a new analysis of an algorithm of kumar et al. [2004].
geodesic delaunay triangulations in bounded planar domains. we introduce a new feature size for bounded domains in the plane endowed with an intrinsic metric. given a point x in a domain x, the systolic feature size of x at x measures half the length of the shortest loop through x that is not null-homotopic in x. the resort to an intrinsic metric makes the systolic feature size rather insensitive to the local geometry of the domain, in contrast with its predecessors (local feature size, weak feature size, homology feature size). this reduces the number of samples required to capture the topology of x, provided that a reliable approximation to the intrinsic metric of x is available. under sufficient sampling conditions involving the systolic feature size, we show that the geodesic delaunay triangulation dx(l) of a finite sampling l is homotopy equivalent to x. under similar conditions, dx(l) is sandwiched between the geodesic witness complex cwx(l) and a relaxed version cwx,&nu;(l). in the conference version of the article, we took advantage of this fact and proved that the homology of dx(l) (and hence the one of x) can be retrieved by computing the persistent homology between cwx(l) and cwx,&nu;(l). here, we investigate further and show that the homology of x can also be recovered from the persistent homology associated with inclusions of type cwx,&nu;(l)&rarrhk;cwx,&nu;&prime;(l), under some conditions on the parameters &nu;&le;&nu;&prime;. similar results are obtained for vietoris-rips complexes in the intrinsic metric. the proofs draw some connections with recent advances on the front of homology inference from point cloud data, but also with several well-known concepts of riemannian (and even metric) geometry. on the algorithmic front, we propose algorithms for estimating the systolic feature size of a bounded planar domain x, selecting a landmark set of sufficient density, and computing the homology of x using geodesic witness complexes or rips complexes.
finding equitable convex partitions of points in a polygon efficiently. previous work has developed algorithms for finding an equitable convex partition that partitions the plane into n convex pieces each containing an equal number of red and blue points. motivated by a vehicle routing heuristic, we look at a related problem where each piece must contain one point and an equal fraction of the area of some convex polygon. we first show how algorithms for solving the older problem lead to approximate solutions for this new equitable convex partition problem. then we demonstrate a new algorithm that finds an exact solution to our problem in o(n nlog n) time or operations, where n is the number of points, m the number of vertices or edges of the polygon, and n:&equals;n+m the sum.
nondecreasing paths in a weighted graph or: how to optimally read a train schedule. a travel booking office has timetables giving arrival and departure times for all scheduled trains, including their origins and destinations. a customer presents a starting station and demands a route with perhaps several train connections taking him to his destination as early as possible. the booking office must find the best route for its customers. this problem was first considered in the theory of algorithms by minty [1958], who reduced it to a problem on directed edge-weighted graphs: find a path from a given source to a given target such that the consecutive weights on the path are nondecreasing and the last weight on the path is minimized. minty gave the first algorithm for the single-source version of the problem, in which one finds minimum last weight nondecreasing paths from the source to every other vertex. in this article we give the first linear-time algorithm for this problem in the word-ram model of computation. we also define an all-pairs version for the problem and give a strongly polynomial truly subcubic algorithm for it. finally, we discuss an extension of the problem in which one also has prices on trip segments and one wishes to find a cheapest valid itinerary.
mind change complexity of inferring unbounded unions of restricted pattern languages from positive data. this paper shows that the mind change complexity of inferring from positive data the class of unbounded unions of languages of regular patterns with constant segment length bound is of the form @w^@w^^^@a+@b, assuming that the patterns are defined over a finite alphabet containing at least two elements. here @a and @b are natural numbers, and we give tight bounds on their values based on the length of the constant segments and the size of the alphabet of the pattern languages. this is, to the authors' knowledge, the first time a natural class of languages has been shown to be inferable with mind change complexity above @w^@w. the proof uses the notion of closure operators on a class of languages, and also uses the order type of well-partial-orderings to obtain a mind change bound. the inference algorithm presented can be easily applied to a wide range of classes of languages. finally, we show an interesting connection between proof theory and mind change complexity.
comparing free algebras in topological and classical domain theory. we compare how computational effects are modelled in classical domain theory and topological domain theory. both of these theories provide powerful toolkits for denotational semantics: classical domain theory having been introduced by scott, and well established and developed since; topological domain theory being a generalization in which topologies more general than the scott-topology are admitted. computational effects can be modelled using free algebra constructions, according to plotkin and power, and we show that for a wide range of computational effects, including all the classical powerdomains, this free algebra construction coincides in classical and topological domain theory, when restricted to countably-based continuous domains.