Improving a State-of-the-Art Heuristic for the Minimum Latency Problem with Data Mining

• URL: http://arxiv.org/abs/1908.10705v2
• Date: Sun, 11 Jun 2023 23:27:05 GMT
• Title: Improving a State-of-the-Art Heuristic for the Minimum Latency Problem with Data Mining
• Authors: \'Italo Santana, Alexandre Plastino, Isabel Rosseti
• Abstract summary: Hybrid metaheuristics have become a trend in operations research. A successful example combines the Greedy Randomized Adaptive Search Procedures (GRASP) and data mining techniques.
• Score: 69.00394670035747
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, hybrid metaheuristics have become a trend in operations research. A successful example combines the Greedy Randomized Adaptive Search Procedures (GRASP) and data mining techniques, where frequent patterns found in high-quality solutions can lead to an efficient exploration of the search space, along with a significant reduction of computational time. In this work, a GRASP-based state-of-the-art heuristic for the Minimum Latency Problem (MLP) is improved by means of data mining techniques for two MLP variants. Computational experiments showed that the approaches with data mining were able to match or improve the solution quality for a large number of instances, together with a substantial reduction of running time. In addition, 88 new cost values of solutions are introduced into the literature. To support our results, tests of statistical significance, impact of using mined patterns, equal time comparisons and time-to-target plots are provided.

Related papers

• CoSTI: Consistency Models for (a faster) Spatio-Temporal Imputation [0.0]
  CoSTI employs Consistency Training to achieve comparable imputation quality to DDPMs while drastically reducing inference times. We evaluate CoSTI across multiple datasets and missing data scenarios, demonstrating up to a 98% reduction in imputation time with performance par with diffusion-based models.
  arXiv  Detail & Related papers  (2025-01-31T18:14:28Z)
• Accelerated Methods with Compressed Communications for Distributed Optimization Problems under Data Similarity [55.03958223190181]
  We propose the first theoretically grounded accelerated algorithms utilizing unbiased and biased compression under data similarity. Our results are of record and confirmed by experiments on different average losses and datasets.
  arXiv  Detail & Related papers  (2024-12-21T00:40:58Z)
• Efficient Architecture Search via Bi-level Data Pruning [70.29970746807882]
  This work pioneers an exploration into the critical role of dataset characteristics for DARTS bi-level optimization. We introduce a new progressive data pruning strategy that utilizes supernet prediction dynamics as the metric. Comprehensive evaluations on the NAS-Bench-201 search space, DARTS search space, and MobileNet-like search space validate that BDP reduces search costs by over 50%.
  arXiv  Detail & Related papers  (2023-12-21T02:48:44Z)
• High-dimensional Contextual Bandit Problem without Sparsity [8.782204980889077]
  We propose an explore-then-commit (EtC) algorithm to address this problem and examine its performance. We derive the optimal rate of the ETC algorithm in terms of $T$ and show that this rate can be achieved by balancing exploration and exploitation. We introduce an adaptive explore-then-commit (AEtC) algorithm that adaptively finds the optimal balance.
  arXiv  Detail & Related papers  (2023-06-19T15:29:32Z)
• A Projected Upper Bound for Mining High Utility Patterns from Interval-Based Event Sequences [0.0]
  We propose a projected upper bound on the utility of the patterns discovered from sequences of interval-based events. Experimental results show that the new upper bound improves HUIPMiner performance in terms of both execution time and memory usage.
  arXiv  Detail & Related papers  (2022-12-21T21:06:07Z)
• Fast Bayesian Optimization of Needle-in-a-Haystack Problems using Zooming Memory-Based Initialization [73.96101108943986]
  A Needle-in-a-Haystack problem arises when there is an extreme imbalance of optimum conditions relative to the size of the dataset. We present a Zooming Memory-Based Initialization algorithm that builds on conventional Bayesian optimization principles.
  arXiv  Detail & Related papers  (2022-08-26T23:57:41Z)
• Time-Series Anomaly Detection with Implicit Neural Representation [0.38073142980733]
  Implicit Neural Representation-based Anomaly Detection (INRAD) is proposed. We train a simple multi-layer perceptron that takes time as input and outputs corresponding values at that time. Then we utilize the representation error as an anomaly score for detecting anomalies.
  arXiv  Detail & Related papers  (2022-01-28T06:17:24Z)
• DEALIO: Data-Efficient Adversarial Learning for Imitation from Observation [57.358212277226315]
  In imitation learning from observation IfO, a learning agent seeks to imitate a demonstrating agent using only observations of the demonstrated behavior without access to the control signals generated by the demonstrator. Recent methods based on adversarial imitation learning have led to state-of-the-art performance on IfO problems, but they typically suffer from high sample complexity due to a reliance on data-inefficient, model-free reinforcement learning algorithms. This issue makes them impractical to deploy in real-world settings, where gathering samples can incur high costs in terms of time, energy, and risk. We propose a more data-efficient IfO algorithm
  arXiv  Detail & Related papers  (2021-03-31T23:46:32Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• A Robust Matching Pursuit Algorithm Using Information Theoretic Learning [37.968665739578185]
  A new OMP algorithm is developed based on the information theoretic learning (ITL) The experimental results on both simulated and real-world data consistently demonstrate the superiority of the proposed OMP algorithm in data recovery, image reconstruction, and classification.
  arXiv  Detail & Related papers  (2020-05-10T01:36:00Z)

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.