检索结果-内蒙古大学图书馆

Approximation Algorithms for Robust clustering problems Using Local Search Techniques 1

18th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Wu, Chenchen Moehring, Rolf H. Wang, Yishui Xu, Dachuan Zhang, Dongmei Tianjin Univ Technol Coll Sci Inst Operat Res & Syst Engn Tianjin 300384 Peoples R China Hefei Univ Inst Appl Optimizat Dept Comp Sci & Technol Hefei Peoples R China Tech Univ Berlin Inst Math Combinatorial Optimizat & Graph Algorithms COGA G Berlin Germany Univ Sci & Technol Beijing Sch Math & Phys Beijing Peoples R China Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

ISBN: (数字)9789819723409

ISBN: (纸本)9789819723393;9789819723409

In this paper, we explore two robust models for the k-median and k-means problems: the outlier-version (k-MedO/k-MeaO) and the penalty-version (k-MedP/k-MeaP), enabling the marking and elimination of certain points as outliers. In k-MedO/k-MeaO, the count of outliers is restricted by a specified integer, while in k-MedP/k-MeaP, there's no explicit limit on outlier quantity, yet each outlier incurs a penalty cost. We introduce a novel approach to evaluate the approximation ratio of local search algorithms for these problems. This involves an adapted clustering method that captures pertinent information about outliers within both local and global optimal solutions. For k-MeaP, we enhance the best-known approximation ratio derived from local search, elevating it from 25 + epsilon to 9 + epsilon. The best-known approximation ratio for k-MedP is also obtained. Regarding k-MedO/k-MeaO, only two bi-criteria approximation algorithms based on local search exist. One violates the outlier constraint (limiting outlier count), while the other breaches the cardinality constraint (restricting the number of clusters). We focus on the former algorithm, enhancing its approximation ratios from 17+epsilon to 3+epsilon for k-MedO and from 274 + epsilon to 9 + epsilon for k-MeaO.

关键词： clustering problems Approximation algorithms Robust

来源：评论

学校读者我要写书评

暂无评论

A self-supervised learning model for graph clustering optimization problems

引用

KNOWLEDGE-BASED SYSTEMS 2024年 290卷

作者： Cai, Qingqiong Guo, Xingyue Huang, Shenwei Nankai Univ Coll Comp Sci Tianjin 300350 Peoples R China Nankai Univ Tianjin Key Lab Network & Data Secur Technol Tianjin 300350 Peoples R China

The graph clustering optimization problems are ubiquitous in both scientific and engineering fields, for example the graph partitioning problem and facility location problem. Since most of these problems are NP -hard, it is challenging to design effective algorithms for them. Recently, deep learning has achieved promising performances in solving combinatorial optimization problems. However, existing supervised learning -based methods are limited by the absence of labeled instances, while reinforcement learning -based methods tend to be hard to train and converge slowly for large instances. In this paper, we propose a self -supervised model named GCOM to address NP -hard graph clustering optimization problems. It adopts a pre -training and fine-tuning framework. In the pre -training process, we utilize graph contrastive learning to mine the latent clustering relations and useful optimization strategies, which can be generalized to the downstream tasks. Additionally, two effective graph encodings are introduced to enhance the expressive power of our model. We evaluate our model on facility location problem (FLP) and balanced graph partitioning (BGP). Extensive experiments conducted on both synthetic and real -world datasets validate superior performance, strong generalization ability and high sample -efficiency of our model.

关键词： Self-supervised pre-training Contrastive learning Combinatorial optimization clustering problems

来源：评论

学校读者我要写书评

暂无评论

Hybrid heuristics based on column generation with path-relinking for clustering problems

引用

EXPERT SYSTEMS WITH APPLICATIONS 2014年第11期41卷 5277-5284页

作者： de Oliveira, Rudinei Martins Nogueira Lorena, Luiz Antonio Chaves, Antonio Augusto Mauri, Geraldo Regis Natl Inst Space Res INPE BR-12227010 Sao Jose Dos Campos SP Brazil Univ Fed Sao Paulo UNIFESP BR-12231280 Sao Jose Dos Campos SP Brazil Fed Univ Espirito Santo UFES BR-29500000 Alegre ES Brazil

