Multilevel Memetic Hypergraph Partitioning with Greedy Recombination
- URL: http://arxiv.org/abs/2204.03730v1
- Date: Thu, 7 Apr 2022 20:45:17 GMT
- Title: Multilevel Memetic Hypergraph Partitioning with Greedy Recombination
- Authors: Utku Umur Acikalin, Bugra Caskurlu
- Abstract summary: KaHyPar-E is the first multilevel memetic computation algorithm designed for the Hypergraph Partitioning problem.
We introduce novel problem-specific recombination and mutation operators, and develop a new multilevel memetic algorithm by combining KaHyPar-E with these operators.
Our algorithm outperforms all others and finds the best solutions in $112$, $115$, and $125$ instances in $2, 4$, and $8$ hours, respectively.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Hypergraph Partitioning (HGP) problem is a well-studied problem that
finds applications in a variety of domains. The literature on the HGP problem
has heavily focused on developing fast heuristic approaches. In several
application domains, such as the VLSI design and database migration planning,
the quality of the solution is more of a concern than the running time of the
algorithm. KaHyPar-E is the first multilevel memetic algorithm designed for the
HGP problem and it returns better quality solutions, compared to the heuristic
algorithms, if sufficient computation time is given. In this work, we introduce
novel problem-specific recombination and mutation operators, and develop a new
multilevel memetic algorithm by combining KaHyPar-E with these operators. The
performance of our algorithm is compared with the state-of-the-art HGP
algorithms on $150$ real-life instances taken from the benchmark datasets used
in the literature. In the experiments, which would take $39,000$ hours in a
single-core computer, each algorithm is given $2, 4$, and $8$ hours to compute
a solution for each instance. Our algorithm outperforms all others and finds
the best solutions in $112$, $115$, and $125$ instances in $2, 4$, and $8$
hours, respectively.
Related papers
- Unlocking the Potential of Operations Research for Multi-Graph Matching [14.3836693915104]
Multi-graph matching plays a central role in computer vision, e.g., for matching images or shapes.
We transfer well-known approximation algorithms for the MDAP to incomplete multi-graph matching.
Our algorithm matches, for example, 29 images with more than 500 keypoints each in less than two minutes, whereas the fastest considered competitor requires at least half an hour.
arXiv Detail & Related papers (2024-06-26T09:58:05Z) - EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
We present EKM: a novel algorithm for solving this problem exactly with worst-case $Oleft(NK+1right)$ complexity.
EKM is developed according to recent advances in transformational programming and generation, using formal program steps.
We show that the wall-clock run time of our algorithm matches the worst-case time complexity analysis on synthetic datasets.
arXiv Detail & Related papers (2024-05-16T15:11:37Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al.
A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$.
We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
arXiv Detail & Related papers (2024-02-09T19:01:48Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching.
Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
arXiv Detail & Related papers (2022-10-14T01:42:05Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms.
For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime.
In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem.
We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
arXiv Detail & Related papers (2021-09-13T18:10:52Z) - Combining K-means type algorithms with Hill Climbing for Joint
Stratification and Sample Allocation Designs [0.0]
This is a sample problem in which we search for the optimal stratification from the set of all possible stratifications of basic strata.
evaluating the cost of each solution is expensive.
We compare the above multi-stage combination of algorithms with three recent algorithms and report the solution costs, evaluation times and training times.
arXiv Detail & Related papers (2021-08-18T08:41:58Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
Bilevel optimization has been widely applied in many important machine learning applications.
We propose two new algorithms for bilevel optimization.
We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
arXiv Detail & Related papers (2021-06-08T21:05:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - 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) - Towards Solving Large-scale Expensive Optimization Problems Efficiently
Using Coordinate Descent Algorithm [3.1600708674008393]
We propose a modified Coordinate Descent algorithm (MCD) to tackle LSEGO problems with a limited computational budget.
Our proposed algorithm benefits from two leading steps, namely, finding the region of interest and then shrinkage of the search space by folding it into the half with exponential speed.
The proposed algorithm is compared with cooperative co-evolution with delta grouping on 20 benchmark functions with dimension 1000.
arXiv Detail & Related papers (2020-03-07T22:48:38Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
Mixed integer programming (MIP) can be used to solve (to optimality) $ell_0$-regularized regression problems.
We propose two classes of scalable algorithms: an exact algorithm that can handlepapprox 50,000$ features in a few minutes, and approximate algorithms that can address instances with $papprox6$.
In addition, we present new estimation error bounds for $ell$-regularizeds.
arXiv Detail & Related papers (2020-01-17T18:47:02Z)
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.