The Importance of Good Starting Solutions in the Minimum Sum of Squares
Clustering Problem
- URL: http://arxiv.org/abs/2004.04593v1
- Date: Mon, 6 Apr 2020 22:13:41 GMT
- Title: The Importance of Good Starting Solutions in the Minimum Sum of Squares
Clustering Problem
- Authors: Pawel Kalczynski, Jack Brimberg and Zvi Drezner
- Abstract summary: The clustering problem has many applications in Machine Learning, Operations Research, and Statistics.
We propose three algorithms to create starting solutions for improvement algorithms for this problem.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The clustering problem has many applications in Machine Learning, Operations
Research, and Statistics. We propose three algorithms to create starting
solutions for improvement algorithms for this problem. We test the algorithms
on 72 instances that were investigated in the literature. Forty eight of them
are relatively easy to solve and we found the best known solution many times
for all of them. Twenty four medium and large size instances are more
challenging. We found five new best known solutions and matched the best known
solution for 18 of the remaining 19 instances.
Related papers
- Navigating the Labyrinth: Evaluating and Enhancing LLMs' Ability to Reason About Search Problems [59.72548591120689]
We introduce a new benchmark, SearchBench, containing 11 unique search problem types.
We show that even the most advanced LLMs fail to solve these problems end-to-end in text.
Instructing LLMs to generate code that solves the problem helps, but only slightly, e.g., GPT4's performance rises to 11.7%.
arXiv Detail & Related papers (2024-06-18T00:44:58Z) - Efficient anytime algorithms to solve the bi-objective Next Release
Problem [2.8148957592979422]
Next Release Problem consists in selecting a subset of requirements to develop in the next release of a software product.
We propose five new methods that maintain a well-spread set of solutions at any time during the search.
arXiv Detail & Related papers (2024-02-07T05:03:31Z) - Problem-Solving Guide: Predicting the Algorithm Tags and Difficulty for
Competitive Programming Problems [10.692589986082922]
Most tech companies require the ability to solve algorithm problems including Google, Meta, and Amazon.
Our study addresses the task of predicting the algorithm tag as a useful tool for engineers and developers.
We also consider predicting the difficulty levels of algorithm problems, which can be used as useful guidance to calculate the required time to solve that problem.
arXiv Detail & Related papers (2023-10-09T15:26:07Z) - Invex Programs: First Order Algorithms and Their Convergence [66.40124280146863]
Invex programs are a special kind of non-constrained problems which attain global minima at every stationary point.
We propose new first-order algorithms to solve general convergence rates in beyondvex problems.
Our proposed algorithm is the first algorithm to solve constrained invex programs.
arXiv Detail & Related papers (2023-07-10T10:11:01Z) - Randomized Greedy Algorithms and Composable Coreset for k-Center
Clustering with Outliers [11.546734084378683]
The presence of outliers can significantly increase the computational complexity.
Our idea is inspired by the greedy method, that was developed for solving the ordinary $k$-center clustering problem.
arXiv Detail & Related papers (2023-01-07T09:26:01Z) - An Adaptive Repeated-Intersection-Reduction Local Search for the Maximum
Independent Set Problem [5.459881847627117]
The independent set (MIS) problem is a classical NP-hard problem with extensive applications in various areas.
We propose an efficient local search algorithm for MIS called ARIR.
Compared with four state-of-the-art algorithms, ARIR offers the best accuracy on 89 instances and obtains competitive results on the three remaining instances.
arXiv Detail & Related papers (2022-08-16T14:39:38Z) - Learning to Solve Hard Minimal Problems [6.117371161379209]
We present an approach to solving hard geometric optimization problems in the RANSAC framework.
The hard minimal problems arise from relaxing the original geometric optimization problem into a minimal problem with many spurious solutions.
arXiv Detail & Related papers (2021-12-06T23:51:20Z) - Algorithm Selection on a Meta Level [58.720142291102135]
We introduce the problem of meta algorithm selection, which essentially asks for the best way to combine a given set of algorithm selectors.
We present a general methodological framework for meta algorithm selection as well as several concrete learning methods as instantiations of this framework.
arXiv Detail & Related papers (2021-07-20T11:23:21Z) - 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) - Towards Meta-Algorithm Selection [78.13985819417974]
Instance-specific algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidates.
We show that meta-algorithm-selection can indeed prove beneficial in some cases.
arXiv Detail & Related papers (2020-11-17T17:27:33Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
We study the problem of clustering a set of items from binary user feedback.
We devise an algorithm with a minimal cluster recovery error rate.
For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
arXiv Detail & Related papers (2019-10-14T09:18:26Z)
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.