waashk/dblp huggingface dataset:
deterministic pivoting algorithms for constrained ranking and clustering problems. we introduce new problems of finding minimum-cost rankings and clusterings which must be consistent with certain constraints (e.g. an input partial order in the case of ranking problems); we give deterministic approximation algorithms for these problems. randomized approximation algorithms for unconstrained versions of these problems were given by ailon, charikar, and newman [2] and by ailon and charikar [1]. finding deterministic approximation algorithms for these problems answers an open question of ailon et al. [2]. in particular, we give deterministic algorithms for constrained weighted feedback arc set in tournaments, constrained correlation clustering, and constrained hierarchical clustering related to finding good ultrametrics. our algorithms follow the paradigm of ailon et al. [2] of choosing a particular vertex as a pivot and partitioning the graph according to the pivot; unlike their algorithms, we do not choose the pivot randomly but rather use an lp relaxation to choose a good pivot deterministically. additionally, the use of the lp relaxation allows us to impose constraints easily and analyze the results. in several cases we are able to find approximation factors for the constrained problems that improve on the factors they obtained for the unconstrained cases. we also give a combinatorial algorithm for constrained weighted feedback arc set in tournaments with weights satisfying probability constraints. this algorithm improves on the best known factor given by deterministic combinatorial algorithms for the unconstrained case.
stochastic analyses for online combinatorial optimization problems. in this paper, we study online algorithms when the input is not chosen adversarially, but consists of draws from some given probability distribution. while this model has been studied for online problems like paging and k-server, it is not known how to beat the &phi;(log n) bound for online steiner tree if at each time instant, the demand vertex is a uniformly random vertex from the graph. for the online steiner tree problem, we show that if each demand vertex is an independent draw from some probability distribution &pi;: v &rarr; [0, 1], a variant of the natural greedy algorithm achieves e&omega;[a(&omega;)]/e&omega;[opt (&omega;)] = o(1); moreover, this result can be extended to some other subadditive problems. both assumptions that the input sequence consists of independent draws from &pi;, and that &pi; is known to the algorithm are both essential; we show (almost) logarithmic lower bounds if either assumption is violated. moreover, we give preliminary results on extending the steiner tree results above to the related "expected ratio" measure e&omega;[&omega;(&omega;)/opt (&omega;)]. finally, we use these ideas to give an average-case analysis of the universal tsp problem.
analysis of greedy approximations with nonsubmodular potential functions. in this paper, we present two techniques to analyze greedy approximation with nonsubmodular functions restricted submodularity and shifted submodularity. as an application of the restricted submodularity, we present a worst-case analysis of a greedy algorithm for network steiner tree adapted from a heuristic originally proposed by chang in 1972 for euclidean steiner tree. the performance ratio of chang's heuristic is a longstanding open problem due to the nonsubmodularity of its potential function. as an application of the shifted submodularity, we present a worst-case analysis of a greedy algorithm for connected dominating set generalized from a greedy algorithm proposed by ruan et al. such generalized greedy algorithm is shown to have performance ratio at most (1 + &epsilon;)(1 + ln(&delta; - 1)), which matches the well-known lower bound (1-&epsilon;)ln &delta;, where &delta; is the maximum vertex-degree of input graph and &epsilon; is any positive constant.
set connectivity problems in undirected graphs and the directed steiner network problem. in the generalized connectivity problem, we are given an edge-weighted graph g = (v, e) and a collection d = {(s1,t1),&hellip;, (sk,tk)} of distinct demands; each demand (si, ti) is a pair of disjoint vertex subsets. we say that a subgraph f &sube; g connects a demand (si, ti) when it contains a path with one endpoint in si and the other in ti. the goal is to identify a minimum weight subgraph that connects all demands in d. alon et al. (soda '04) introduced this problem to study online network formation settings and showed that it captures some well-studied problems such as steiner forest, non-metric facility location, tree multicast, and group steiner tree. finding a non-trivial approximation ratio for generalized connectivity was left as an open problem. our starting point is the first polylogarithmic approximation for generalized connectivity attaining a performance guarantee of o(log2 n log2 k). here n is the number of vertices in g and k is the number of demands. we also prove that the cut-covering relaxation of this problem has an o(log3 n log2 k) integrality gap. building upon the results for generalized connectivity we obtain improved approximation algorithms for two problems that contain generalized connectivity as a special case. for the directed steiner network problem, we obtain an o(k1/2+&epsilon;) approximation, which improves on the currently best performance guarantee of o(k2/3) due to charikar et al. (soda '98). for the set connector problem, recently introduced by fukunaga and nagamochi (ipco '07), we present a polylogarithmic approximation; this result improves on the previously known ratio which can be &omega;(n) in the worst case.
improved algorithms for fully dynamic geometric spanners and geometric routing. for a set s of points in ℝd, a t-spanner is a sparse graph on the points of s such that between any pair of points there is a path in the spanner whose total length is at most t times the euclidean distance between the points. in this paper, we show how to construct a (1 + &epsilon;)-spanner with o(n/&epsilon;d) edges and maximum degree o(1/&epsilon;d) in time o(n log n). a spanner with similar properties was previously presented in [6, 8]. however, using our new construction (coupled with several other innovations) we obtain new results for two fundamental problems for constant doubling dimension metrics: the first result is an essentially optimal compact routing scheme. in particular, we show how to perform routing with a stretch of 1 + &isin;, where the label size is [log n] and the size of the table stored at each point is only o(log n/&epsilon;d). this routing problem was first considered by peleg and hassin [11], who presented a routing scheme in the plane. later, chan et al. [6] and abraham et al. [1] considered this problem for doubling dimension metric spaces. abraham et al. [1] were the first to present a (1 + &isin;) routing scheme where the label size depends solely on the number of points. in their scheme labels are of size of [log n], and each point stores a table of size o(log2 n/&epsilon;d). in our routing scheme, we achieve routing tables of size o(log n/&epsilon;d), which is essentially the same size as a label (up to the factor of 1/&epsilon;d). the second and main result of this paper is the first fully dynamic geometric spanner with poly-logarithmic update time for both insertions and deletions. we present an algorithm that allows points to be inserted into and deleted from s with an amortized update time of o(log3 n).
an efficient cost-sharing mechanism for the prize-collecting steiner forest problem. in an instance of the prize-collecting steiner forest problem (pcsf) we are given an undirected graph g = (v, e), non-negative edge-costs c(e) for all e &epsilon; e, terminal pairs r = {(si, ti)}1&le;i&le;k, and penalties &pi;1,...,&pi;k. a feasible solution (f, q) consists of a forest f and a subset q of terminal pairs such that for all (si, ti) &epsilon; r either si, ti are connected by f or (si, ti) &epsilon; q. the objective is to compute a feasible solution of minimum cost c(f) + &pi; (q). a game-theoretic version of the above problem has k players, one for each terminal-pair in r. player i's ultimate goal is to connect si and ti, and the player derives a privately held utility ui &ge; 0 from being connected. a service provider can connect the terminals si and ti of player i in two ways: (1) by buying the edges of an si, ti-path in g, or (2) by buying an alternate connection between si and ti (maybe from some other provider) at a cost of &pi;i. in this paper, we present a simple 3-budget-balanced and group-strategyproof mechanism for the above problem. we also show that our mechanism computes client sets whose social cost is at most o(log2 k) times the minimum social cost of any player set. this matches a lower-bound that was recently given by roughgarden and sundararajan (stoc '06).
finding an optimal tree searching strategy in linear time. we address the extension of the binary search technique from sorted arrays and totally ordered sets to trees and tree-like partially ordered sets. as in the sorted array case, the goal is to minimize the number of queries required to find a target element in the worst case. however, while the optimal strategy for searching an array is straightforward (always query the middle element), the optimal strategy for searching a tree is dependent on the tree's structure and is harder to compute. we present an o(n)-time algorithm that finds the optimal strategy for binary searching a tree, improving the previous best o(n3)-time algorithm. the significant improvement is due to a novel approach for computing subproblems, as well as a method for reusing parts of already computed subproblems, and a linear-time transformation from a solution in the form of an edge-weighed tree into a solution in the form of a decision tree.
on properties of random dissections and triangulations. in the past decades the gn,p model of random graphs, introduced by erd&odblac;s and r&eacute;nyi in the 60's, has led to numerous beautiful and deep theorems. a key feature that is used in basically all proofs is that edges in gn,p appear independently. the independence of the edges allows, for example, to obtain extremely tight bounds on the number of edges of gn,p and its degree sequence by straightforward applications of chernoff bounds. this situation changes dramatically if one considers graph classes with structural side constraints. for example, in a random planar graph rn (a graph drawn uniformly at random from the class of all labeled planar graphs on n vertices) the edges are obviously far from being independent. consequently, so far basically all results about properties of random graphs with structural side constraints rely on completely different methods, mostly from analytic combinatorics. in this paper we show that recent progress in the construction of so-called boltzmann samplers by duchon, flajolet, louchard, and schaeffer [3] and fusy [6] can be used to reduce the study of degree sequences and subgraph counts to properties of sequences of independent and identically distributed random variables -- to which we can then again apply chernoff bounds to obtain extremely tight results. we elaborate our ideas by studying random dissections and triangulations of a labeled convex n-gon. for both we obtain the degree sequence and the number of induced copies of given fixed graphs. the degree sequence for triangulations was already obtained previously by gao and wormald [8] using deep methods from analytic combinatorics. we do, however, get better bounds for the tails of the probability distribution.
comparing the strength of query types in property testing: the case of testing -colorability. we study the power of four query models in the context of property testing in general graphs, where our main case study is the problem of testing k-colorability. two query types, which have been studied extensively in the past, are pair queries and neighbor queries. the former corresponds to asking whether there is an edge between any particular pair of vertices, and the latter to asking for the i'th neighbor of a particular vertex. we show that while for pair queries, testing k-colorability requires a number of queries that is a monotone decreasing function in the average degree d, the query complexity in the case of neighbor queries remains roughly the same for every density and for large values of k. we also consider a combined model that allows both types of queries, and we propose a new, stronger, query model, which is related to the field of group testing. we give one-sided error upper and lower bounds for all the models, where the bounds are nearly tight for three of the models. in some of the cases our lower bounds extend to two-sided error algorithms. the problem of testing k-colorability was previously studied in the contexts of dense and sparse graphs, and in our proofs we unify approaches from those cases, and also provide some new tools and techniques which may be of independent interest.
the random graph threshold for -orientiability and a fast algorithm for optimal multiple-choice allocation. we investigate a linear time greedy algorithm for the following load balancing problem: assign m balls to n bins such that the maximum occupancy is minimized. each ball can be placed into one of two randomly choosen bins. this problem is closely related to the problem of orienting the edges of an undirected graph to obtain a directed graph with minimum in-degree. using differential equation methods, we derive thresholds for the solution quality achieved by our algorithm. since these thresholds coincide with lower bounds for the achievable solution quality, this proves the optimality of our algorithm (as n &rarr; &infin;, in a probabilistic sense) and establishes the thresholds for k-orientability of random graphs. this proves an assertion of karp and saks.
auctions for structured procurement. this paper considers a general setting for structured procurement and the problem a buyer faces in designing a procurement mechanism to maximize profit. this brings together two agendas in algorithmic mechanism design, frugality in procurement mechanisms (e.g., for paths and spanning trees) and profit maximization in auctions (e.g., for digital goods). in the standard approach to frugality in procurement, a buyer attempts to purchase a set of elements that satisfy a feasibility requirement as cheaply as possible. for profit maximization in auctions, a seller wishes to sell some number of goods for as much as possible. we unify these objectives by endowing the buyer with a decreasing marginal benefit per feasible set purchased and then considering the problem of designing a mechanism to buy a number of sets which maximize the buyer's profit, i.e., the difference between their benefit for the sets and the cost of procurement. for the case where the feasible sets are bases of a matroid, we follow the approach of reducing the mechanism design optimization problem to a mechanism design decision problem. we give a profit extraction mechanism that solves the decision problem for matroids and show that a reduction based on random sampling approximates the optimal profit. we also consider the problem of non-matroid procurement and show that in this setting the approach does not succeed.
tight lower bounds for selection in randomly ordered streams. we show that any algorithm computing the median of a stream presented in random order, using polylog(n) space, requires an optimal &omega; (log log n) passes, resolving an open question from the seminal paper on streaming by munro and paterson, from focs 1978.
linked decompositions of networks and the power of choice in polya urns. a linked decomposition of a graph with n nodes is a set of subgraphs covering the n nodes such that all pairs of subgraphs intersect; we seek linked decompositions such that all subgraphs have about &radic;n vertices, logarithmic diameter, and each vertex of the graph belongs to either one or two subgraphs. a linked decomposition enables many control and management functions to be implemented locally, such as resource sharing, maintenance of distributed directory structures, deadlock-free routing, failure recovery and load balancing, without requiring any node to maintain information about the state of the network outside the subgraphs to which it belongs. linked decompositions also enable efficient routing, schemes with small routing tables, which we describe in section 5. our main contribution is to show that "internet-like graphs" (e.g. the preferential attachment model proposed by barabasi et al. [10] and other similar models) have linked decompositions with the parameters described above with high probability; moreover, our experiments show that the internet topology itself can be so decomposed. our proof proceeds by analyzing a novel process, which we call polya urns with the power of choice, which may be of great independent interest. in this new process, we start with n nonempty bins containing o(n) balls total, and each arriving ball is placed in the least loaded of m bins, drawn independently at random with probability proportional to load. our analysis shows that in our new process, with high probability the bin loads become roughly balanced some time before o(n2+&epsilon;) further balls have arrived and stay roughly balanced, regardless of how the initial o(n) balls were distributed, where &epsilon; > 0 can be arbitrarily small, provided m is large enough.
sampling algorithms and coresets for &ell; regression. the &ell;p regression problem takes as input a matrix a &isin; ℝn, a vector b &isin; ℝn, and a number p &isin; [1, &infin;), and it returns as output a number z and a vector xopt &isin; ℝd such that z = minx&isin;ℝd ||ax - b||p = ||axopt - b||p. in this paper, we construct coresets and obtain an efficient two-stage sampling-based approximation algorithm for the very overconstrained (n &gt; d) version of this classical problem, for all p &isin; [1, &infin;). the first stage of our algorithm non-uniformly samples &rcirc;1 = o(36pdmax{p/2+1, p}+1) rows of a and the corresponding elements of b, and then it solves the lp regression problem on the sample; we prove this is an 8-approximation. the second stage of our algorithm uses the output of the first stage to resample &rcirc;1/&epsilon;2 constraints, and then it solves the lp regression problem on the new sample; we prove this is a (1 + &epsilon;)-approximation. our algorithm unifies, improves upon, and extends the existing algorithms for special cases of &ell;p regression, namely p = 1,2 [10, 13]. in course of proving our result, we develop two concepts--well-conditioned bases and subspace-preserving sampling--that are of independent interest.
maximum overhang. how far can a stack of n identical blocks be made to hang over the edge of a table? the question dates back to at least the middle of the 19th century and the answer to it was widely believed to be of order log n. however, at soda'06, paterson and zwick constructed n-block stacks with overhangs of order n1/3. here we complete the solution to the overhang problem, and answer paterson and zwick's primary open question, by showing that order n1/3 is best possible. at the heart of the argument is a lemma (possibily of independent interest) showing that order d3 non-adaptive coinflips are needed to propel a discrete random walk on the number line to distance d. we note that our result is not a mainstream algorithmic result, yet it is about the solution to a discrete optimization problem. moreover, it illusrates how methods founded in theoretical computer science can be aplied to a problem that has puzzled some mathematicians and physicists for more than 150 years.
on distance to monotonicity and longest increasing subsequence of a data stream. in this paper we consider problems related to the sortedness of a data stream. first we investigate the problem of estimating the distance to monotonicity; given a sequence of length n, we give a deterministic (2 + &epsilon;)-approximation algorithm for estimating its distance to monotonicity in space o(1/&epsilon;2 log2 (&epsilon;n)). this improves over the randomized (4 + &epsilon;)-approximation, algorithm of [3]. we then consider the problem of approximating the length of the longest increasing subsequence of an input stream of length n. we use techniques from multi-party communication complexity combined with a fooling set approach to prove that any o(1)-pass deterministic streaming algorithm that approximates the length of the longest increasing subsequence within 1 + &epsilon; requires &omega;(&radic;n) space. this proves the conjecture in [3] and matches the current upper bound.
distribution-sensitive point location in convex subdivisions. a data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. the data structure has an expected query time that differs from the optimal one by only lower order terms in the linear comparison tree model.
embedding metric spaces in their intrinsic dimension. a fundamental question of metric embedding is whether the metric dimension of a metric space is related to its intrinsic dimension. that is whether the dimension in which it can be embedded in some real normed space is implied by the intrinsic dimension which is reflected by the inherent geometry of the space. the existence of such an embedding was conjectured by assouad and was later posed as an open problem by others. this question is tightly related to a major goal of many practical application fields: developing tools to represent intrinsically low dimensional metric data sets in a succinct manner. in this paper we give the first algorithmic technique with formal guarantees for finding faithful and low dimensional representations of data lying in high dimensional space. our main theorem states that every finite metric space x embeds into euclidean space with dimension o(dim(x)/&isin;) and distortion o(log 1+&epsilon;n), where dim(x) is the doubling dimension of the space x. moreover, we show that x can be embedded into dimension &otilde;(dim(x)) with constant average distortion and lq-distortion for any q < &infin;. our technique also provides a dimension-distortion tradeoff and an extension of assouad's theorem, providing distance oracles that improve known construction when dim(x) = o(log |x|).
efficient subspace approximation algorithms. confronted with high-dimensional data arising from either word-document count, global climate patterns or any one of the myriad other sources, most scientific approaches extract a good low-dimensional summary. this desire to reduce dimensionality may be seen as a consequence of occam's razor, and the scientific methodologies we have in mind include those from data mining and statistics.