Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem

• URL: http://arxiv.org/abs/2105.12525v1
• Date: Wed, 26 May 2021 13:00:31 GMT
• Title: Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem
• Authors: Jakob Bossek, Frank Neumann, Pan Peng, Dirk Sudholt
• Abstract summary: We study the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized searchs to recompute high quality solutions.
• Score: 15.45783225341009
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical vertex coloring problem on graphs and investigate the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized search heuristics to recompute high quality solutions. The (1+1)~Evolutionary Algorithm and RLS operate in a setting where the number of colors is bounded and we are minimizing the number of conflicts. Iterated local search algorithms use an unbounded color palette and aim to use the smallest colors and, consequently, the smallest number of colors. We identify classes of bipartite graphs where reoptimization is as hard as or even harder than optimization from scratch, i.e., starting with a random initialization. Even adding a single edge can lead to hard symmetry problems. However, graph classes that are hard for one algorithm turn out to be easy for others. In most cases our bounds show that reoptimization is faster than optimizing from scratch. We further show that tailoring mutation operators to parts of the graph where changes have occurred can significantly reduce the expected reoptimization time. In most settings the expected reoptimization time for such tailored algorithms is linear in the number of added edges. However, tailored algorithms cannot prevent exponential times in settings where the original algorithm is inefficient.

Related papers

• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs [3.707290781951909]
  Causal effect estimation from observational data is a fundamental task in empirical sciences. This paper focuses on front-door adjustment -- a classic technique which, using observed mediators, allows to identify causal effects even in the presence of unobserved confounders.
  arXiv  Detail & Related papers  (2022-11-29T18:44:03Z)
• Withdrawn: A Measurement-based Algorithm for Graph Colouring [0.5482532589225553]
  In a previous version of this document we misinterpreted the runtime of a part of the described algorithm. We present a novel algorithmic approach to find a proper colouring of a graph with $d$ colours, if it exists.
  arXiv  Detail & Related papers  (2021-11-29T09:17:34Z)
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization [111.24899593052851]
  Conditional gradient algorithm (also known as the Frank-Wolfe algorithm) has recently regained popularity in the machine learning community. ARCS is the first zeroth-order conditional gradient sliding type algorithms solving convex problems in zeroth-order optimization. In first-order optimization, the convergence results of ARCS substantially outperform previous algorithms in terms of the number of gradient query oracle.
  arXiv  Detail & Related papers  (2021-09-18T07:08:11Z)
• A Grover search-based algorithm for the list coloring problem [1.332560004325655]
  We propose a quantum algorithm based on Grover search to speed up exhaustive search. Our algorithm loses in complexity to classical ones in specific restricted cases, but improves exhaustive search for cases where the lists and graphs considered are arbitrary in nature.
  arXiv  Detail & Related papers  (2021-08-20T08:41:22Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  In this paper, we denote the non-strongly setting on the magnitude of a gradient-free minimax optimization problem. We show that a novel zeroth-order variance reduced descent algorithm achieves the best known query complexity.
  arXiv  Detail & Related papers  (2020-06-16T17:55:46Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  We study the problem of zero-order optimization of a strongly convex function. We consider a randomized approximation of the projected gradient descent algorithm. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
  arXiv  Detail & Related papers  (2020-06-14T10:42:23Z)
• Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time [12.43303621344215]
  We develop a new framework to solve any optimization problem over graphs without expert knowledge. Our method trains a graph neural network using reinforcement learning on an unlabeled training set of graphs. We demonstrate our approach on both NP-hard problems with optimality gaps close to 1, and show that our method is able to generalize well.
  arXiv  Detail & Related papers  (2020-06-06T01:35:45Z)
• More Effective Randomized Search Heuristics for Graph Coloring Through Dynamic Optimization [15.45783225341009]
  We show that evolutionary algorithms can solve the graph coloring problem for bipartite graphs more efficiently by using dynamic optimization. An island model using 3 islands succeeds in an optimal time of $Theta(m)$ on every $m$-edge bipartite graph, outperforming offspring populations.
  arXiv  Detail & Related papers  (2020-05-28T07:55:12Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.