ARES: An Efficient Algorithm with Recurrent Evaluation and Sampling-Driven Inference for Maximum Independent Set
The Maximum Independent Set (MIS) problem is a well-known NP-complete problem with a wide range of applications across various fields. Heuristic approaches are commonly utilized to efficiently tackle large instances of this problem, yielding high-quality solutions within a reasonable time. However, heuristics face challenges such as falling into local optima and redundant searches within the solution space. This paper introduces an efficient heuristic algorithm for the MIS problem, incorporating two innovative techniques. The first technique features a recurrent evaluation mechanism that monitors the progress of solutions and identifies local optima, triggering restarts to avoid convergence on suboptimal outcomes. The second technique utilizes a sampling-driven inference rule to selectively fix vertices based on sampled solutions, thereby narrowing the search space and enhancing efficiency. Comprehensive experimental evaluations across multiple well-established real-world benchmarks demonstrate that the proposed algorithm outperforms state-of-the-art algorithms in terms of solution quality, computational efficiency, and stability.
Code (0)
등록된 구현이 없습니다.
Tasks
Computational EfficiencySimilar Papers 제목 키워드 기반
Approximate discounting-free policy evaluation from transient and recurrent states
In order to distinguish policies that prescribe good from bad actions in transient states, we need to evaluate the so-called bias of a policy from transient states. However, we observe that most (if not all) works in app…
reinforcement-learningReinforcement Learning (RL)Professor Forcing: A New Algorithm for Training Recurrent Networks
The Teacher Forcing algorithm trains recurrent networks by supplying observed sequence values as inputs during training and using the network's own one-step-ahead predictions to do multi-step sampling. We introduce the P…
Domain AdaptationHandwriting generationImage GenerationLanguage Modeling+1An Intrinsic Nearest Neighbor Analysis of Neural Machine Translation Architectures
Earlier approaches indirectly studied the information captured by the hidden states of recurrent and non-recurrent neural machine translation models by feeding them into different classifiers. In this paper, we look at t…
Machine TranslationTranslationWord EmbeddingsAbrupt Motion Tracking via Nearest Neighbor Field Driven Stochastic Sampling
Stochastic sampling based trackers have shown good performance for abrupt motion tracking so that they have gained popularity in recent years. However, conventional methods tend to use a two-stage sampling paradigm, in w…
Motion DetectionWhen Recurrent Neural Networks meet the Neighborhood for Session-Based Recommendation
Deep learning methods have led to substantial progress in various application fields of AI, and in recent years a number of proposals were made to improve recommender systems with artificial neural networks. For the prob…
Recommendation SystemsSession-Based Recommendations