This paper examines hybrid heuristics for solving clustering problems. The clustering problem can be defined as the process of separating a set of objects into groups such that members of a group are similar to each other. The methods are based on the application of a column generation technique for solving p-medians problems. Five heuristics are derived directly from the column generation algorithm: a solution made feasible from the master problem, the column generation solution, a heuristic with path-relinking considering the initial columns of the column generation procedure, a solution of the master problem with path-relinking and the column generation process with path-relinking. Solutions are tested with the external measure CRand and the computational results compared to recent methods in literature. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Hybrid heuristics Column generation p-Median problems clustering problems

来源：评论

学校读者我要写书评

暂无评论

Constant-Factor Approximation Algorithms for Parity-Constrained Facility Location and k-Center

引用

ALGORITHMICA 2023年第7期85卷 1883-1911页

作者： Kim, Kangsan Shin, Yongho An, Hyung-Chan Devsisters Corp Seoul South Korea Yonsei Univ Dept Comp Sci Seoul South Korea

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement-odd, even, or unconstrained-of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse T-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. We also consider the parity-constrained k-center problem, the bottleneck optimization variant of parity-constrained facility location. We present the first constant-factor approximation algorithm also for this problem.

关键词： Facility location problems Approximation algorithms k-center Parity constraints clustering problems

来源：评论

学校读者我要写书评

暂无评论

Convergence analysis of two-step inertial Douglas-Rachford algorithm and application

引用

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2022年第2期68卷 953-977页

作者： Dixit, Avinash Sahu, D. R. Gautam, Pankaj Som, T. Indian Inst Technol BHU Dept Math Sci Varanasi Uttar Pradesh India Banaras Hindu Univ Inst Sci Dept Math Varanasi Uttar Pradesh India

Monotone inclusion problems are crucial to solve engineering problems and problems arising in different branches of science. In this paper, we propose a novel two-step inertial Douglas-Rachford algorithm to solve the monotone inclusion problem of the sum of two maximally monotone operators based on the normal S-iteration method (Sahu, D.R.: Applications of the S-iteration process to constrained minimization problems and split feasibility problems. Fixed Point Theory 12(1), 187-204 (2011)). We have studied the convergence behavior of the proposed algorithm. Based on the proposed method, we develop an inertial primal-dual algorithm to solve highly structured monotone inclusions containing the mixtures of linearly composed and parallel-sum type operators. Finally, we apply the proposed inertial primal-dual algorithm to solve a highly structured minimization problem. We also perform a numerical experiment to solve the generalized Heron problem and compare the performance of the proposed inertial primal-dual algorithm to already known algorithms.

关键词： Inertial splitting algorithm Normal S-iteration method Douglas-Rachford splitting method Composite minimization problems clustering problems

来源：评论

学校读者我要写书评

暂无评论

A Hybrid Between TOA and Levy Flight Trajectory for Solving Different Cluster problems

引用

INTERNATIONAL JOURNAL OF COGNITIVE INFORMATICS AND NATURAL INTELLIGENCE 2021年第4期15卷 1页

作者： Devarakonda, Nagaraju Saidala, Ravi Kumar Kamarajugadda, Raviteja VIT AP Univ Amaravati India Koneru Lakshmaiah Educ Fdn Vaddeswaram AP India LBR Coll Engn Mylavaram India

In data analysis applications for extraction of useful knowledge, clustering plays an important role. The major shortcoming of traditional clustering algorithms is exhibiting poor performance in solving complex data cluster problems. This research paper introduces a novel hybrid optimization technique-based clustering approach. This paper is designed with two main objectives: designing efficient function optimization algorithm and developing advanced data clustering approach. In achieving the first objective, the standard TOA is first enhanced by hybridizing with Levy flight trajectory and benchmarked on 23 functions. A new clustering approach is developed by conjoining k-means algorithm and Levy flight TOA. The numerical complexity of the proposed novel clustering approach was tested on 10 UCI clustering datasets and four web document cluster problems. Several simulation experiments were conducted and an analysis of the results was done. The obtained graphical and statistical analysis reveals that the proposed novel clustering approach yields better quality clusters.

关键词： clustering problems Computational Intelligence Nature-Inspired Metaheuristics TOA Levy Flight Trajectory NP-Hard problems Web Document Cluster problems

来源：评论

学校读者我要写书评

暂无评论

A memetic algorithm based on reformulation local search for minimum sum-of-squares clustering in networks

引用

INFORMATION SCIENCES 2020年 541卷 271-296页

作者： Zhou, Qing Benlic, Una Wu, Qinghua Huazhong Univ Sci & Technol Sch Management 1037 Luoyu Rd Wuhan Peoples R China SATALIA 40 High StIslington High St London N1 8XB England

