waashk/dblp huggingface dataset:
oblivious routing on node-capacitated and directed graphs. oblivious routing algorithms for general undirected networks were introduced by r&auml;cke [17], and this work has led to many subsequent improvements and applications. comparatively little is known about oblivious routing in general directed networks, or even in undirected networks with node capacities.we present the first non-trivial upper bounds for both these cases, providing algorithms for k-commodity oblivious routing problems with competitive ratio o(&radic;klog(n)) for undirected node-capacitated graphs and o(&radic;kn1/4log(n)) for directed graphs. in the special case that all commodities have a common source or sink, our upper bound becomes o(&radic;nlog(n)) in both cases, matching the lower bound up to a factor of log(n). the lower bound (which first appeared in [6]) is obtained on a graph with very high degree. we show that in fact the degree of a graph is a crucial parameter for node-capacitated oblivious routing in undirected graphs, by providing an o( polylog(n))competitive oblivious routing scheme for graphs of degree. for the directed case, however, we show that the lower bound of &omega;(&radic;n) still holds in low-degree graphs.finally, we settle an open question about routing problems in which all commodities share a common source or sink. we show that even in this simplified scenario there are networks in which no oblivious routing algorithm can achieve a competitive ratio better than &omega;(log n).
new lower bounds for oblivious routing in undirected graphs. oblivious routing algorithms for general undirected networks were introduced by r&auml;cke, and this work has led to many subsequent improvements and applications. r&auml;cke showed that there is an oblivious routing algorithm with polylogarithmic competitive ratio (with respect to edge congestion) for any undirected graph. however, there are directed networks for which the competitive ratio is in &omega;(&radic;n).to cope with this inherent hardness in general directed networks, the concept of oblivious routing with demands chosen randomly from a known demand distribution was introduced recently. under this new model, o(log2 n)-competitiveness with high probability is possible in general directed graphs.however, it remained an open problem whether or not the competitive ratio, under this new model, could also be significantly improved in undirected graphs. in this paper, we rule out this possibility by providing a lower bound of &omega;(log n/log log n) for the multicommodity case and &omega;(&radic;logn) for the single-sink case for oblivious routing in a random demand model.we also introduce a natural candidate model for evaluating the throughput of an oblivious routing scheme which subsumes all suggested models for the throughput of oblivious routing considered so far. in this general model, we first prove a lower bound &omega;(log n/log log n) for the competitive ratio of any oblivious routing scheme. interestingly, the graphs that we consider for the lower bound in this case are expanders, for which we also obtain a lower bound &omega;(log n/log log n) on the competitive ratio of congestion based oblivious routing with adversarial demands.
finding large sticks and potatoes in polygons. we study a class of optimization problems in polygons that seek to compute the "largest" subset of a prescribed type, e.g., a longest line segment ("stick") or a maximum-area triangle or convex body ("potato"). exact polynomial-time algorithms are known for some of these problems, but their time bounds are high (e.g., o(n7) for the largest convex polygon in a simple n-gon). we devise efficient approximation algorithms for these problems. in particular, we give near-linear time algorithms for a (1 - &isin;)-approximation of the biggest stick, an o(1)-approximation of the maximum-area convex body, and a (1 - &isin;)-approximation of the maximum-area fat triangle or rectangle. in addition, we give efficient methods for computing large ellipses inside a polygon (whose vertices are a dense sampling of a closed smooth curve). our algorithms include both deterministic and randomized methods, one of which has been implemented (for computing large area ellipses in a well sampled closed smooth curve).
on algorithms for efficient data migration. the data migration problem is the problem of computing an efficient plan for moving data stored on devices in a network from one configuration to another. load balancing or changing usage patterns could necessitate such a rearrangement of data. in this paper, we consider the case where the objects are fixed-size and the network is complete. the direct migration problem is closely related to edge-coloring. however, because there are space constraints on the devices, the problem is more complex. our main results are polynomial time algorithms for finding a near-optimal migration plan in the presence of space constraints when a certain number of additional nodes is available as temporary storage, and a 3/2-approximation for the case where data must be migrated directly to its destination.
finding subsets maximizing minimum structures. we consider the problem of finding a set of k vertices in a graph that are in some sense remote. stated more formally, given a graph g and an integer k, find a set p of k vertices for which the total weight of a minimum structure on p is maximized. in particular, we are interested in three problems of this type, where the structure to be minimized is a spanning tree ({\sc remote-mst}), steiner tree, or traveling salesperson tour.we study a natural greedy algorithm that simultaneously approximates all three problems on metric graphs. for instance, its performance ratio for {\sc remote-mst} is exactly 4, while this problem is np-hard to approximate within a factor of less than 2. we also give a better approximation for graphs induced by euclidean points in the plane, present an exact algorithm for graphs whose distances correspond to shortest-path distances in a tree, and prove hardness and approximability results for general graphs.
lower bounds for on-line graph coloring. an algorithm for vertex-coloring graphs is said to be online if each vertex is irrevocably assigned a color before any later vertices are considered. we show that such algorithms are inherently ineffective. the performance ratio of any such algorithm can be no better than &ohgr;(n/log2 n), even for randomized algorithms against oblivious adversary. we also show that various means of relaxing the constraints of the on-line model do not reduce these lower bounds. the features include presenting the input in blocks of log2 n vertices, recoloring any fraction of the vertices, presorting vertices according to degree, and disclosing the adversary's previous coloring.
improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. we obtain improved algorithms for finding small vertex covers in bounded degree graphs and hypergraphs. we use semidefinite programming to relax the problems and introduce new} rounding techniques for these relaxations. on graphs with maximum degree at most $\delta$, the algorithm achieves a performance ratio of $2-(1-o(1))\frac{2 \ln \ln \delta}{\ln \delta}$ for large $\delta$, which improves the previously known ratio of $2-\frac{\log \delta + o(1)}{\delta}$ obtained by halld{órsson and radhakrishnan. using similar techniques, we also present improved approximations for the vertex cover problem in hypergraphs. for k-uniform hypergraphs with n vertices, we achieve a ratio of $k-(1-o(1))\frac{k\ln \ln n}{\ln n}$ for large n, and for k-uniform hypergraphs with maximum degree at most $\delta$ the algorithm achieves a ratio of $k-(1-o(1))\frac{k(k-1)\ln \ln \delta}{\ln \delta}$ for large $\delta$. these results considerably improve the previous best ratio of $k(1-c/\delta^\frac{1}{k-1})$ for bounded degree k-uniform hypergraphs, and $k(1-c/n^\frac{k-1}{k})$ for general k-uniform hypergraphs, both obtained by krivelevich. using similar techniques, we also obtain an approximation algorithm for the weighted independent set problem, matching a recent result of halldorsson.
integrality ratio for group steiner trees and directed steiner trees. we present an &omega;(log2k) lower bound on the integrality ratio of the flow-based relaxation for the group steiner tree problem, where k denotes the number of groups; this holds even for input graphs that are hierarchically well-separated trees, introduced by bartal [symp. foundations of computer science, pp. 184--193, 1996], in which case this lower bound is tight. this relaxation appears to be the only one that have been studied for the problem, as well as for its generalization, the directed steiner tree problem. for the latter problem, our results imply an &omega;(log2n/(log logn)2) integrality ratio, where n is the number of vertices in the graph. for both problems, this is the first known lower bound on the integrality ratio that is superlogarithmic in the input size. we also show algorithmically that the integrality ratio for group steiner tree is much better for certain families of instances, which helps pinpoint the types of instances that appear to be most difficult to approximate.
max cut in cubic graphs. we present an improved semidefinite programming based approximation algorithm for the max cut problem in graphs of maximum degree at most 3. the approximation ratio of the new algorithm is at least 0.9326. this improves, and also somewhat simplifies, a result of feige, karpinski and langberg. we also observe that results of hopkins and staton and of bondy and locke yield a simple combinatorial 4/5-approximation algorithm for the problem. finally, we present a combinatorial 22/27-approximation algorithm for the max cut problem for regular cubic graphs.
coloring k-colorable graphs using smaller palettes. we obtain the following new coloring results: a 3-colorable graph on n vertices with maximum degree &dgr; can be colored, in polynomial time, using &ogr;((&dgr; log &dgr;)1/3 &middot;log n) colors. this slightly improves an &ogr;((&dgr;1/3 log&frac12; &dgr;) &middot; log n) bound given by karger, motwani and sudan. more generally, k-colorable graphs with maximum degree &dgr; can be colored, in polynomial time, using &ogr;((&dgr;1-2/k log1/k &dgr;) &middot; log n) colors. a 4-colorable graph on n vertices can be colored, in polynomial time, using &ogr;(n7/19) colors. this improves an &ogr;(n2/5) bound given again by karger, motwani and sudan. more generally, k-colorable graphs on n-vertices can be colored, in polynomial time, using &ogr;(n&agr;k) colors, where &agr;5 = 97/207, &agr;6 = 43/79, &agr;7 = 1391/2315, &agr;8 = 175/271, &hellip; the first result is obtained by a slightly more refined probabilistic analysis of the semidefinite programming based coloring algorithm of karger, motwani and sudan. the second result is obtained by combining the coloring algorithm of karger, motwani and sudan, the combinatorial coloring algorithms of blum and an extension of a technique of alon and kahale (which is based on the karger, motwani and sudan algorithm) for finding relatively large independent sets in graphs that are guaranteed to have very large independent sets. the extension of the alon and kahale result may be of independent interest.
combinatorial approximation algorithms for the maximum directed cut problem. we describe several combinatorial algorithms for the maximum directed cut problem. among our results is a simple linear time 9/20-approximation algorithm for the problem, and a somewhat slower &frac12;-approximation algorithm that uses a bipartite matching routine. no better combinatorial approximation algorithms are known even for the easier maximum cut problem for undirected graphs. our algorithms do not use linear programming, nor semidefinite programming. they are based on the observation that the maximum directed cut problem is equivalent to the problem of finding a maximum independent set in the line graph of the input graph, and that the linear programming relaxation of the problem is equivalent to the problem of finding a maximum fractional independent set of that line graph. the maximum fractional independent set problem can be easily reduced to a bipartite matching problem. as a consequence of this relation, we also get that the maximum directed cut problem for bipartite digraphs can be solved in polynomial time.
computing minimal spanning subgraphs in linear time. let p be a property of undirected graphs. we consider the following problem: given a graph g that has property p, find a minimal spanning subgraph of g with property p. we describe two related algorithms for this problem and prove their correctness under some rather weak assumptions about p. we devise a general technique for analyzing the worst-case behavior of these algorithms. by applying the technique to 2-edge-connectivity and biconnectivity, we obtain an &ohgr;(m + n log n) lower bound on the worst-case running time of the algorithms for these two properties, thus settling open questions posed earlier with regard to these properties. we then describe refinements of the basic algorithms that yield the first linear-time algorithms for finding a minimal 2-edge-connected spanning subgraph and a minimal biconnected spanning subgraph of a graph.
parallel integer sorting is more efficient than parallel comparison sorting on exclusive write prams. we present a significant improvement for parallel integer sorting. on the erew (exclusive read exclusive write) pram our algorithm sorts n integers in the range {0,1, . . . ,m-1 } in time o(log n) with $o(n \sqrt{\frac{\log n}{k}})$ operations using word length $k \log (m+n)$, where $1 \leq k \leq \log n$. in this paper we present the following four variants of our algorithm.\noindent (1) the first variant sorts integers in $\{ 0, 1, \ldots, m-1\}$ in time o(log n) and in linear space with o(n) operations using word length log m log n. (2) the second variant sorts integers in {0, 1, . . , n-1} in time o(log n) and in linear space with $o(n\sqrt{\log n})$ operations using word length log n. (3) the third variant sorts integers in {0, 1, . . . , m-1} in time o(log3/2 n) and in linear space with $o(n\sqrt{\log n})$ operations using word length log (m+n). (4) the fourth variant sorts integers in {0, 1, . . . ,m-1} in time o(log n) and space $o(nm^\epsilon )$ with $o(n\sqrt{\log n})$ operations using word length log (m+n).our algorithms can then be generalized to the situation where the word length is k log (m+n), $1 \leq k \leq \log n$.
on the distributed complexity of computing maximal matchings. we show that maximal matchings can be computed deterministically in o(log4 n) rounds in the synchronous, message-passing model of computation. this is one of the very few cases known of a nontrivial graph structure, and the only "classical" one, which can be computed distributively in polylogarithmic time without recourse to randomization.
a faster algorithm for finding the minimum cut in a graph. we consider the problem of finding the minimum capacity cut in a network g with n nodes. this problem has applications to network reliability and survivability and is useful in subroutines for other network optimization problems. one can use a maximum flow problem to find a minimum cut separating a designated source node s from a designated sink node t, and by varying the sink node one can find a minimum cut in g as a sequence of at most 2n - 2 maximum flow problems. we then show how to reduce the running time of these 2n - 2 maximum flow algorithms to the running time for solving a single maximum flow problem. the resulting running time is o(nm log n2/m) for finding the minimum cut in either a directed or undirected network. the algorithm also determines the arc connectivity of either a directed or undirected network in o(nm) steps.
online point location in planar arrangements and its applications. recently, har-peled [17] presented a new randomized technique for online construction of the zone of a curve in a planar arrangement of arcs. in this paper: we present several applications of this technique, which yield improved solutions to a variety of problems. these applications include: (i) an efficient mechanism for performing online point location queries in an arrangement of arcs; (ii) an efficient algorithm for computing an approximation to the minimum-weight steiner-tree of a set of points, where the weight is the number of intersections between the tree edges and a given collection of arcs; (iii) a subquadratic algorithm for cutting a set of pseudo-parabolas into pseudo-segments; (iv) an algorithm for cutting a set of line segments (`rods') in 3-space so as to eliminate all cycles in the vertical depth order; and (v) a near-optimal algorithm for reporting all bichromatic intersections between a set r of red arcs and a set b of blue arcs, where the unions of the arcs in each set are both connected.
how fast is the k-means method? we present polynomial upper and lower bounds on the number of iterations performed by the k-means method (a.k.a. lloyd's method) for k-means clustering. our upper bounds are polynomial in the number of points, number of clusters, and the spread of the point set. we also present a lower bound, showing that in the worst case the k-means heuristic needs to perform &omega;(n) iterations, for n points on the real line and two centers. surprisingly, the spread of the point set in this construction is polynomial. this is the first construction showing that the k-means heuristic requires more than a polylogarithmic number of iterations. furthermore, we present two alternative algorithms, with guaranteed performance, which are simple variants of the k-means method.
unknotting is in am cup co-am. hass, lagarias, and pippenger analyzed the computational complexity of various decision problems in knot theory. they proved that the problem whether a given knot is unknotting is in np, and conjectured that the problem is contained in np&cap;co-np. agol, hass, and thurston proved that the problem called manifoldgenus, which is a general problem of unknotting, is np-complete. we construct an interactive proof system for knotting, and prove that the problem is contained in ip(2). consequently, unknotting is contained in am &cap; co-am. if unknotting is np-complete, then &sigma;2p = &pi;2p.
an optimal (expected time) algorithm for minimizing lab costs in dna sequencing. the final step for obtaining very accurate dna sequence data is known as "finishing." most steps of dna sequencing are highly automated, but it is only recently that researchers have looked at automating the finishing step. our perspective is to look at automated finishing as an optimization problem, with the goal to minimize lab costs.we give new algorithms for solving this problem. we look at a model of the problem for which previous researchers gave an o(n4) algorithm (where n is the length of the dna measured in reads). we give an algorithm that runs in o(n2⅓) worst case time. we then show that the algorithm runs in o(n) expected time, if we make an assumption, accepted by many molecular biologists, about randomness in the input data.
deterministic network coding by matrix completion. we present a new deterministic algorithm to construct network codes for multicast problems, a particular class of network information ow problems. our algorithm easily generalizes to several variants of multicast problems. our approach is based on a new algorithm for maximum-rank completion of mixed matrices---taking a matrix whose entries are a mixture of numeric values and symbolic variables, and assigning values to the variables so as to maximize the resulting matrix rank. our algorithm is faster than existing deterministic algorithms and can operate over a smaller field.
the complexity of matrix completion. given a matrix whose entries are a mixture of numeric values and symbolic variables, the matrix completion problem is to assign values to the variables so as to maximize the resulting matrix rank. this problem has deep connections to computational complexity and numerous important algorithmic applications. determining the complexity of this problem is a fundamental open question in computational complexity. under different settings of parameters, the problem is variously in p, in rp, or np-hard. we shed new light on this landscape by demonstrating a new region of np-hard scenarios. as a special case, we obtain the first known hardness result for matrices in which each variable appears only twice.another particular scenario that we consider is the simultaneous matrix completion problem, where one must simultaneously maximize the rank for several matrices that share variables. this problem has important applications in the field of network coding. recent work has given a simple, greedy, deterministic algorithm for this problem, assuming that the algorithm works over a sufficiently large field. we show an exact threshold for the field size required to find a simultaneous completion efficiently. this result implies that, surprisingly, the simple greedy algorithm is optimal: finding a simultaneous completion over any smaller field is np-hard.
variable length path coupling. we present a new technique for constructing and analyzing couplings to bound the convergence rate of finite markov chains. our main theorem is a generalization of the path coupling theorem of bubley and dyer, allowing the defining partial couplings to have length determined by a random stopping time. unlike the original path coupling theorem, our version can produce multi-step (non-markovian) couplings. using our variable length path coupling theorem, we improve the upper bound on the mixing time of the glauber dynamics for randomly sampling colorings.
coupling with the stationary distribution and improved sampling for colorings and independent sets. we present an improved coupling technique for analyzing the mixing time of markov chains. using our technique, we simplify and extend previous results for sampling colorings and independent sets. our approach uses properties of the stationary distribution to avoid worst-case configurations which arise in the traditional approach.as an application, we show that for k/&delta; > 1.764, the glauber dynamics on k-colorings of a graph on n vertices with maximum degree &delta; converges in o(n log n) steps, assuming &delta; = &omega;(log n) and that the graph is triangle-free. previously, girth &ge; 5 was needed.as a second application, we give a polynomial-time algorithm for sampling weighted independent sets from the gibbs distribution of the hard-core lattice gas model at fugacity &lambda; < (1 - &epsilon;)e/&delta;, on a regular graph g on n vertices of degree &delta; = &omega;(log n) and girth &ge; 6. the best known algorithm for general graphs currently assumes &lambda; < 2/(&delta; - 2).