waashk/dblp huggingface dataset:
approximation algorithm for embedding metrics into a two-dimensional space. in this paper, we present a polynomial-time approximation algorithm for computing an embedding of an arbitrary metric into a two-dimensional space. the algorithm finds an embedding whose additive distortion is at most c&epsilon;*, where &epsilon;* is the smallest additive distortion possible and c is an absolute constant. to our knowledge, this is the first result of this type, i.e., it gives an algorithm that finds (approximately) optimal embedding of a given distance matrix into a fixed d-dimensional space, where d < 1 is low, under any standard definition of embedding (see related work).
smaller core-sets for balls. given a set of points p &sub; rd and value ∊ > 0, an ∊-core-set s &sub; p has the property that the smallest ball containing s is an ∊-approximation of the smallest ball containing p. this paper shows that any point-set has an ∊-core-set of size [2/∊]. we also give a fast algorithm that finds this core-set. these results imply the existence of small core-sets for solving approximate k-center clustering and related problems. the sizes of these core-sets are considerably smaller than the previously known bounds, and imply faster algorithms; one such algorithm needs o(dn/∊ + (l/∊)5) time to compute an ∊-approximate minimum enclosing ball (1-center) of n points in d dimensions. a simple gradient-descent algorithm is also given, for computing the minimum enclosing ball in o(dn/∊2) time. this algorithm also implies slightly faster algorithms for computing approximately the smallest radius k-flat fitting a set of points.
approximation algorithms for low-distortion embeddings into low-dimensional spaces. we present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. among other results, we give an o(&radic;n)-approximation algorithm for the problem of finding a line embedding of a metric induced by a given unweighted graph, that minimizes the (standard) multiplicative distortion. we give an improved &otilde;(n1/3) approximation for the case of metrics generated by unweighted trees. this is the first result of this type.
approximation algorithms for data placement in arbitrary networks. we study approximation algorithms for placing replicated data in arbitrary networks. consider a network of nodes with individual storage capacities and a metric communication cost function, in which each node periodically issues a request for an object drawn from a collection of uniform-length objects. we consider the problem of placing copies of the objects among the nodes such that the average access cost is minimized. our main result is a polynomial-time constant-factor approximation algorithm for this placement problem. our algorithm is based on a careful rounding of a linear programming relaxation of the problem. we also show that the data placement problem is maxsnp-hard. we extend our approximation result to a generalization of the data placement problem that models additional costs such as the cost of realizing the placement. we also show that when object lengths are non-uniform, a constant-factor approximation is achievable if the capacity at each node in the approximate solution is allowed to exceed that in the optimal solution by the length of the largest object.
loop quantum gravity. one of the great challenges facing physics today is to reconcile quantum theory and general relativity. loop quantum gravity is an approach to this challenge that incorporates quantum theory into our description of spacetime from the very start. quantum states of the geometry of space are described by "spin networks" - graphs with certain labellings of their edges and vertices. the theory predicts that geometrical quantities such as area and volume take on a discrete spectrum of possible values, and it explains the entropy of black holes by associating information to each point at which a spin network edge punctures the event horizon. i will give a nontechnical introduction to these ideas, focussing on some computational challenges that arise in studying this theory. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
counting without sampling: new algorithms for enumeration problems using statistical physics. we propose a new type of approximate counting algorithms for the problems of enumerating the number of independent sets and proper colorings in low degree graphs with large girth. our algorithms are not based on a commonly used markov chain technique, but rather are inspired by recent developments in statistical physics in connection with correlation decay properties of gibbs measures and its implications to uniqueness of gibbs measures on infinite trees, reconstruction problems and local weak convergence methods. on a negative side, our algorithms provide &isin;-approximations only to the logarithms of the size of a feasible set (also known as free energy in statistical physics). but on the positive side, unlike markov chain based algorithms, our approach provides deterministic as opposed to probabilistic guarantee on approximations. moreover, for some regular graphs we obtain explicit values for the counting problem. for example, we show that every 4-regular n-node graph with large girth has asymptotically (1.494 ...)n independent sets, and in every r-regular graph with n nodes and large girth the number of q &ge; r + 1-proper colorings is asymptotically (q(1-1/q)r/2)n for large n. in statistical physics terminology, we compute explicitly the partition function (free energy) in these cases. we extend our results to random regular graphs graphs also. the explicit results obtained in this paper would be hard to derive via markov chain sampling technique.
almost-delaunay simplices: nearest neighbor relations for imprecise points. delaunay tessellations and voronoi diagrams capture proximity relationships among sets of points in any dimension. when point coordinates are not known exactly, as in the case of 3d points representing protein atom coordinates, the delaunay tessellation may not be robust; small perturbations in the coordinates may cause the delaunay simplices to change. in this paper, we define the almost-delaunay simplices, derive some of their properties, and give algorithms for computing them, especially for neighbor analysis in three dimensions. we sketch applications in proteins that will be described more fully in a companion paper in biology. http://www.cs.unc.edu/&sim;debug/papers/almdel.
edge-connectivity augmentation with partition constraints. in the well-solved edge-connectivity augmentation problem we must find a minimum cardinality set $f$ of edges to add to a given undirected graph to make it $k$-edge-connected. this paper solves the generalization where every edge of $f$ must go between two different sets of a given partition of the vertex set. a special case of this partition-constrained problem, previously unsolved, is increasing the edge-connectivity of a bipartite graph to $k$ while preserving bipartiteness. based on this special case we present an application of our results in statics. our solution to the general partition-constrained problem gives a min-max formula for $|f|$ which includes as a special case the original min-max formula of cai and sun \cite{cai} for the problem without partition constraints. when $k$ is even the min-max formula for the partition-constrained problem is a natural generalization of \cite{cai}. however this generalization fails when $k$ is odd. we show that at most one more edge is needed when $k$ is odd and we characterize the graphs that require such an extra edge. we give a strongly polynomial algorithm that solves our problem in time $o(n(m+n\log n)$ $\log n)$. here $n$ and $m$ denote the number of vertices and distinct edges of the graph respectively. this bound is identical to the best-known time bound for the problem without partition constraints. our algorithm is based on the splitting off technique of lov\''asz, like several known efficient algorithms for the unconstrained problem. however unlike previous splitting algorithms, when $k$ is odd our algorithm must handle ``obstacles'''' that prevent all edges from being split off. our algorithm is of interest even when specialized to \nopagebreak the unconstrained problem, because it produces an asymptotically optimum number of distinct splits.
on minimizing the total flow time on multiple machines. we consider the problem of minimizing the total flow time on multiple machines with preemption, where the flow time of a job is the time spent since it arrives until it finishes. our main result is a quasi-polynomial time approximation scheme for a constant number of machines (m). the result also extends to total weighted flow time where either the job weights or the job sizes are polynomially bounded by the number of jobs (n). we also show that the dependence on m cannot be substantially improved. in particular, obtaining an o(1) approximation for the weighted case (even when all weights and sizes are polynomially bounded by n) by an algorithm with running time npolylog(n,m) would imply that np &sub; dtime(npolylog(n)).
approximating the average response time in broadcast scheduling. we consider the problem of approximating the minimum average response time in on-demand data broadcasting systems. the best approximation factors known for this problem involve resource augmentation. we provide the first non-trivial approximation factors in the absence of resource augmentation, achieving an additive o(&radic;n)-approximation, where n is the number of distinct pages. our result can be extended, for any &epsilon; > 0, to a (1 + &epsilon;)-speed, additive o(1/&epsilon;)-approximation algorithm. prior to our work, no non-trivial approximation factor was known for the case of &epsilon; < 1.
improved approximation algorithms for broadcast scheduling. we consider two scheduling problems in the broadcast setting. the first is that of minimizing the average response time of requests. for the offline version of this problem we give an algorithm with an approximation ratio of o(log2 (n)/ log log(n)), where n is the total number of pages. this substantially improves the previously best known approximation factor of o(&radic;n) for the problem [3]. our second result is for the profit maximization version of the broadcast scheduling problem. here each request has a deadline and a profit which is obtained if the request is satisfied before its deadline. the goal is to maximize the total profit. we give an algorithm with an approximation ratio of 5/6, which improves the previously best known approximation guarantee of 3/4 for the problem [13].
minimizing weighted flow time. we consider the problem of minimizing weighted flow time on a single machine in the preemptive setting. our main result is an o(log w) competitive online algorithm where the maximum to the minimum ratio of weights is w. more generally our algorithm achieves a competitive ratio of k if there are k weight classes. this gives the first o(1)-competitive algorithm for constant k. no o(1) competitive algorithm was known previously even for the special case of k = 2. these results settle a question posed by chekuri et al [5] about the existence of a "truly" online algorithm with a non-trivial competitive ratio. we also give a "semi-online" algorithm with competitive ratio o(log n + log p), where p is ratio of the maximum to minimum job size. our second result deals with the non-clairvoyant setting where the job sizes are unknown (but the weight of the jobs are known). we consider the resource augmentation model, and give a non-clairvoyant online algorithm, which if allowed a (1 + &epsilon;) speed-up, is (1 + l/&epsilon;) competitive against an optimal offline, clairvoyant algorithm.
job shop scheduling with unit processing times. we consider randomized algorithms for the preemptive job shop problem, or equivalently, the case in which all operations have unit length. we give an α-approximation for the case of two machines where α o(log m/log log m) for an arbitrary number m of machines, and the first (2 + ε)-approximation for a constant number of machines. the first result is via an approximation algorithm for a string matching problem that is of independent interest.
new approximability and inapproximability results for 2-dimensional bin packing. we study the 2-dimensional generalization of the classical bin packing problem: given a collection of rectangles of specified size (width, height), the goal is to pack these into minimum number of square bins of unit size. a long history of results exists for this problem and its special cases [3, 14, 10, 18, 9, 1, 15]. currently, the best known approximation algorithm achieves a guarantee of 1.69 in the asymptotic case (i.e. when the optimum uses a large number of bins) [1]. however, an important open question has been whether 2-dimensional bin packing is essentially similar to the 1-dimensional case in that it admits an asymptotic polynomial time approximation scheme (aptas) [8, 13] or not? we answer the question in the negative and show that the problem is apx hard in the asymptotic case. on the other hand, we give an asymptotic ptas for the special case when all the rectangles to be packed are squares (or more generally hypercubes). this improves upon the previous best known guarantee of 1.454 for d = 2 [9] and 2 - (2/3)d for d > 2 [15], and settles the approximability for this special case.
scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. power management policies aim at reducing the amount of energy consumed by battery operated systems, while keeping the overall performance high. in this paper we focus on shut-down mechanisms that put a system into a sleep state when it is idle. a very small amount of energy is consumed in this state but, a fixed amount of energy is required when moving the system from the sleep state to the active state. the offline version of this problem consists in scheduling a set of unit execution tasks, with release dates and deadlines, on a single machine in order to minimize the number of idle time periods. we show that this problem can be solved in polynomial time by dynamic programming.
on-line navigation in a room. we consider the problem of navigating through an unknown environment in which the obstacles are disjoint oriented rectangles enclosed in an n x n square room. the task of navigating algorithm is to reach the center of the room starting from one of the corners. while there always exists a path of length n, the best previously known navigating algorithm finds paths of length n201nn . we give an efficient deterministic algorithm which finds a path of length o(n ln n); this algorithm uses tactile information only. moreover, we prove that any deterministic algorithm can be forced to traverse a distance of &ohgr;(n ln n), even if it uses visual information.
competitive on-line switching policies. a switch, or server, serves n input queues, processing messages arriving at these queues to a single output channel. at each time slot the switch can process a single message from one of the queues. the goal of a switching policy is to minimize the size of the buffers at the input queues that maintain the messages that have not yet been processed. this is a typical on-line setting in which decisions are made based on the current state without knowledge of future events. this general scenario models multiplexing tasks in various systems such as communication networks, cable modem systems, and traffic control. traditionally, researchers analyzed the performance of a given policy assuming some distribution on the arrival rates of messages at the input queues, or by assuming that the service rate is at least the aggregate of all the input rates. we use competitive analysis to analyze switching service policies, thus avoiding any prior assumptions on the input. specifically, we show o(log n)-competitive switching policies for the problem and demonstrate matching lower bounds.
throughput maximization of real-time scheduling with batching. we consider the following scheduling with batching problem that has many applications, e.g., in multimedia-on-demand and manufacturing of integrated circuits. the input to the problem consists of n jobs and k parallel machines. each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or non-explicitly), a weight, and a family. each family is associated with a processing time. jobs that belong to the same family can be batched and executed together on the same machine. the processing time of each batch is the processing time of the family of jobs it contains. the goal is to find a non-preemptive schedule with batching that maximizes the weight of the scheduled jobs. we give constant factor (4 or 4 + &epsilon;) approximation algorithms for two variants of the problem, depending on the precise representation of the input. when the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + &epsilon;, respectively. we also show exact algorithms for several special cases.
competitive on-line stream merging algorithms for media-on-demand. we consider the problem of minimizing the bandwidth needed by media-on-demand servers that use stream merging. we consider the on-line case where client requests are not known ahead of time. to facilitate stream merging, clients have the ability to receive data from two streams simultaneously and can buffer up to half of a full stream. we present a new family of on-line stream merging algorithms called dynamic tree algorithms. the bandwidth requirements of the best of these, the dynamic fibonacci tree algorithms, are within a factor of the minimum between logφ(n) + o(1) and logφ(1/(2d)) + o(1) from the off-line optimal, where n is the number of requests, d is the guaranteed maximum start-up delay measured as a fraction of the time for a full stream, and φ = (1 + √5)/2. the new on-line algorithms use a dynamic fibonacci tree to control how new arrivals should merge with existing streams. empirical studies show that the dynamic fibonacci tree algorithms perform much better than indicated by the analysis.
windows scheduling problems for broadcast systems. the windows scheduling problem is defined by the positive integers n, h, and w1, ...,wn. there are n pages where the window wi is associated with page i, and h is the number of slotted channels available for broadcasting the pages. a schedule that solves the problem assigns pages to slots such that the gap between any two consecutive appearances of page i is at most wi slots. we investigate two optimization problems. (i) the optimal windows scheduling problem: given w1, ..., wn find a schedule in which h is minimized. (ii) the optimal harmonic windows scheduling problem: given h find a schedule for the windows wi = i in which n is maximized. the former is a formulation of the problem of minimizing the bandwidth in push systems that support guaranteed delay, and the latter is a formulation of the problem of minimizing the startup delay in media-on-demand systems. for the optimal windows scheduling problem we present an algorithm that constructs asymptotically close to optimal schedules, and for the optimal harmonic windows scheduling problem we show how to achieve the largest known n's for all values of h.
scheduling techniques for media-on-demand. broadcasting popular media to clients is the ultimate scalable solution for media-on-demand. recently, it was shown that if clients can receive data at a rate faster than what they need for playback and if they can store later parts of the media in their buffers, then much higher scalability may be obtained. in the paper we focus on scheduling problems arising from these new systems for media-on-demand.for given amount of bandwidth, we improve the guaranteed start-up delay time for an uninterrupted playback. we achieve our results by introducing two techniques. in the first, the media is arranged on the channels such that clients gain from buffering later parts of the transmission before the actual start of the playback. in the second, segments of different media may be mixed together on the same channel. we introduce a simple class of recursive round-robin scheduling algorithms that implement our techniques.our results improve the best known asymptotic results. moreover, our scheduling algorithms outperform known results for "practical" values for number of media and number of broadcasting channels. for some specific small values, we present hand designed solutions that are better than those achieved by our algorithms.
windows scheduling as a restricted version of bin packing. given is a sequence of n positive integers w1;w2....,wn that are associated with the items 1, 2....n respectively. in the windows scheduling problem, the goal is to schedule all the items (equal length information pages) on broadcasting channels such that the gap between two consecutive appearances of page i on any of the channels is at most wi slots (a slot is the transmission time of one page). in the unit fractions bin packing problem, the goal is to pack all the items in bins of unit size where the size (width) of item i is 1/wi. the optimization objective is to minimize the number of channels or bins. in the off-line setting the sequence is known in advance whereas in the on-line setting the items arrive in order and assignment decisions are irrevocable. since a page requires at least 1=wi of the channel's bandwidth, it follows that windows scheduling without migration (all broadcasts of a page must be from the same channel) is a restricted version of unit fractions bin packing.let h = [&sigma;ni = 1 (1/wi)] be the obvious bandwidth lower bound on the required number of bins (channels). previously an h + o(ln h) off-line algorithm for the windows scheduling problem was known. this paper presents an h + 1 off-line algorithm to the unit fractions bin packing problem. in the on-line setting, this paper presents an h + o(&radic;h) algorithm to both problems where the one for the unit fractions bin packing problem is simpler. on the other hand, this paper shows that already for the unit fractions bin packing problem, any on-line algorithm must use at least h + &omega; (ln h) bins.
guaranteeing fair service to persistent dependent tasks. we introduce a new scheduling problem that is motivated by applications in the area of access and flow control in high-speed and wireless networks. an instance of the problem consists of a set of persistent tasks that have to be scheduled repeatedly. each task has a demand to be scheduled "as often as possible." there is no explicit limit on the number of tasks that can be scheduled concurrently. however, such limits are imposed implicitly because some tasks may be in conflict and cannot be scheduled simultaneously. these conflicts are presented in the form of a conflict graph. we define parameters which quantify the fairness and regularity of a given schedule. we then proceed to show lower bounds on these parameters and present fair and efficient scheduling algorithms for the case where the conflict graph is an interval graph. some of the results presented here extend to the case of perfect graphs and circular-arc graphs as well.