waashk/dblp huggingface dataset:
experimental analysis of simple, distributed vertex coloring algorithms. we perform an extensive experimental evaluation of very simple, distributed, randomized algorithms for (&delta; + 1)- and so-called brooks-vizing vertex colorings, i.e., colorings using considerably fewer than &delta; colors. we consider variants of algorithms known from the literature, boosting them with a distributed independent set computation. our study clearly determines the relative performance of the algorithms w.r.t. the number of communication rounds and the number of colors. the results are confirmed by all the experiments and instance families. the empirical evidence shows that some algorithms are extremely fast and very effective, thus being amenable to be used in practice.
testing graphs for colorable properties. let p be a property of graphs. an &egr;-test for p is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph g with n vertices are adjacent or not, distinguishes, with high probability, between the case of g satisfying p and the case that it has to be modified by adding and removing more than &egr;( <stack>2n</stack>) edges to make it satisfy p. the property p is called testable if for every &egr; there exists an &egr;-test for p whose total number of queries is independent of the size of the input graph. goldreich, goldwasser, and ron [property testing and its connection to learning and approximation, j acm 45 (1998), 653&ndash;750] showed that certain graph properties, like k-colorability, admit an &egr;-test. in alon, fischer, krivelevich, and szegedy [efficient testing of large graphs, combinatorica 20 (2000), 451&ndash;476] a first step towards a logical characterization of the testable graph properties was made by proving that all first order properties of type &ldquo;&exist;&forall;&rdquo; are testable, while there exist first-order graph properties of type &ldquo;&exist;&forall;&rdquo; that are not testable. for proving the positive part, it was shown that all properties describable by a very general type of coloring problem are testable. while this result is tight from the standpoint of first order expressions, further steps towards the characterization of the testable graph properties can be taken by considering the coloring problem instead. it is proven here that other classes of graph properties, describable by various generalizations of the coloring notion used in alon et al. [combinatorica 20 (2000), 451&ndash;476], are testable, showing that this approach can broaden the understanding of the nature of the testable graph properties. the proof combines some generalizations of the methods used in alon et al. with additional methods. &copy; 2004 wiley periodicals, inc. random struct. alg., 2005an extended abstract of this paper has appeared in the proceedings of the 12th acm-siam soda (2001), 873&ndash;882.
testing graph isomorphism. we deal with the question of how many queries are required to distinguish between the case that two graphs g and h on n vertices are isomorphic, and the case that they are &epsilon;-far, that is they differ in more than &epsilon;(n2) pairs for all possible bijections of their vertices. querying is defined as probing the adjacency matrix of any one of the two graphs, i.e. asking if a pair of vertices forms an edge of the graph or not.we investigate both one-sided error and two-sided error testers under two possible settings: the first setting is where both graphs need to be queried; and the second setting is where one of the graphs is known to the algorithm in advance.we prove that the query complexity of the one-sided error testing problem is &theta;(n3/2) if both graphs need to be queried, and that it is &theta;(n) if one of the graphs is known in advance (where the &theta; notation hides polylogarithmic factors in the upper bounds). for the two-sided error testers we prove that the query complexity is &theta;(&radic;n when one of the graphs is known in advance, and we show that the query complexity lies between &omega;(n) and &otilde;(n5/4) if both g and h need to be queried. all of our algorithms are additionally non-adaptive, while all of our lower bounds apply for adaptive testers as well as non-adaptive ones.
a spectral technique for random satisfiable 3cnf formulas. let i be a random 3cnf formula generated by choosing a truth assignment &phis; for variables x1, xn uniformly at random and including every clause with i literals set true by &phis; with probability pi, independently. we show that for any constants 0 &le; &eta;2,&eta;3 &le; 1 there is a constant dmin so that for all d &ge; dmin a spectral algorithm similar to the graph coloring algorithm of alon and kahale will find a satisfying assignment with high probability for p1 = d-n2, p2 = &eta;2d-n2, and p3 = &eta;3d-n2. appropriately setting the &eta;i's yields natural distributions on satisfiable 3cnfs, not-all-equal-sat 3cnfs, and exactly-one-sat 3cnfs. &copy; 2008 wiley periodicals, inc. random struct. alg., 2008
on the random 2-stage minimum spanning tree. it is known [7] that if the edge costs of the complete graph kn are independent random variables, uniformly distributed between 0 and 1, then the expected cost of the minimum spanning tree is asymptotically equal to &zeta;(3) = &sigma; &infin;i=1 i-3. here we consider the following stochastic two-stage version of this optimization problem. there are two sets of edge costs cm: e &larr; r and ct: e &larr; r, called monday's prices and tuesday's prices, respectively. for each edge e, both costs cm(e) and ct(e) are independent random variables, uniformly distributed in [0, 1]. the monday costs are revealed first. the algorithm has to decide on monday for each edge e whether to buy it at monday's price cm(e), or to wait until its tuesday price ct(e) appears. the set of edges xm bought on monday is then completed by the set of edges xt bought on tuesday to form a spanning tree. if both monday's and tuesday's prices were revealed simultaneously, then the optimal solution would have expected cost &zeta;(3)/2 + o(1). we show that in the case of two-stage optimization, the expected value of the optimal cost exceeds &zeta;(3)/2 by an absolute constant &isin; > 0. we also consider a threshold heuristic, where the algorithm buys on monday only edges of cost less than &alpha; and completes them on tuesday in an optimal way, and show that the optimal choice for &alpha; is &alpha; = 1/n with the expected cost &zeta;(3) - 1/2 + o(1). the threshold heuristic is shown to be sub-optimal. finally we discuss the directed version of the problem, where the task is to construct a spanning out-arborescence rooted at a fixed vertex r, and show, somewhat surprisingly, that in this case a simple variant of the threshold heuristic gives the asymptotically optimal value 1 - 1/e + o(1).
adversarial deletion in a scale free random graph process. we study a dynamically evolving random graph which adds vertices and edges using preferential attachment and is &lsquo;attacked by an adversary&rsquo;. at time $t$, we add a new vertex $x_t$ and $m$ random edges incident with $x_t$, where $m$ is constant. the neighbours of $x_t$ are chosen with probability proportional to degree. after adding the edges, the adversary is allowed to delete vertices. the only constraint on the adversarial deletions is that the total number of vertices deleted by time $n$ must be no larger than $\delta n$, where $\delta$ is a constant. we show that if $\delta$ is sufficiently small and $m$ is sufficiently large then with high probability at time $n$ the generated graph has a component of size at least $n/30$.
online convex optimization in the bandit setting: gradient descent without a gradient. we study a general online convex optimization problem. we have a convex set s and an unknown sequence of cost functions c1, c2,..., and in each period, we choose a feasible point xt in s, and learn the cost ct(xt). if the function ct is also revealed after each period then, as zinkevich shows in [25], gradient descent can be used on these functions to get regret bounds of o(&radic;n). that is, after n rounds, the total cost incurred will be o(&radic;n) more than the cost of the best single feasible decision chosen with the benefit of hindsight, minx &sigma; ct(x).we extend this to the "bandit" setting, where, in each period, only the cost ct(xt) is revealed, and bound the expected regret as o(n3/4).our approach uses a simple approximation of the gradient that is computed from evaluating ct at a single (random) point. we show that this biased estimate is sufficient to approximate gradient descent on the sequence of functions. in other words, it is possible to use gradient descent without seeing anything more than the value of the functions at a single point. the guarantees hold even in the most general case: online against an adaptive adversary.for the online linear optimization problem [15], algorithms with low regrets in the bandit setting have recently been given against oblivious [1] and adaptive adversaries [19]. in contrast to these algorithms, which distinguish between explicit explore and exploit periods, our algorithm can be interpreted as doing a small amount of exploration in each period.
a fast approximation scheme for fractional covering problems with variable upper bounds. we present the first combinatorial approximation scheme for mixed positive packing and covering linear programs that yields a pure approximation guarantee. our algorithm returns solutions that simultaneously satisfy general positive covering constraints and packing constraints that are variable upper bounds. the returned solution has positive linear objective function value at most 1 + ε times the optimal value.our approximation scheme is based on lagrangian-relaxation methods. previous such approximation schemes for mixed packing and covering problems does not simultaneously satisfy packing and covering constraints exactly. we show how to exactly satisfy general positive covering constraints simultaneously with variable upper bounds.a natural set of problems that our work addresses are linear programs for various network design problems: generalized steiner network, vertex connectivity, directed connectivity, capacitated network design, group steiner forest. these are all np-hard problems for which there are approximation algorithms that round the solution to the corresponding linear program. solving the linear program is often the computational bottleneck in these problems, and thus a fast approximation scheme for the lp relaxation means faster approximation algorithms.for the special case of survivable network design, we introduce a new modification of the push-relabel maximum flow algorithm that allows us to perform each iteration in amortized o(m + n log n) time, instead of one maximum flow per iteration that is implied by the straight forward adaptation of our general algorithm. (m is the number of edges and n is the number of vertices in the network.) in conjunction with an observation that reduces the number of iterations to {log n for f0} constraint matrices, the modification allows us to obtain an algorithm that is faster than existing exact or approximate algorithms by a factor of at least o(m) and by a factor of o(m log n) if the number of demand pairs is &omega;(n).
tight approximation algorithms for maximum general assignment problems. a separable assignment problem (sap) is defined by a set of bins and a set of items to pack in each bin; a value, fij, for assigning item j to bin i; and a separate packing constraint for each bin - i.e. for bin i, a family li of subsets of items that fit in bin i. the goal is to pack items into bins to maximize the aggregate value. this class of problems includes the maximum generalized assignment problem (gap)1) and a distributed caching problem (dcp) described in this paper.given a &beta;-approximation algorithm for finding the highest value packing of a single bin, we give1. a polynomial-time lp-rounding based ((1 &minus; 1/e)&beta;)-approximation algorithm.2. a simple polynomial-time local search (&beta;/&beta;+1 - &epsilon;) - approximation algorithm, for any &epsilon; > 0.therefore, for all examples of sap that admit an approximation scheme for the single-bin problem, we obtain an lp-based algorithm with (1 - 1/e - &epsilon;)-approximation and a local search algorithm with (1/2-&epsilon;)-approximation guarantee. furthermore, for cases in which the subproblem admits a fully polynomial approximation scheme (such as for gap), the lp-based algorithm analysis can be strengthened to give a guarantee of 1 - 1/e. the best previously known approximation algorithm for gap is a 1/2-approximation by shmoys and tardos; and chekuri and khanna. our lp algorithm is based on rounding a new linear programming relaxation, with a provably better integrality gap.to complement these results, we show that sap and dcp cannot be approximated within a factor better than 1 -1/e unless np&sube; dtime(no(log log n)), even if there exists a polynomial-time exact algorithm for the single-bin problem.we extend the (1 - 1/e)-approximation algorithm to a nonseparable assignment problem with applications in maximizing revenue for budget-constrained combinatorial auctions and the adwords assignment problem. we generalize the local search algorithm to yield a 1/2-&epsilon; approximation algorithm for the k-median problem with hard capacities. finally, we study naturally defined game-theoretic versions of these problems, and show that they have price of anarchy of 2. we also prove the existence of cycles of best response moves, and exponentially long best-response paths to (pure or sink) equilibria.
approximately optimal control of fluid networks. we give an approximation algorithm for the optimal control problem in fluid networks. such problems arise as fluid relaxations of multiclass queueing networks, and are used to find approximate solutions to complex job shop scheduling problems. in a network with linear flow costs and linear, per-unit-time holding costs, our algorithm finds a drainage of the network, that for given constants &epsilon; > 0 and &delta; > 0 has total cost (1 + &epsilon;)opt + &delta;, where opt is the cost of the minimum cost drainage. the complexity of our algorithm is polynomial in the size of the input network, 1/&epsilon; and log 1/&delta;. the fluid relaxation is a continuous problem. while the problem is known to have a piecewise constant solution, it is not known to have a polynomially-sized solution. we introduce a natural discretization of polynomial size and prove that this discretization produces a solution with low cost. this is the first polynomial time algorithm with a provable approximation guarantee for fluid relaxations.
minimum cost flows over time without intermediate storage. flows over time (also called dynamic flows) generalize standard network flows by introducing an element of time. they naturally model problems where travel and transmission are not instantaneous. solving these problems raises issues that do not arise in standard network flows. one issue is the question of storage of flow at intermediate nodes. in most applications (such as, e.g., traffic routing, evacuation planning, telecommunications etc.), intermediate storage is limited, undesired, or prohibited.the minimum cost flow over time problem is np-hard. in this paper we 1) prove that the minimum cost flow over time never requires storage; 2) provide the first approximation scheme for minimum cost flows over time that does not require storage; 3) provide the first approximation scheme for minimum cost flows over time that meets hard cost constraints, while approximating only makespan.our approach is based on a condensed variant of time- expanded networks. it also yields fast approximation schemes with simple solutions for the quickest multicommodity flow problem.finally, using completely different techniques, we describe a very simple capacity scaling fpas for the minimum cost flow over time problem when costs are proportional to transit times. the algorithm builds upon our observation about the structure of optimal solutions to this problem: they are universally quickest flows. again, the fpas does not use intermediate node storage. in contrast to the preceding algorithms that use a time-expanded network, this fpas runs directly on the original network.
measure and conquer: a simple o(2) independent set algorithm. for more than 30 years davis-putnam-style exponential-time backtracking algorithms have been the most common tools used for finding exact solutions of np-hard problems. despite of that, the way to analyze such recursive algorithms is still far from producing tight worst case running time bounds.the "measure and conquer" approach is one of the recent attempts to step beyond such limitations. the approach is based on the choice of the measure of the subproblems recursively generated by the algorithm considered; this measure is used to lower bound the progress made by the algorithm at each branching step. a good choice of the measure can lead to a significantly better worst case time analysis.in this paper we apply "measure and conquer" to the analysis of a very simple backtracking algorithm solving the well-studied maximum independent set problem. the result of the analysis is striking: the running time of the algorithm is o(20.288n), which is competitive with the current best time bounds obtained with far more complicated algorithms (and naive analysis).our example shows that a good choice of the measure, made in the very first stages of exact algorithms design, can have a tremendous impact on the running time bounds achievable.
dominating sets in planar graphs: branch-width and exponential speed-up. we introduce a new approach to design parameterized algorithms on planar graphs which builds on the seminal results of robertson and seymour on graph minors. graph minors provide a list of powerful theoretical results and tools. however, the widespread opinion in the graph algorithms community about this theory is that it is of mainly theoretical importance. in this paper we show how deep min-max and duality theorems from graph minors can be used to obtain exponential speed-up to many known practical algorithms for different domination problems. our use of branch-width instead of the usual tree-width allows us to obtain much faster algorithms. by using this approach, we show that the k-dominating set problem on planar graphs can be solved in time o(215.13 \sqrt k + n3).
proximity mergesort: optimal in-place sorting in the cache-oblivious model. an algorithm performs its operations in-place if it uses o(1) extra locations of main memory besides those containing the input entries. an algorithm is cache-oblivious if it is not conscious of any parameter of the memory hierarchy (m, the size of cache memory, and b, the size of the minimal contiguous block of information that can be transferred between the cache and the main memory). hence, it cannot directly exploit these parameters to reach the optimality. in the cache-oblivious model the complexity is measured with two criteria: the work complexity, which is the standard complexity in the ram model, and the cache complexity, which is the total number of block transfers (cache misses) incurred during the computation.the contribution of this paper is twofold. we present the first sorting algorithm that is optimal in both work and cache complexity in the cache-oblivious model and that operates in-place. furthermore, we introduce a new approach to the sorting problem in the cache-oblivious model.
implicit dictionaries supporting searches and amortized updates in o(log n log log n) time. we describe a new implicit data structure for maintaining n data values in the first n locations of an array. no information other than n and the data is to be retained, and the only operations which we may perform on the data values (other than reads and writes) are comparisons. our structure supports searches in o(log n log log n) time in the worst case, and insertions and deletions in o(log n log log n) amortized time. the best known bound for these operations in main memory is o(log 2 n/log log n) in the worst case.
implicit dictionaries with (1) modifications per update and fast search. the implicit dictionary problem is that of maintaining a dynamic ordered set, s, under the operations search, insert and delete, so that the elements of s are stored in the first |s| locations of an array. no operations are permitted on the data other than comparisons (&le;) and interchanges. the only auxiliary memory permitted is a constant number of o(log |s|) bit integers. the organization will, then, rely heavily on the permutations of the relative order of the values in which the data is stored. while such a structure can be maintained in o(log |s|) time, the most interesting lower bound on the topic is that of borodin, fich, meyer auf der heide, upfal and wigderson [3]. they proved a tradeoff between search and update time in implicit dictionaries: if the update cost (comparisons and exchanges) is o(1), then the search cost must be &omega;(|s|&epsilon;), for some constant &epsilon; > 0. the authors left open the question of whether such a tradeoff would hold if only the modifications performed during an update were considered. they conjectured that any implicit dictionary performing only o(1) exchanges per update should very quickly become "disorganized", and so require &omega;(|s|&epsilon;) comparisons per search. we answer this long-standing open question by disproving the conjecture.
edge-disjoint paths in expander graphs. given a graph g=(v,e)and a set of $\kappa$ pairs of vertices in v, we are interested in finding, for each pair (ai, bi), a path connecting ai to bi such that the set of $\kappa$ paths so found is edge-disjoint. for arbitrary graphs the problem is ${\cal np}$-complete, although it is in ${\cal p}$ if $\kappa$ is fixed. we present a polynomial time randomized algorithm for finding edge-disjoint paths in an r-regular expander graph g. we show that if g has sufficiently strong expansion properties and r is sufficiently large, then all sets of $\kappa=\omega(n/\log n)$ pairs of vertices can be joined. this is within a constant factor of best possible.
random graphs. we will review some of the major results in random graphs and some of the more challenging open problems. we will cover algorithmic and structural questions. we will touch on newer models, including those related to the www.
the probabilistic relationship between the assignment and asymmetric traveling salesman problems. we consider the gap between the cost of an optimal assignment in a complete bipartite graph with random edge weights, and the cost of an optimal traveling salesman tour in a complete directed graph with the same edge weights. using an improved &ldquo;patching&rdquo; heuristic, we show that with high probability the gap is $o((\ln n)^2/n)$, and that its expectation is $\omega(1/n)$. one of the underpinnings of this result is that the largest edge weight in an optimal assignment has expectation $\theta(\ln n / n)$. a consequence of the small assignment-tsp gap is an $e^{\tilde{o}(\sqrt{n})}$-time algorithm which, with high probability, exactly solves a random asymmetric traveling salesman instance. in addition to the assignment-tsp gap, we also consider the expected gap between the optimal and second-best assignments; it is at least $\omega(1/n^2)$ and at most $o(\ln n/n^2)$.
optimal construction of edge-disjoint paths in random regular graphs. given a graph g = (v, e) and a set of &kappa; pairs of vertices in v, we are interested in finding, for each pair (ai, bi), a path connecting ai to bi such that the set of &kappa; paths so found is edge-disjoint. (for arbitrary graphs the problem is &nscr;&pscr;-complete, although it is in &pscr; if &kappa; is fixed.)we present a polynomial time randomized algorithm for finding edge-disjoint paths in the random regular graph gn,r, for sufficiently large r. (the graph is chosen first, then an adversary chooses the pairs of end-points.) we show that almost every gn,r is such that all sets of &kappa; = &omega;(n&#x002f;log n) pairs of vertices can be joined. this is within a constant factor of the optimum.