waashk/dblp huggingface dataset:
approximation algorithms for wavelet transform coding of data streams. given a set of orthonormal basis functions {&psi;i} and a target function/vector f, the wavelet representation problem is to construct f as a combination of at most b basis vectors to minimize some normed distance between f and f. the problem is well understood if the error is the mean squared error: the largest (ignoring signs) b coefficients of the wavelet expansion should be retained. this strategy follows from the proof of optimality and is not a built-in constraint.the mean squared error, however, is not the optimization criterion in several scenarios. the above easy solution to the wavelet representation problem does not carry over to lp for p &ne; 2, and it turns out that restricting the solution to any subset of coefficients of size b or less is suboptimal compared to the best solution which can choose arbitrary real numbers. further, all the previous literature on non-l2 errors only considered the haar system.in this paper we provide the first approximation schemes for the unrestricted optimization problem. we provide a lower bounding technique based on a system of inequalities. we show that a modified greedy algorithm that retains the coefficients of expansion gives a o(log n) true (factor) approximation algorithm for a wide variety of compact wavelet systems, including haar, daubechies, symmlets, coiflets among others. this vindicates several scaling type algorithms which are used in practice. we subsequently augment the lower bound and give a fptas for the haar system. the same ideas extend to a qptas for the more general class of compact wavelets mentioned above. we also consider adaptive quantization problems, which are generalizations of the b-term representations.
capacitated vertex covering with applications. in this paper we study the capacitated vertex cover problem, a generalization of the well known vertex cover problem. given a graph g = (v, e) with weights on the vertices, the goal is to cover all the edges by picking a cover of minimum weight from the vertices. when we pick a copy of a vertex, we pay the weight of the vertex and cover upto a pre-specified number of edges incident on this vertex (its capacity). the problem is np-hard. we give a primal-dual based 2 approximation and study several generalizations, as well as the problem restricted to trees.
improved algorithms for the data placement problem. we study the data placement problem [1, 3], where the goal is to place certain data objects (with possible replication) in fixed capacity caches in a network to optimize latency of access. the locations of the caches are given and each cache has capacities both on the number of objects it can store and the number of users it can serve. each user has a demand for a specific object.the end objective is to optimize the average user latency of accessing the objects. we present a constant approximation, while blowing up the cache capacities by a constant factor. this improves the previous results, which either ignore the bound on the number of users [1], or which need to blow up the capacities by a logarithmic factor [3]. our solution technique involves writing an integer program for this problem and rounding its linear relaxation.we note that our result is the best possible that can be obtained by lp rounding. the problem is max-snp hard as shown in [1], and the linear program has unbounded integrality gap unless we relax the capacity constraints [5].our basic technique is to separate the rounding into two stages:opening objects: in this stage, we consider each object separately, and open copies in the network. we ignore the interaction of this object with other objects due to the cache capacity constraints. we use the capacitated facility location rounding from [5].packing objects: in this stage, we pack the objects into the cache so that cache capacity constraints are satisfied. we use the gap rounding from [4].
improved algorithms for fault tolerant facility location. we consider a generalization of the classical facility location problem, where we require the solution to be fault-tolerant. every demand point j is served by rj facilities instead of just one. the facilities other than the closest one are &ldquo;backup&rdquo; facilities for that demand, and will be used only if the closer facility (or the link to it) fails. hence, for any demand, we assign non-increasing weights to the routing costs to farther facilities. the cost of assignment for demand j is the weighted linear combination of the assignment costs to its rj closest open facilities. we wish to minimize the sum of the cost of opening the facilities and the assignment cost of each demand j. we obtain a factor 4 approximation to this problem through the application of various rounding techniques to the linear relaxation of an integer program formulation. we further improve this result to 3.16 using randomization and to 2.47 using greedy local-search type techniques.
streaming and sublinear approximation of entropy and information distances. in most algorithmic applications which compare two distributions, information theoretic distances are more natural than standard lp norms. in this paper we design streaming and sublinear time property testing algorithms for entropy and various information theoretic distances.batu et al posed the problem of property testing with respect to the jensen-shannon distance. we present optimal algorithms for estimating bounded, symmetric f-divergences (including the jensen-shannon divergence and the hellinger distance) between distributions in various property testing frameworks. along the way, we close a (log n)/h gap between the upper and lower bounds for estimating entropy h, yielding an optimal algorithm over all values of the entropy. in a data stream setting (sublinear space), we give the first algorithm for estimating the entropy of a distribution. our algorithm runs in polylogarithmic space and yields an asymptotic constant factor approximation scheme. an integral part of the algorithm is an interesting use of an f0 (the number of distinct elements in a set) estimation algorithm; we also provide other results along the space/time/approximation tradeoff curve.our results have interesting structural implications that connect sublinear time and space constrained algorithms. the mediating model is the random order streaming model, which assumes the input is a random permutation of a multiset and was first considered by munro and paterson in 1980. we show that any property testing algorithm in the combined oracle model for calculating a permutation invariant functions can be simulated in the random order model in a single pass. this addresses a question raised by feigenbaum et al regarding the relationship between property testing and stream algorithms. further, we give a polylog-space ptas for estimating the entropy of a one pass random order stream. this bound cannot be achieved in the combined oracle (generalized property testing) model.
the robot localization problem in two dimensions. we consider the following problem: given a simple polygon p and a star-shaped polygon v, find a point (or the set of points) in p from which the portion of p that is visible is congruent to v. the problem arises in the localization of robots using a range-finder&mdash;p is a map of a known environment, v is the portion visible from the robot's position, and the robot must use this information to determine its position in the map. we give a scheme that preprocesses p so that any subsequent query v is answered in optimal time o(m + log n + a), where m and n are the number of vertices in v and p, and a is the number of points in p that are valid answers (the output size). our technique allows us to trade off smoothly between the query time and the preprocessing time or space. we also devise a data structure for output-sensitive determination of the visibility polygon of a query point inside a polygon p. we then consider a variant of the localization problem in which there is a maximum distance to which the robot can &ldquo;see&rdquo;&mdash;this is motivated by practical considerations, and we outline a similar solution for this case. we also show that a single localization query v can be answered in time o(mn) with no preprocessing.
zonotopes as bounding volumes. zonotopes are centrally symmetric polytopes with a very special structure: they are minkowski sums of line segments. in this paper we propose to use zonotopes as bounding volumes for geometry in collision detection and other applications where the spatial relationship between two pieces of geometry is important. we show how to construct optimal, or approximately optimal zonotopes enclosing given set of points or other geometry. we also show how zonotopes can be used for efficient collision testing, based on their representation via their defining line segments --- without ever building their explicit description as polytopes. this implicit representation adds flexibility, power, and economy to the use of zonotopes as bounding volumes.
optimizing markov models with applications to triangular connectivity coding. in this work markov models are constructed to describe the asymptotic stochastical behavior of regular languages, what allows for optimal arithmetic coding of words from the language. a new method is presented for the optimization of markov models such that also constraints are captured that cannot be described within a regular language. the new technique is applied to the encoding of the connectivity graph of triangle meshes of low genus and boundary fraction. the resulting compression rates are up to one percent optimal and the best known upper bound for this class of models.
steiner points in tree metrics don't (really) help. consider an edge-weighted tree t = (v, e, w : e &rarrtl; r+), in which a subset r of the nodes (called the required nodes) are colored red and the remaining nodes in s = v\r are colored black (and called the steiner nodes). the shortest-path distance according to the edge-weights defines a metric dt on the vertex set v. we now ask the following question: is it possible to define another weighted tree t* = (r, e*, w* : e* &rarrtl; r+), this time on just the red vertices so that the shortest-path metric dt* induced by t* on the vertices in r is &ldquo;close&rdquo; to the metric dt restricted to the red vertices? i.e., does there exist a weighted tree t* = (r, e*, c*) and a (small) constant &agr; such that dt(u, v) &le; dt* (u, v) &le; &agr; dt(u, v) for any two red vertices u, v &isin; r? we answer this question in the affirmative, and give a linear time algorithm to obtain a tree t* with &agr; &le; 8. we also give two applications of this result: an upper bound, in which we show that emulating multicasts using unicasts can be almost as good as general multicasts for certain performance measures; and a lower bound, in which we give a simple combinatorial proof of the fact that the metric generated by a graph of girthg must suffer a distortion of at least &ohgr;(g) when approximated by a tree.
improved results for directed multicut. we give a simple algorithm for the minimum directed multicut problem, and show that it gives an o(&radic;n)-approximation. this improves on the previous approximation guarantee of o(&radic;n log k) of cheriyan, karloff and rabani [1], which was obtained by a more sophisticated algorithm.
oblivious network design. consider the following network design problem: given a network g = (v, e), source-sink pairs {si, ti} arrive and desire to send a unit of flow between themselves. the cost of the routing is this: if edge e carries a total of fe flow (from all the terminal pairs), the cost is given by &sigma; el(fe), where l is some concave cost function; the goal is to minimize the total cost incurred. however, we want the routing to be oblivious: when terminal pair {si, ti} makes its routing decisions, it does not know the current flow on the edges of the network, nor the identity of the other pairs in the system. moreover, it does not even know the identity of the function l, merely knowing that l is a concave function of the total flow on the edge. how should it (obliviously) route its one unit of flow? can we get competitive algorithms for this problem?in this paper, we develop a framework to model oblivious network design problems (of which the above problem is a special case), and give algorithms with poly-logarithmic competitive ratio for problems in this framework (and hence for this problem). abstractly, given a problem like the one above, the solution is a multicommodity flow producing a "load" on each edge of le = l(f1(e),f2(e), ..., fk(e)), and the total cost is given by an "aggregation function" agg (le1,...,lem) of the loads of all edges. our goal is to develop oblivious algorithms that approximately minimize the total cost of the routing, knowing the aggregation function agg, but merely knowing that l lies in some class c, and having no other information about the current state of the network. hence we want algorithms that are simultaneously "function-oblivious" as well as "traffic-oblivious".the aggregation functions we consider are the max and &sigma; objective functions, which correspond to the well-known measures of congestion and total cost of a network; in this paper, we prove the following:&bull; if the aggregation function is &sigma;, we give an oblivious algorithm with o(log2 n) competitive ratio whenever the load function l is in the class of monotone sub-additive functions. (recall that our algorithm is also "function-oblivious"; it works whenever each edge has a load function l in the class.)&bull; for the case when the aggregation function is max, we give an oblivious algorithm with o(log2 n log log n) competitive ratio, when the load function l is a norm; we also show that such a competitive ratio is not possible for general sub-additive functions.these are the first such general results about oblivious algorithms for network design problems, and we hope the ideas and techniques will lead to more and improved results in this area.
approximating unique games. the unique games problem is the following: we are given a graph g = (v, e), with each edge e = (u, v) having a weight we and a permutation &pi;uv on [k]. the objective is to find a labeling of each vertex u with a label fu &isin; [k] to minimize the weight of unsatisfied edges---where an edge (u, v) is satisfied if fv = &pi;uv(fu).the unique games conjecture of khot [8] essentially says that for each &epsilon; > 0, there is a k such that it is np-hard to distinguish instances of unique games with (1-&epsilon;) satisfiable edges from those with only &epsilon; satisfiable edges. several hardness results have recently been proved based on this assumption, including optimal ones for max-cut, vertex-cover and other problems, making it an important challenge to prove or refute the conjecture.in this paper, we give an o(log n)-approximation algorithm for the problem of minimizing the number of unsatisfied edges in any unique game. previous results of khot [8] and trevisan [12] imply that if the optimal solution has opt = &epsilon;m unsatisfied edges, semidefinite relaxations of the problem could give labelings with min {k2&epsilon;1/5, (&epsilon; log n)1/2}m unsatisfied edges. in this paper we show how to round a lp relaxation to get an o(log n)-approximation to the problem; i.e., to find a labeling with only o(&epsilon;m log n) = o(opt log n) unsatisfied edges.
counting inversions in lists. in a recent paper, ajtai et al. [1] give a streaming algorithm to count the number of inversions in a stream l&epsilon;[m]n using two passes and o(&epsilon;&minus;1-&radic;n log n(log m + log n)) space. here, we present a simple randomized streaming algorithm for the same problem that uses one pass and o(&epsilon;&minus;3 log2 n log m) space. our algorithm is based on estimating quantiles of the items already seen in the stream, and using that to estimate the number of inversions involving each element.
on profit-maximizing envy-free pricing. we study the problem of pricing items for sale to consumers so as to maximize the seller's revenue. we assume that for each consumer, we know the maximum amount he would be willing to pay for each bundle of items, and want to find pricings of the items with corresponding allocations that maximize seller profit and at the same time are envy-free, which is a natural fairness criterion requiring that consumers are maximally happy with the outcome they receive given the pricing. we study this problem for two important classes of inputs: unit demand consumers, who want to buy at most one item from among a selection they are interested in, and single-minded consumers, who want to buy one particular subset, but only if they can afford it.we show that computing envy-free prices to maximize the seller's revenue is apx-hard in both of these cases, and give a logarithmic approximation algorithm for them. for several interesting special cases, we derive polynomial-time algorithms. furthermore, we investigate some connections with the corresponding mechanism design problem, in which the consumer's preferences are private values: for this case, we give a log-competitive truthful mechanism.
efficiently decodable codes meeting gilbert-varshamov bound for low rates. we demonstrate a probabilistic construction of binary linear codes meeting the gv bound (with overwhelming probability) for rates up to about 10-4 together with polynomial time algorithms to perform encoding and decoding up to half the distance. the only previous result of this type (for rates up to about 0.02) suffered from sub-exponential time decoding [3].
maximum-likelihood decoding of reed-solomon codes is np-hard. maximum-likelihood decoding is one of the central problems in coding theory. it has been known for over 25 years that maximum-likelihood decoding of general linear codes is np-hard. nevertheless, it was so far unknown whether maximum-likelihood decoding remains hard for any specific family of codes with nontrivial algebraic structure. in this paper, we prove that maximum-likelihood decoding is np-hard for the family of reed-solomon codes. we moreover show that maximum-likelihood decoding of reed-solomon codes remains hard even with unlimited preprocessing, thereby strengthening a result of bruck and naor.
parametric optimization of sequence alignment. the optimal alignment or the weighted minimum edit distance between two dna or amino acid sequences for a given set of weights is computed by classical dynamic programming techniques, and is widely used in molecular biology. however, in dna and amino acid sequences there is considerable disagreement about how to weight matches, mismatches, insertions/deletions (indels) and gaps. parametric sequence alignment is the problem of computing the optimal valued alignment between two sequences as a function of variable weights for matches, mismatches, spaces and gaps. the goal is to partition the parameter space into regions (which are necessarily convex) such that in each region one alignment is optimal throughout and such that the regions are maximal for this property. in this paper we are primarily concerned with the structure of this convex decomposition, and secondarily with the complexity of computing the decomposition. the most striking results are the following: for the special case where only matches, mismatches and spaces are counted, and where spaces are counted throughout the alignment, we show that the decomposition is surprisingly simple: all regions are infinite; there are at most n2/3 regions; the lines that bound the regions are all of the form &bgr; = c+(c + 0.5)&agr;; and the entire decomposition can be found in o(knm) time, where k is the actual number of regions and n < m are the lengths of the two strings. these results were found while implementing a large software package to do parametric sequence analysis, and in turn have led to faster algorithms for those tasks.
inserting an edge into a planar graph. computing a crossing minimum drawing of a given planar graph g augmented by an additional edge e in which all crossings involve e, has been a long standing open problem in graph drawing. alternatively, the problem can be stated as finding a planar combinatorial embedding of a planar graph g in which the given edge e can be inserted with the minimum number of crossings. many problems concerned with the optimization over the set of all combinatorial embeddings of a planar graph turned out to be np-hard. surprisingly, we found a conceptually simple linear time algorithm based on spqr trees, which is able to find a crossing minimum solution.
the prize-collecting generalized steiner tree problem via a new approach of primal-dual schema. in this paper we study the prize-collecting version of the generalized steiner tree problem. to the best of our knowledge, there is no general combinatorial technique in approximation algorithms developed to study the prize-collecting versions of various problems. these problems are studied on a case by case basis by bienstock et al. [5] by applying an lp-rounding technique which is not a combinatorial approach. the main contribution of this paper is to introduce a general combinatorial approach towards solving these problems through novel primal-dual schema (without any need to solve an lp). we fuse the primal-dual schema with farkas lemma to obtain a combinatorial 3-approximation algorithm for the prize-collecting generalized steiner tree problem. our work also inspires a combinatorial algorithm [19] for solving a special case of kelly's problem [22] of pricing edges.we also consider the k-forest problem, a generalization of k-mst and k-steiner tree, and we show that in spite of these problems for which there are constant factor approximation algorithms, the k-forest problem is much harder to approximate. in particular, obtaining an approximation factor better than o(n1/6-&epsilon;) for k-forest requires substantially new ideas including improving the approximation factor o(n1/3-&epsilon;) for the notorious densest k-subgraph problem. we note that k-forest and prize-collecting version of generalized steiner tree are closely related to each other, since the latter is the lagrangian relaxation of the former.
improved lower and upper bounds for universal tsp in planar metrics. a universal tsp tour of a metric space is a total ordering of the points of the space such that for any finite subset, the tour which visits these points in the given order is not too much longer than the optimal tour. there is a vast literature on the tsp problem, and universal tsp tours have been studied since the 1980's when bartholdi and platzman [29] introduced the spacefilling curve heuristic for the euclidean tsp problem and conjectured that there exists a constant-competitive universal tsp tour based on this heuristic. here, we settle this conjecture negatively by proving an &omega; (6&radic;log n/log log n) lower bound for universal tsp tours of the n &times; n grid; this is the first known example of a family of finite metrics with no constant-competitive universal tour.generalizing from the n &times; n grid to arbitrary weighted planar graph metrics, and more generally h-minor-free metrics, we improve the best known upper bound for universal tours of such metrics from o(log4 n/ log log n) to o(log2 n).