waashk/dblp huggingface dataset:
maintaining deforming surface meshes. we present a method to maintain a mesh approximating a deforming surface, which is specified by a dense set of sample points. we identify a reasonable motion model for which a provably good surface mesh can be maintained. our algorithm determines the appropriate times at which the mesh is updated to maintain a good approximation. the updates use simple primitives, and no costly computation such as line-surface intersection is necessary. point insertions and deletions are allowed at the updates. each update takes time linear in the size of the current sample set plus the new sample points inserted. we also construct examples for which, under the same model, no other algorithm makes asymptotically fewer changes to the mesh than our algorithm.
bounded-leg distance and reachability oracles. in a weighted, directed graph an l-bounded leg path is one whose constituent edges have length at most l. for any fixed l, computing l-bounded leg shortest paths is just as easy as the standard shortest path algorithm. in this paper we study approximate distance oracles (and reachability oracles) for bounded leg path problems, where the leg bound l is not known in advance, but forms part of the query. bounded-leg path problems are more complicated than standard shortest path problems because the number of distinct shortest paths between two vertices (over all leg bounds) could be as large as the number of edges in the graph. the bounded leg constraint models situations where there is some limited resource that must be spent when traversing an edge. for example, the size of a fuel tank or the life of a battery places a hard limit on how far a vehicle can travel in one leg before refueling or recharging. someone making a long road trip may place a hard limit on how many hours they are willing to drive in any one day. our main result is a nearly optimal algorithm for preprocessing a directed graph in order to answer approximate bounded leg distance and bounded leg shortest path queries. in particular, we can preprocess any graph in &otilde;(n3) time, producing a data structure with size &otilde;(n2) that answers (1 + &isin;)-approximate bounded leg distance queries in o(log log n) time. if the corresponding (1 + &isin;)-approximate shortest path has l edges it can be returned in o(l log log n) time. these bounds are all within polylog(n) factors of the best standard all-pairs shortest path algorithm and improve substantially the previous best bounded leg shortest path algorithm, whose preprocessing time and space are o(n4) and &otilde;(n2.5). we also consider bounded leg oracles in other situations. in the context of planar directed graphs we give a time-space tradeoff for answering bounded leg reachability queries. for any k &ge; 2 we can build a data structure with size o(kn1+1/k) that answers reachability queries in time &otilde;(nk&minus;1/2k).
coresets, sparse greedy approximation, and the frank-wolfe algorithm. the problem of maximizing a concave function f(x) in a simplex s can be solved approximately by a simple greedy algorithm. for given k, the algorithm can find a point x(k) on a k-dimensional face of s, such that f(x(k)) &ge; f(x*) - o(1/k). here f(x*) is the maximum value of f in s. this algorithm and analysis were known before, and related to problems of statistics and machine learning, such as boosting, regression, and density mixture estimation. in other work, coming from computational geometry, the existence of &epsilon;-coresets was shown for the minimum enclosing ball problem, by means of a simple greedy algorithm. similar greedy algorithms, that are special cases of the frank-wolfe algorithm, were described for other enclosure problems. here these results are tied together, stronger convergence results are reviewed, and several coreset bounds are generalized or strengthened.
a constant factor approximation algorithm for -median clustering with outliers. we consider the k-median clustering with outliers problem: given a finite point set in a metric space and parameters k and m, we want to remove m points (called outliers), such that the cost of the optimal k-median clustering of the remaining points is minimized. we present the first polynomial time constant factor approximation algorithm for this problem.
price based protocols for fair resource allocation: convergence time analysis and extension to leontief utilities. we analyze several distributed, continuous time protocols for a fair allocation of bandwidths to flows in a network (or resources to agents). our protocols converge to an allocation which is a logarithmic approximation, simultaneously, to all canonical social welfare functions (i.e. functions which are symmetric, concave, and non-decreasing). these protocols can be started in an arbitrary state. while a similar protocol was known before, it only applied to the simple bandwidth allocation problem, and its stability and convergence time was not understood. in contrast, our protocols also apply to the more general case of leontief utilities, where each user may place a different requirement on each resource. further, we prove that our protocols converge in polynomial time. the best convergence time we prove is o(n log ncmaxamax/cminamin), where n is the number of agents in the network, cmax and cmin are the maximum and minimum capacity of the links, and amax, amin are the largest and smallest leontief coefficients, respectively. this time is achieved by a simple mimd (multiplicative increase, multiplicative decrease) protocol which had not been studied before in this setting. we also identify combinatorial properties of these protocols that may be useful in proving stronger convergence bounds. the final allocations by our protocols are supported by usage-sensitive dual prices which are fair in the sense that they shield light users of a resource from the impact of heavy users. thus our protocols can also be thought of as efficient distributed schemes for computing fair prices.
approximating connected facility location problems via random facility sampling and core detouring. we present a simple randomized algorithmic framework for connected facility location problems. the basic idea is as follows: we run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the facilities serving sampled clients in the approximate solution. via a novel analytical tool, which we term core detouring, we show that this approach significantly improves over the previously best known approximation ratios for several np-hard network design problems. for example, we reduce the approximation ratio for the connected facility location problem from 8.55 to 4.00 and for the single-sink rent-or-buy problem from 3.55 to 2.92. we show that our connected facility location algorithms can be derandomized at the expense of a slightly worse approximation ratio. the versatility of our framework is demonstrated by devising improved approximation algorithms also for other related problems.
empty-ellipse graphs. we define and study a geometric graph over points in the plane that captures the local behavior of delaunay triangulations of points on smooth surfaces in ir3. two points in a planar point set p are neighbors in the empty-ellipse graph if they lie on an axis-aligned ellipse with no point of p in its interior. the empty-ellipse graph can be a clique in the worst case, but it is usually much less dense. specifically, the empty-ellipse graph of n points has complexity &theta;(&delta;n) in the worst case, where &delta; is the ratio between the largest and smallest pairwise distances. for points generated uniformly at random in a rectangle, the empty-ellipse graph has expected complexity &theta;(n log n). as an application of our proof techniques, we show that the delaunay triangulation of n random points on a circular cylinder has expected complexity &theta;(n log n).
ascending auctions for integral (poly)matroids with concave nondecreasing separable values. consider a seller with a fixed set of resources that can produce a variety of bundles from a set e of indivisible goods. several bidders are interested in purchasing a bundle of such goods. their utility for a bundle is privately known and represented by an additively separable, nondecreasing and concave function. in the case when the set of feasible bundles forms an integral polymatroid (or its basis), we present an ascending auction which in equilibrium returns the efficient outcome. formally, given an integral, monotone, submodular function &rho;: e &rarr; n0 with &rho;(&theta;) = 0 the integral points of the polymatroid p&rho; represent various allocations which the seller can feasibly offer. buyers j &isin; n have privately known valuations vj (xj) for xj &isin; p&rho; with the property that vj (xj) = &sigma;e&isin;evje(xje) where the vje(xje) are nondecreasing and concave. we present an ascending auction running in pseudo-polynomial time in which truthful bidding is an ex post equilibrium and results in the efficient outcome. our auction strictly generalizes the ascending auction of demange, gale, and sotomayor (1986) applied to scheduling matroids (agents want to schedule several jobs; their due and release dates are common knowledge, but the value of completing a job is private information). for a suitable class of uniform matroids, our auction reduces to the ascending auction of ausubel (2004) for the allocation of multiple units of a homogeneous good when agents have decreasing marginal values in quantities. finally, our auction can be applied to the setting of spatially distributed markets considered in babaioff, nisan, and pavlov (2004).
a faster cache-oblivious shortest-path algorithm for undirected graphs with bounded edge lengths. we present a cache-oblivious algorithm for computing single-source shortest paths in undirected graphs with non-negative edge lengths. the algorithm incurs o(&radic;(nm log w)/b+(m/b) log n +mst (n, m)) memory transfers on a graph with n vertices, m edges, and real edge lengths between 1 and w; b denotes the cache block size, and mst(n, m) denotes the number of memory transfers required to compute a minimum spanning tree of a graph with n vertices and m edges. our algorithm is the first cache-oblivious shortest-path algorithm incurring less than one memory transfer per vertex if the graph is sparse (m = o(n)) and w = 2&deg;(b).
an elementary construction of constant-degree expanders. we describe a short and easy-to-analyse construction of constant-degree expanders. the construction relies on the replacement product, applied by reingold, vadhan and wigderson (2002) to give an iterative construction of bounded-degree expanders. here we give a simpler construction, which applies the replacement product (only twice!) to turn the cayley expanders of alon and roichman (1994), whose degree is polylog n, into constant-degree expanders. this enables us to prove the required expansion using a simple new combinatorial analysis of the replacement product (instead of the spectral analysis used by reingold, vadhan and wigderson).
complexity of delaunay triangulation for points on lower-dimensional polyhedra. we show that the delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is o(n(d-1)/p). for all 2 &le; p &le; d - 1, this improves on the well-known worst-case bound of o(n&lceil;d/2&rceil;).
improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry. in this paper we consider the online steiner tree problem in weighted directed graphs of bounded edge-asymmetry &alpha;. the edge-asymmetry of a directed graph is defined as the maximum ratio of the cost (weight) of antiparallel edges in the graph. the problem has applications in multicast routing over a network with non-symmetric links. we improve the previously known upper and lower bounds on the competitive ratio of any deterministic algorithm due to faloutsos et al. [11]. in particular, we show that a better analysis of a simple greedy algorithm yields a competitive ratio of o (min {k, &alpha; log k/log log &alpha;}), where k denotes the number of terminals requested. on the negative side, we show a lower bound of &omega;(min{k1-&epsilon;, &alpha; log k/log log k}) on the competitive ratio of every deterministic algorithm for the problem, for any arbitrarily small constant &epsilon;.
on the separation and equivalence of paging strategies. it has been experimentally observed that lru and variants thereof are the preferred strategies for on-line paging. however, under most proposed performance measures for on-line algorithms the performance of lru is the same as that of many other strategies which are inferior in practice. in this paper we first show that any performance measure which does not include a partition or implied distribution of the input sequences of a given length is unlikely to distinguish between any two lazy paging algorithms as their performance is identical in a very strong sense. this provides a theoretical justification for the use of a more refined measure. building upon the ideas of concave analysis by albers et al. [afg05], we prove strict separation between lru and all other paging strategies. that is, we show that lru is the unique optimum strategy for paging under a deterministic model. this provides full theoretical backing to the empirical observation that lru is preferable in practice.
compressing rectilinear pictures and minimizing access control lists. we consider a geometric model for the problem of minimizing access control lists (acls) in network routers, a model that also has applications to rectilinear picture compression and figure drawing in common graphics software packages. here the goal is to create a colored rectilinear pattern within an initially white rectangular canvas, and the basic operation is to choose a subrectangle and paint it a single color, overwriting all previous colors in the rectangle. rectangle rule list (rrl) minimization is the problem of finding the shortest list of rules needed to create a given pattern. acl minimization is a restricted version of this problem where the set of allowed rectangles must correspond to pairs of ip address prefixes. motivated by the acl application, we study the special cases of rrl and acl minimization in which all rectangles must be strips that extend either the full width or the full height of the canvas (strip-rules). we provide several equivalent characterizations of the patterns achievable using strip-rules and present polynomial-time algorithms for optimally constructing such patterns when, as in the acl application, the only colors are black and white (permit or deny). we also show that rrl minimization is np-hard in general and provide o(min(n1/3, opt1/2))-approximation algorithms for general rrl and acl minimization by exploiting our results about strip-rule patterns.
k-means++: the advantages of careful seeding. the k-means method is a widely used clustering technique that seeks to minimize the average squared distance between points in the same cluster. although it offers no accuracy guarantees, its simplicity and speed are very appealing in practice. by augmenting k-means with a very simple, randomized seeding technique, we obtain an algorithm that is &theta;(logk)-competitive with the optimal clustering. preliminary experiments show that our augmentation improves both the speed and the accuracy of k-means, often quite dramatically.
path-independent load balancing with unreliable machines. we consider algorithms for load balancing on unreliable machines. the objective is to optimize the two criteria of minimizing the makespan and minimizing job reassignments in response to machine failures. we assume that the set of jobs is known in advance but that the pattern of machine failures is unpredictable. motivated by the requirements of bgp routing, we consider path-independent algorithms, with the property that the job assignment is completely determined by the subset of available machines and not the previous history of the assignments. we examine first the question of performance measurement of path-independent load-balancing algorithms, giving the measure of makespan and the normalized measure of reassignments cost. we then describe two classes of algorithms for optimizing these measures against an oblivious adversary for identical machines. the first, based on independent random assignments, gives expected reassignment costs within a factor of 2 of optimal and gives a makespan within a factor of o (log m/log log m) of optimal with high probability, for unknown job sizes. the second, in which jobs are first grouped into bins and at most one bin is assigned to each machine, gives constant-factor ratios on both reassignment cost and makespan, for known job sizes. several open problems are discussed.
sandpile transience on the grid is polynomially bounded. we study the process of adding one grain at a time in the abelian sandpile model (asm) based on the n x n grid (bak et al., 1988, dhar, 1990, dhar et al., 1995). we prove that within a polynomial (in n) number of steps, we necessarily reach a recurrent configuration regardless of the choice of sites where the grains are dropped. this adds credence to the common notion that "recurrence" represents "longterm behavior" of the system.
harmonic algorithm for 3-dimensional strip packing problem. in the three dimensional strip packing problem, we are given a set of three-dimensional rectangular items i = {(xi, yi, zi) : i = 1, ..., n} and a three dimensional box b. the goal is to pack all the items in the box b without any overlap, such that the height of the packing is minimized. we consider the most basic version of the problem, where the items must be packed with their edges parallel to the edges of b and cannot be rotated. building upon caprara's work [4] for the two dimensional bin packing problem we obtain an approximation algorithm with a similar performance guarantee of t&infin; &ap; 1.69 where t&infin; is the well known harmonic number that occurs naturally in the context of bin packing. the previously known approximation algorithms for this problem had worst case performance guarantees of 2 [7], 2.64 [14], 2.67 [15], 2.89 [10] and 3.25 [11]. our second algorithm is an asymptotic ptas for the case in which all items have square bases.
speed scaling for weighted flow time. in addition to the traditional goal of efficiently managing time and space, many computers now need to efficiently manage power usage. for example, intel's speedstep and amd's powernow technologies allow the windows xp operating system to dynamically change the speed of the processor to prolong battery life. in this setting, the operating system must not only have a job selection policy to determine which job to run, but also a speed scaling policy to determine the speed at which the job will be run. these policies must be online since the operating system does not in general have knowledge of the future. in current cmos based processors, the speed satisfies the well known cube-root-rule, that the speed is approximately the cube root of the power [mud01, bbs+00]. thus, in this work, we make the standard generalization that the power is equal to speed to some power &alpha; &ge; 1, where one should think of &alpha; as being approximately 3 [yds95, bkp04]. energy is power integrated over time. the operating system is faced with a dual objective optimization problem as it both wants to conserve energy, and optimize some quality of service (qos) measure of the resulting schedule.
a polynomial-time approximation scheme for steiner tree in planar graphs. we give an o(n log n) approximation scheme for steiner tree in planar graphs.
fast computation of power series solutions of systems of differential equations. we propose algorithms for the computation of the first n terms of a vector (or a full basis) of power series solutions of a linear system of differential equations at an ordinary point, using a number of arithmetic operations that is quasi-linear with respect to n. similar results are also given in the non-linear case. this extends previous results obtained by brent and kung for scalar differential equations of order 1 and 2.
on the bandwidth conjecture for 3-colourable graphs. a conjecture by bollob&aacute;s and koml&oacute;s states that for every &gamma; > 0 and integers r &ge; 2 and &delta;, there exists &beta; > 0 such that for sufficiently large n the following holds: if g is a graph on n vertices with minimum degree at least (r-1/r+&gamma;)n and h is an r-chromatic graph on n vertices with bandwidth at most &beta;n and maximum degree at most &delta;, then g contains a copy of h. this conjecture generalises several results concerning sufficient degree conditions for the containment of spanning subgraphs. we prove the conjecture for the case r = 3. our proof yields a polynomial time algorithm for embedding h into g if h is given together with a 3-colouring and vertex labelling respecting the bandwidth bound.
on extremal subgraphs of random graphs. let &kappa;l denote the complete graph on l vertices. we prove that there is a constant c = c(l) > 0, such that whenever p &ge; n-c, with probability tending to 1 when n goes to infinity, every maximum &kappa;l-free subgraph of the binomial random graph gn, p is (l-1)-partite. this answers a question of babai, simonovits and spencer [3]. the proof is based on a tool of independent interest: we show, for instance, that the maximum cut of almost all graphs with m edges, where m &gt; n, is nearly unique. more precisely, given a maximum cut c of gn, m, we can obtain all maximum cuts by moving at most o (&radic;n3/m) vertices between the parts of c.
single source multiroute flows and cuts on uniform capacity networks. for an integer h &ge; 1, an elementary h-route flow is a flow along h edge disjoint paths between a source and a sink, each path carrying a unit of flow, and a single commodity h-route flow is a non-negative linear combination of elementary h-flows. an instance of a single source multicommodity flow problem for a graph g = (v, e) consists of a source vertex s &epsilon; v and k sinks t1,..., tk &epsilon; v; we denote it i = (s; t1,..., tk). in the single source multicommodity multiroute flow problem, we are given an instance i = (s; t1,..., tk) and an integer h &ge; 1, and the objective is to maximize the total amount of flow that is transferred from the source to the sinks so that the capacity constraints are obeyed and, moreover, the flow of each commodity is an h-route flow. we study the relation between classical and multiroute single source flows on networks with uniform capacities and we provide a tight bound. in particular, we prove the following result. given an instance &ge; = (s; t1,...,tk) such that each s - ti pair is h-connected, the maximum classical flow between s and the ti's is at most 2(1 - 1/h)-times larger than the maximum h-route flow between s and the ti's and this is the best possible bound for h &ge; 2. this, as we show, is in contrast to the situation of general multicommodity multiroute flows that are up to k(1 - 1/h)-times smaller than their classical counterparts. as a corollary, we establish a max-flow min-cut theorem for the single source multicommodity multiroute flow and cut. an h-disconnecting cut for i is a set of edges f &sube; e such that for each i, the maximum h-flow between s - ti is zero. we show that the maximum h-flow is within 2(h-1) of the mininimum h-disconnecting cut, independently of the number of commodities; we also describe a 2(h - 1)-approximation algorithm for the minimum h-disconnecting cut problem.