The edge minimum sum-of-squares clustering problem (E-MSSC) aims at finding p prototypes such that the sum of squares of distances from a set of vertices to their closest prototype is minimized, where a prototype is either a vertex or an interior point of an edge. This paper proposes a highly effective memetic algorithm for E-MSSC that combines a dedicated crossover operator for solution generation with a reformulation local search for solution improvement. Reformulation local search is a recent algorithmic framework for continuous location problems that is based on an alternation between original (continuous) and discrete formulations of a given problem. Furthermore, the proposed algorithm uses a simple strategy for population updating, and a mutation operator to prevent from premature convergence. The computational results obtained on three sets of 132 benchmark instances show that the proposed algorithm competes very favorably with the existing state-of-the-art algorithms in terms of both solution quality and computational efficiency. We also analyze several essential components of the proposed algorithm to understand their contribution to the algorithm's performance. (C) 2020 Published by Elsevier Inc.

关键词： Heuristics clustering problems Memetic algorithm Reformulation local search

来源：评论

学校读者我要写书评

暂无评论

A Dynamic Genetic Algorithm for clustering problems

A Dynamic Genetic Algorithm for Clustering Problems

引用

2nd International Conference on Information Technology and Management Innovation (ICITMI 2013)

作者： Cao, Yongchun Shao, Yabin Tian, Shuangliang Cai, Zhengqi Northwest Univ Nationalities Sch Math & Comp Sci Lanzhou 730030 Peoples R China

ISBN: (纸本)9783037858646

Due to many of the clustering algorithms based on GAs suffer from degeneracy and are easy to fall in local optima, a novel dynamic genetic algorithm for clustering problems (DGA) is proposed. The algorithm adopted the variable length coding to represent individuals and processed the parallel crossover operation in the subpopulation with individuals of the same length, which allows the DGA algorithm clustering to explore the search space more effectively and can automatically obtain the proper number of clusters and the proper partition from a given data set;the algorithm used the dynamic crossover probability and adaptive mutation probability, which prevented the dynamic clustering algorithm from getting stuck at a local optimal solution. The clustering results in the experiments on three artificial data sets and two real-life data sets show that the DGA algorithm derives better performance and higher accuracy on clustering problems.

关键词： clustering problems genetic algorithm dynamic crossover adaptive mutation

来源：评论

学校读者我要写书评

暂无评论

A clustering method of asset cybersecurity classification

引用

IFAC-PapersOnLine 2019年第13期52卷 928-933页

作者： Promyslov, Vitaly G. Semenkov, Kirill V. Shumov, Alexander S. V.A. Trapeznikov Institute of Control Sciences Russian Academy of Science 65 Profsoyuznaya Moscow117997 Russia

A formal method for asset classifying by cyber security is provided. The problem is solved in the frame of a clustering problem. The data structure and content are specified. A classification algorithm for systems with arbitrary number of subsystems is provided. © 2019, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.

关键词： Formal methods Hierarchical clustering Hierarchical systems Security of data Arbitrary number Classification algorithm clustering clustering methods clustering problems Cyber security

来源：评论

学校读者我要写书评

暂无评论

A new grouping genetic algorithm for clustering problems

引用

EXPERT SYSTEMS WITH APPLICATIONS 2012年第10期39卷 9695-9703页

作者： Agustin-Blas, L. E. Salcedo-Sanz, S. Jimenez-Fernandez, S. Carro-Calvo, L. Del Ser, J. Portilla-Figueras, J. A. Univ Alcala Dept Signal Theory & Commun Madrid 28871 Spain Tecnalia Res & Innovat Bizkaia Spain

In this paper we present a novel grouping genetic algorithm for clustering problems. Though there have been different approaches that have analyzed the performance of several genetic and evolutionary algorithms in clustering, the grouping-based approach has not been, to our knowledge, tested in this problem yet. In this paper we fully describe the grouping genetic algorithm for clustering, starting with the proposed encoding, different modifications of crossover and mutation operators, and also the description of a local search and an island model included in the algorithm, to improve the algorithm's performance in the problem. We test the proposed grouping genetic algorithm in several experiments in synthetic and real data from public repositories, and compare its results with that of classical clustering approaches, such as K-means and DBSCAN algorithms, obtaining excellent results that confirm the goodness of the proposed grouping-based methodology. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Grouping genetic algorithms clustering problems Hybrid algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：