waashk/dblp huggingface dataset:
earth mover distance over high-dimensional spaces. the earth mover distance (emd) between two equal-size sets of points in ℝd is defined to be the minimum cost of a bipartite matching between the two pointsets. it is a natural metric for comparing sets of features, and as such, it has received significant interest in computer vision. motivated by recent developments in that area, we address computational problems involving emd over high-dimensional pointsets. a natural approach is to embed the emd metric into l1, and use the algorithms designed for the latter space. however, khot and naor [kn06] show that any embedding of emd over the d-dimensional hamming cube into l1 must incur a distortion &omega;(d), thus practically losing all distance information. we circumvent this roadblock by focusing on sets with cardinalities upper-bounded by a parameter s, and achieve a distortion of only o(log s &middot; log d). since in applications the feature sets have bounded size, the resulting distortion is much smaller than the &omega;(d) lower bound. our approach is quite general and easily extends to emd over ℝd. we then provide a strong lower bound on the multi-round communicatic complexity of estimating emd, which in particular strengthens the known non-embeddability result of [kn06]. our bound exhibits a smooth tradeoff between approximation and communication, and for example implies that every algorithm that estimates emd using constant size sketches can only achieve &omega;(log s) approximation.
computational advertising. computational advertising is an emerging new scientific sub-discipline, at the intersection of large scale search and text analysis, information retrieval, statistical modeling, machine learning, classification, optimization, and microeconomics. the central challenge of computational advertising is to find the "best match" between a given user in a given context and a suitable advertisement. the context could be a user entering a query in a search engine ("sponsored search"), a user reading a web page ("content match" and "display ads"), a user watching a movie on a portable device, and so on. the information about the user can vary from scarily detailed to practically nil. the number of potential advertisements might be in the billions. thus, depending on the definition of "best match" this challenge leads to a variety of massive optimization and search problems, with complicated constraints.
polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. the multidimensional bin packing and vector bin packing problems are known to not have asymptotic polynomial-time approximation schemes (unless p = np). nevertheless, we show that: &bull; any smoothed (randomly perturbed) instance, and any instance from a class of other distributions, does have a polynomial-time probable approximation scheme. namely, for any fixed &epsilon; > 0, we exhibit a linear-time algorithm that finds a (1+ &epsilon;)-approximate packing with probability 1 - 2-&omega;(n) over the space of random inputs. &bull; there exists an oblivious algorithm that does not know from which distribution inputs come, and still asymptotically does almost as well as the previous algorithms. the oblivious algorithm outputs almost surely a (1 + &epsilon;)-approximation for every &epsilon; > 0. &bull; for vector bin packing, for each considered class of random instances, there exists an algorithm that in expected linear time computes a (1 + &epsilon;)-approximation, for any fixed &epsilon; > 0. to achieve these results we develop a multidimensional version of the one-dimensional rounding technique introduced by fernadez de la vega and lueker. our results generalize karp, luby and marchetti-spaccamela's results on approximatibility of random instances of multidimensional bin packing to a much wider class of distributions.
minimum weight convex steiner partitions. new tight bounds are presented on the minimum length of planar straight line graphs connecting n given points in the plane and having convex faces. specifically, we show that the convex steiner partition of n points in the plane is at most o(log n/log log n) times longer than their euclidean minimum spanning tree (emst), and this bound is best possible. without allowing steiner points, the corresponding bound is known to be &theta;(log n), attained for n points lying along a pseudo-triangle. we also show that the convex steiner partition of n points along a pseudo-triangle is at most o(log log n) times longer than the emst, and this bound is also best possible. our methods are constructive and lead to polynomial-time algorithms for computing convex steiner partitions within these bounds in both cases.
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 city 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 george minty [14], 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 paper we give the first linear time algorithm for this problem. we also define an all pairs version for the problem and give a strongly polynomial truly subcubic algorithm for it.
a network formation game for bipartite exchange economies. we introduce a natural new network formation game in which buyers and sellers may purchase edges representing trading opportunities between themselves, and then accrue wealth in the resulting exchange economy. our main result is an exact characterization of the set of bipartite graphs g that are nash equilibria for this game. this characterization provides sharp limits on the amount and structure of wealth variation that can occur, as well as on the allowable equilibrium exchange rates.
finding one tight cycle. a cycle on a combinatorial surface is tight if it as short as possible in its (free) homotopy class. we describe an algorithm to compute a single tight, non-contractible, simple cycle on a given orientable combinatorial surface in o(n log n) time. the only method previously known for this problem was to compute the globally shortest non-contractible or non-separating cycle in o(min{g3, n} n log n) time, where g is the genus of the surface. as a consequence, we can compute the shortest cycle freely homotopic to a chosen boundary cycle in o(n log n) time and a tight octagonal decomposition in o(gn log n) time.
fast load balancing via bounded best response. it is known that the dynamics of best response in an environment of non-cooperative users may converge to a good solution when users play sequentially, but may cycle far away from the global optimum solution when users play concurrently. we introduce the notion of bounded best response where users react with best response subject to rules that are forced locally by the system. we investigate the problem of load balancing tasks on machines in a bipartite graph model and show that the dynamics of concurrent bounded best response converges to a near-optimum solution quickly, i.e., with poly-logarithmic number of rounds. this is in contrast to the concurrent best response dynamics which cycles far away from the optimum and to any sequential dynamics which requires at least a linear number of rounds to get to a reasonable solution.
online make-to-order joint replenishment model: primal dual competitive algorithms. in this paper, we study an online make-to-order variant of the classical joint replenishment problem (jrp) that has been studied extensively over the years and plays a fundamental role in broader planning issues, such as the management of supply chains. in contrast to the traditional approaches of the stochastic inventory theory, we study the problem using competitive analysis against a worst-case adversary. our main result is a 3-competitive deterministic algorithm for the online version of the jrp. we also prove a lower bound of approximately 2.64 on the competitiveness of any deterministic online algorithm for the problem. our algorithm is based on a novel primal-dual approach using a new linear programming relaxation of the offline jrp model. the primal-dual approach that we propose departs from previous primal-dual and online algorithms in rather significant ways. we believe that this approach can extend the range of problems to which online and primal-dual algorithms can be applied and analyzed.
a plant location guide for the unsure. this paper studies an extension of the k-median problem where we are given a metric space (v, d) and not just one but m client sets {si &sube; v}im=1, and the goal is to open k facilities f to minimize: maxi&isin;[m] {&sigma;j&isin;si d(j, f)}, i.e., the worst-case cost over all the client sets. this is a "min-max" or "robust" version of the k-median problem; however, note that in contrast to previous papers on robust/stochastic problems, we have only one stage of decision-making---where should we place the facilities? we present an o(log n + log m) approximation for robust k-median: the algorithm is combinatorial and very simple, and is based on reweighting/lagrangean-relaxation ideas. in fact, we give a general framework for (minimization) facility location problems where there is a bound on the number of open facilities. for robust and stochastic versions of such location problems, we show that if the problem satisfies a certain "projection" property, essentially the same algorithm gives a logarithmic approximation ratio in both versions. we use our framework to give the first approximation algorithms for robust/stochastic versions of k-tree, capacitated k-median, and fault-tolerant k-median.
broadcast scheduling: algorithms and complexity. broadcast scheduling is a popular method for disseminating information in response to client requests. there are n pages of information, and clients request pages at different times. however, multiple clients can have their requests satisfied by a single broadcast of the requested page. in this paper we consider several related broadcast scheduling problems. one central problem we study simply asks to minimize the maximum response time (over all requests). another related problem we consider is the version in which every request has a release time and a deadline, and the goal is to maximize the number of requests that meet their deadlines. while approximation algorithms for both these problems were proposed several years back, it was not known if they were np-complete. one of our main results is that both these problems are np-complete. in addition, we use the same unified approach to give a simple np-completeness proof for minimizing the sum of response times. a very complicated proof was known for this version. furthermore, we give a proof that fifo is a 2-competitive online algorithm for minimizing the maximum response time (this result had been claimed earlier with no proof) and that there is no better deterministic online algorithm (this result was claimed earlier as well, but with an incorrect proof).
the complexity of game dynamics: bgp oscillations, sink equilibria, and beyond. we settle the complexity of a well-known problem in networking by establishing that it is pspace-complete to tell whether a system of path preferences in the bgp protocol [25] can lead to oscillatory behavior; one key insight is that the bgp oscillation question is in fact one about nash dynamics. we also show that the concept of sink equilibria proposed recently in [11] is pspace-complete to analyze and approximate for graphical games. finally, we propose a new equilibrium concept inspired by game dynamics, unit recall equilibria, which we show to be close to universal (exists with high probability in a random game) and algorithmically promising. we also give a relaxation thereof, called componentwise unit recall equilibria, which we show to be both tractable and universal (guaranteed to exist in every game).
greedy drawings of triangulations. greedy routing is a class of routing algorithms in which the packets are forwarded in a manner that reduces the distance to the destination at every step. in an attempt to provide theoretical guarantees for a class of greedy routing algorithms, papadimitriou and ratajczak [19] came up with the following conjecture: any 3-connected planar graph can be drawn in the plane such that for every pair of vertices s and t a distance decreasing path can be found. a path s = v1, v2,&hellip;,vk=t in a drawing is said to be distance decreasing if ||vi - t|| < ||vi-1 -t||, 2 &le; i &le; k where || &hellip; || denotes the euclidean distance. we settle this conjecture in the affirmative for the case of triangulations. a partitioning of the edges of a triangulation g into 3 trees, called the realizer of g, was first developed by walter schnyder who also gave a drawing algorithm based on this. we generalize schnyder's algorithm to obtain a whole class of drawings of any given triangulation g. we show, using the knaster-kuratowski-mazurkiewicz theorem, that some drawing of g belonging to this class is greedy.
a deterministic sub-linear time sparse fourier algorithm via non-adaptive compressed sensing methods. we study the problem of estimating the best b term fourier representation for a given frequency-sparse signal (i.e., vector) a of length n &gt; b. more precisely, we investigate how to deterministically identify b of the largest magnitude frequencies of &acirc;, and estimate their coefficients, in polynomial (b, log n) time. randomized sub-linear time algorithms, which have a small (controllable) probability of failure for each processed signal, exist for solving this problem. however, for failure intolerant applications such as those involving mission-critical hardware designed to process many signals over a long lifetime, deterministic algorithms with no probability of failure are highly desirable. in this paper we build on the deterministic compressed sensing results of cormode and muthukrishnan (cm) [26, 6, 7] in order to develop the first known deterministic sub-linear time sparse fourier transform algorithm suitable for failure intolerant applications. furthermore, in the process of developing our new fourier algorithm, we present a simplified deterministic compressed sensing algorithm which improves on cm's algebraic compressibility results while simultaneously maintaining their results concerning exponential decay.
ultra-low-dimensional embeddings for doubling metrics. we consider the problem of embedding a metric into low-dimensional euclidean space. the classical theorems of bourgain and of johnson and lindenstrauss imply that any metric on n points embeds into an o(log n)-dimensional euclidean space with o(log n) distortion. moreover, a simple "volume" argument shows that this bound is nearly tight: the uniform metric on n points requires &omega;(log n/log log n) dimensions to embed with logarithmic distortion. it is natural to ask whether such a volume restriction is the only hurdle to low-dimensional low-distortion embeddings. do doubling metrics, which do not have large uniform submetrics, embed in low dimensional euclidean spaces with small distortion? in this paper, we answer the question positively and show that any doubling metric embeds into o(log log n) dimensions with o(log n) distortion. in fact, we give a suite of embeddings with a smooth trade-off between distortion and dimension: given an n-point metric (v,d) with doubling dimension dimd, and any target dimension t in the range &omega;(dimd log log n) &le; t &le; o(log n), we embed the metric into euclidean space ℝt with o(log n&radic;dimd/t) distortion.
on allocations that maximize fairness. we consider a problem known as the restricted assignment version of the max-min allocation problem with indivisible goods. there are n items of various nonnegative values and m players. every player is interested only in some of the items and has zero value for the other items. one has to distribute the items among the players in a way that maximizes a certain notion of fairness, namely, maximizes the minimum of the sum of values of items given to any player. bansal and sviridenko [stoc 2006] describe a linear programming relaxation for this problem, and present a rounding technique that recovers an allocation of value at least &omega;(log log log m/log log m) of the optimum. we show that the value of this lp relaxation in fact approximates the optimum value to within a constant factor. our proof is not constructive and does not by itself provide an efficient algorithm for finding an allocation that is within constant factors of optimal.
in-place 2-d nearest neighbor search. we revisit a classic problem in computational geometry: preprocessing a planar n-point set to answer nearest neighbor queries. in socg 2004, br&ouml;nnimann, chan, and chen showed that it is possible to design an efficient data structure that takes no extra space at all other than the input array holding a permutation of the points. the best query time known for such "in-place data structures" is o(log2 n). in this paper, we break the o(log2 n) barrier by providing a method that answers nearest neighbor queries in time {display equation} the new method uses divide-and-conquer (based on planar separators) in a way that is quite unlike traditional point location methods, and extends previous 1-d data structuring techniques (specifically the van emde boas layout). the method has further applications, for example, in answering extreme point queries for a 3-d point set on the boundary of a convex set of constant complexity.
fast edge splitting and edmonds' arborescence construction for unweighted graphs. given an unweighted undirected or directed graph with n vertices, m edges and edge connectivity c, we present a new deterministic algorithm for edge splitting. our algorithm splits-off any specified subset s of vertices satisfying standard conditions (even degree for the undirected case and in-degree &ge; out-degree for the directed case) while maintaining connectivity c for vertices outside s in &otilde;(m+nc2) time for an undirected graph and &otilde;(mc) time for a directed graph. this improves the current best deterministic time bounds due to gabow [8], who splits-off a single vertex in &otilde;(nc2+m) time for an undirected graph and &otilde;(mc) time for a directed graph. further, for appropriate ranges of n, c, |s| it improves the current best randomized bounds due to bencz&uacute;r and karger [2], who split-off a single vertex in an undirected graph in &otilde;(n2) monte carlo time. we give two applications of our edge splitting algorithms. our first application is a sub-quadratic (in n) algorithm to construct edmonds' arborescences. a classical result of edmonds [5] shows that an unweighted directed graph with c edge-disjoint paths from any particular vertex r to every other vertex has exactly c edge-disjoint arborescences rooted at r. for a c edge connected unweighted undirected graph, the same theorem holds on the digraph obtained by replacing each undirected edge by two directed edges, one in each direction. the current fastest construction of these arborescences by gabow [7] takes &otilde;(n2c2) time. our algorithm takes &otilde;(nc3+m) time for the undirected case and &otilde;(nc4+mc) time for the directed case. the second application of our splitting algorithm is a new steiner edge connectivity algorithm for undirected graphs which matches the best known bound of &otilde;(nc2 + m) time due to bhalgat et al [3]. finally, our algorithm can also be viewed as an alternative proof for existential edge splitting theorems due to lov&aacute;sz [9] and mader [11].
metric clustering via consistent labeling. we design approximation algorithms for a number of fundamental optimization problems in metric spaces, namely computing separating and padded decompositions, sparse covers, and metric triangulations. our work is the first to emphasize relative guarantees, that compare the produced solution to the optimal one for the input at hand. by contrast, the extensive previous work on these topics has sought absolute bounds that hold for every possible metric space (or for a family of metrics). while absolute bounds typically translate to relative ones, our algorithms provide significantly better relative guarantees, using a rather different algorithm. our technical approach is to cast a number of metric clustering problems that have been well studied---but almost always as disparate problems---into a common modeling and algorithmic framework, which we call the consistent labeling problem. having identified the common features of all of these problems, we provide a family of linear programming relaxations and simple randomized rounding procedures that achieve provably good approximation guarantees.
on stars and steiner stars. for a set of n points in the plane, a star connects one of the points (the center) to the other n - 1 points by straight line edges, while a steiner star connects an arbitrary point in the plane to all n input points. the center of the minimum steiner star, the weber center, minimizes the sum of distances from the n points. fekete and meijer showed that the minimum star is at most &radic;2 times longer than the minimum steiner star for any finite point configuration in the plane or 3-space. the maximum ratio between the two is conjectured to be 4/&pi; in the plane and 4/3 in three dimensions. here we improve the upper bound to 1.3999 in the plane, and to &radic;2 - 10-4 in 3-space. our results also imply improved bounds on the maximum ratios between the minimum star and the maximum matching in two and three dimensions. our method relies on constructing a suitable discretization for a continuous problem and then using linear programming to optimize over a relatively large set of constraints.
computing excluded minors. by robertson and seymour's graph minor theorem, every minor ideal can be characterised by a finite family of excluded minors. (a minor ideal is a class of graphs closed under taking minors.) we study algorithms for computing excluded minor characterisations of minor ideals. we propose a general method for obtaining such algorithms, which is based on definability in monadic second-order logic and the decidability of the monadic second-order theory of trees. a straightforward application of our method yields algorithms that, for a given k, compute excluded minor characterisations for the minor ideal tk of all graphs of tree width at most k, the minor ideal bk of all graphs of branch width at most k, and the minor ideal gk of all graphs of genus at most k. our main results are concerned with constructions of new minor ideals from given ones. answering a question that goes back to fellows and langston [11], we prove that there is an algorithm that, given excluded minor characterisations of two minor ideals c and d, computes such a characterisation for the ideal c &cup; d. furthermore, we obtain an algorithm for computing an excluded minor characterisation for the class of all apex graphs over a minor ideal c, given an excluded minor characterisation for c. (an apex graph over c is a graph g from which one vertex can be removed to obtain a graph in c.) a corollary of this result is a uniform ftpalgorithm for the "distance k from planarity" problem.