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

On solving simplified diversified top-k s-plex problem

COMPUTERS & OPERATIONS RESEARCH 2023年第1期153卷

作者： Wu, Jun Li, Chu-Min Wang, Luzhi Hu, Shuli Zhao, Peng Yin, Minghao Nanjing Univ Informat Sci & Technol Sch Comp Sci Nanjing Peoples R China Univ Picardie MIS Jules Verne France Tianjin Univ Coll Intelligence & Comp Tianjin Peoples R China Northeast Normal Univ Informat Sci & Technol Changchun Peoples R China Northeast Normal Univ Key Lab Appl Stat MOE Changchun Peoples R China Northeast Normal Univ Key Lab Appl Stat Informat Sci & Technol MOE 5268 Renmin St Changchun 130024 Jilin Peoples R China

Finding cohesive groups in a graph, which has been extensively studied by many researchers, is a fundamental and critical problem for various real-world applications, such as community search, motif discovery and anomaly detection. Unfortunately, the cohesive groups rarely appear as cliques and are usually highly overlapping, so few cohesive groups can be found by searching maximum or top-k maximal cliques. In other words, maximum or top-k maximal cliques are too strict for representing cohesive groups. To handle this problem, the DTKSP problem was introduced earlier in the literature to find k maximal s-plexes that cover maximum vertices with the lowest overlapping in a given graph. In this paper, we consider the Simplified Diversified Top-k s-Plex (S-DTKSP) problem, by aiming to find k maximal s-plexes that cover the maximum vertices without considering the size of overlap. We prove that the S-DTKSP problem is NP-hard and propose an integer linear programming for S-DTKSP problem. Then, we propose an iterated local search (ILS) algorithm with a tabu strategy to efficiently find a good solution. The proposed algorithms are evaluated on large real -world instances. The experimental results demonstrate that our approaches can solve the S-DTKSP problem effectively and efficiently than two baseline algorithms.

关键词： approximation algorithm Iterated local search Tabu search Scoring function S-DTKSP problem

来源：评论

学校读者我要写书评

暂无评论

A constant-factor approximation algorithm for multi-vehicle collection for processing problem

引用

OPTIMIZATION LETTERS 2013年第7期7卷 1627-1642页

作者： Yucel, E. Salman, F. S. Ormeci, E. L. Gel, E. S. Koc Univ Coll Engn Istanbul Turkey Arizona State Univ Sch Comp Informat & Decis Syst Engn Tempe AZ USA

We define the multiple-vehicle collection for processing problem (mCfPP) as a vehicle routing and scheduling problem in which items that accumulate at customer sites over time should be transferred by a series of tours to a processing facility. We show that this problem with the makespan objective (mCfPP()) is NP-hard using an approximation preserving reduction from a two-stage, hybrid flowshop scheduling problem. We develop a polynomial-time, constant-factor approximation algorithm to solve mCfPP(). The problem with a single site is analyzed as a special case with two purposes. First, we identify the minimum number of vehicles required to achieve a lower bound on the makespan, and second, we characterize the optimal makespan when a single vehicle is utilized.

关键词： approximation algorithm Vehicle routing and scheduling Makespan Collection

来源：评论

学校读者我要写书评

暂无评论

New bounds on the anti-Ramsey numbers of star graphs via maximum edge q-coloring

引用

DISCRETE MATHEMATICS 2024年第4期347卷

作者： Chandran, L. Sunil Hashim, Talha Jacob, Dalu Mathew, Rogers Rajendraprasad, Deepak Singh, Nitin Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 India Indian Inst Technol Dept Comp Sci & Engn Hyderabad 502285 India Indian Inst Technol Dept Comp Sci & Engn Palakkad 678557 India IBM Res Lab Manyata Embassy Business Pk Bangalore 560045 India Univ Haifa Haifa Israel Max Planck Inst Informat Saarbrucken Germany

The anti -Ramsey number ar(G, H) with input graph G and pattern graph H, is the maximum positive integer k such that there exists an edge coloring of G using k colors, in which there are no rainbow subgraphs isomorphic to H in G. (H is rainbow if all its edges get distinct colors). The concept of anti -Ramsey number was introduced by Erdos et al. in 1973. Thereafter, several researchers investigated this concept in the combinatorial setting. Recently, Feng et al. revisited the anti -Ramsey problem for the pattern graph K-1,K-t (for t >= 3) purely from an algorithmic point of view. For a graph G and an integer q >= 2, an edge q -coloring of G is an assignment of colors to edges of G, such that the edges incident on a vertex span at most q distinct colors. The maximum edge q -coloring problem seeks to maximize the number of colors in an edge q -coloring of the graph G. Note that the optimum value of the edge q -coloring problem of G equals ar(G, K-1,K-q+1). Here, we study ar(G, K-1,K-t), the anti -Ramsey number of stars, for each fixed integer t >= 3, both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for ar(G, K-1,K-q+1), in terms of number of vertices and the minimum degree of G. The second one improves this result for the case of triangle -free input graphs. Our third main result presents an upper bound for ar(G, K-1,K-q+1) in terms of |E(G(<=(q-1)))|, which is a frequently used lower bound for ar(G, K-1,K-q+1) and maximum edge q -coloring in the literature. All our results have algorithmic consequences. (c) 2024 Elsevier B.V. All rights reserved.

关键词： Anti -Ramsey number Maximum edge q -coloring problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Effective Heuristic Techniques for Combined Robust Clustering Problem

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2023年第1期40卷

作者： Xu, Yunhe Wu, Chenchen Gai, Ling Han, Lu Tianjin Univ Technol Inst Operat Res & Syst Engn Coll Sci 391 Binshui Xi Rd Tianjin 300384 Peoples R China Donghua Univ Glorious Sun Sch Business & Management Shanghai 200051 Peoples R China Beijing Univ Posts & Telecommun Sch Sci Beijing 100876 Peoples R China

Clustering is one of the most important problems in the fields of data mining, machine learning, and biological population division, etc. Moreover, robust variant for k-means problem, which includes k-means with penalties and k-means with outliers, is also an active research branch. Most of these problems are NP-hard even the most classical problem, k-means problem. For the NP-hard problems, the heuristic algorithm is a powerful method. When the quality of the output can be guaranteed, the algorithm is called an approximation algorithm. In this paper, combining two types of robust settings, we consider k-means problem with penalties and outliers (k-MPO). In the k-MPO, we are given an n-point set U subset of R-d, a penalty cost pv >= 0 for each v is an element of U, an integer k <= n, and an integer z <= n. The target is to find a center subset S subset of R-d with vertical bar S vertical bar <= k, a penalty subset P subset of U and an outlier subset Z subset of U with vertical bar Z vertical bar <= z, such that the sum of the total costs, including the connection cost and the penalty cost, is minimized. We offer an approximation algorithm using a heuristic local search scheme. Based on a single-swap manipulation, we obtain 274-approximation algorithm.

关键词： Robust clustering problem k-means local search scheme approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Group sweep coverage with guaranteed approximation ratio

引用

THEORETICAL COMPUTER SCIENCE 2020年 836卷 1-15页

作者： Liu, Chuang Du, Hongwei Ye, Qiang Xu, Wen Harbin Inst Technol Shenzhen Dept Comp Sci & Technol Shenzhen Peoples R China Dalhousie Univ Comp Sci Halifax NS Canada Texas Womans Univ Dept Math & Comp Sci Denton TX 76204 USA

Wireless Sensor Networks (WSNs) are often deployed to monitor a region of interest. With sweep coverage, mobile sensor nodes are scheduled to move along a planned route (i.e. sweep route) in order to collect the data from a series of Point of Interests (POIs) sequentially. In this paper, we generalize the sweep coverage problem by proposing a new coverage paradigm, group sweep coverage. With group sweep coverage, the POIs are divided into several groups. A group is said to be covered when one of the POIs in the group is covered. The goal in group sweep coverage is to construct a sweep route that mobile sensor nodes should follow in order to cover all groups during each predefined period. In our research, we devised two algorithms for group sweep coverage: AGSC and DSRM. AGSC is a centralized scheme whose approximation ratio is 5A. Namely, the length of the sweep route generated by AGSC is at most 5A times that of the optimal sweep route. DSRM is a distributed scheme for large-scale networks with dynamic POIs. Compared with AGSC, DSRM leads to the same approximation ratio and better scalability. Our experimental results indicate that both AGSC and DSRM outperform the state-of-the-art schemes in terms of average and maximal sweep route length. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Sweep coverage approximation algorithm Wireless Sensor Networks Sweep route

来源：评论

学校读者我要写书评

暂无评论

An Eight-approximation algorithm for Computing Rooted Three-Vertex Connected Minimum Steiner Networks

引用

IEEE TRANSACTIONS ON COMPUTERS 2013年第9期62卷 1684-1693页

作者： Shen, Hong Guo, Longkun Sun Yat Sen Univ Sch Informat Sci & Technol Guangzhou Guangdong Peoples R China Univ Adelaide Sch Comp Sci Adelaide SA 5005 Australia Fuzhou Univ Sch Math & Comp Sci Fuzhou 350108 Fujian Peoples R China

For a given undirected (edge) weighted graph G = (V, E), a terminal set S subset of V and a root r is an element of S, the rooted k-vertex connected minimum Steiner network (kVSMN(r)) problem requires to construct a minimum-cost subgraph of G such that each terminal in S \ {r} is k-vertex connected to r. As an important problem in survivable network design, the kVSMNr problem is known to be NP-hard even when k = 1 [14]. For k = 3 this paper presents a simple combinatorial eight-approximation algorithm, improving the known best ratio 14 of Nutov [20]. Our algorithm constructs an approximate 3VSMNr through augmenting a two-vertex connected counterpart with additional edges of bounded cost to the optimal. We prove that the total cost of the added edges is at most six times of the optimal by showing that the edges in a 3VSMNr compose a subgraph containing our solution in such a way that each edge appears in the subgraph at most six times.

关键词： Rooted three-vertex connectivity survivable network design Steiner minimum network approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A new three-machine shop scheduling: complexity and approximation algorithm

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2013年第4期26卷 799-810页

作者： Dong, Jianming Chen, Yong Zhang, An Yang, Qifan Zhejiang Univ Dept Math Hangzhou 310027 Zhejiang Peoples R China Hangzhou Dianzi Univ Inst Operat Res & Cybernet Hangzhou 310018 Zhejiang Peoples R China

The paper investigates a new three-machine shop scheduling problem that arises from many production systems, such as the garment assembly line, etc. In such scenarios, each job consists of three operations, each of which has to be non-preemptively processed by one specific machine. In contrast with the classical three-machine shop scheduling, the processing order of the operations of each job is partially restricted. In particular, the first two operations are ordered and all the same for all jobs, while the third operation is not restricted. The objective is to minimize the makespan. We show the problem is NP-hard in the ordinary sense and present a polynomial time approximation algorithm with a worst case performance ratio of 3/2.

关键词： Open shop Flow shop approximation algorithm Worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

A Fast Hybrid ε-approximation algorithm for Computing Constrained Shortest Paths

引用

IEEE COMMUNICATIONS LETTERS 2013年第7期17卷 1471-1474页

作者： Feng, Gang Korkmaz, Turgay Univ Wisconsin Dept Elect Engn Platteville WI 53818 USA Univ Texas San Antonio Dept Comp Sci San Antonio TX USA

Considerable efforts have been dedicated to develop both heuristic and approximation algorithms for the NP-complete delay-constrained least-cost (DCLC) routing problem, but to the best of our knowledge, no prior work has been done to mingle the two tracks of research. In this letter we introduce a novel idea to show how a heuristic method can be used to boost the average performance of an approximation algorithm. Simulations on networks of up to 8192 nodes demonstrate that our new hybrid epsilon-approximation algorithm is faster than the best known approximation algorithm by one or two orders of magnitude ( depending on the network size and epsilon).

关键词： Delay-constrained least cost routing multi-constrained path approximation algorithm heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties

引用

THEORETICAL COMPUTER SCIENCE 2013年 476卷 109-117页

作者： Li, Yu Du, Donglei Xiu, Naihua Xu, Dachuan Beijing Jiaotong Univ Sch Sci Dept Math Beijing 100044 Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB E3B 5A3 Canada Beijing Univ Technol Dept Appl Math Beijing 100124 Peoples R China

We offer the currently best approximation ratio 2.375 for the facility location problem with submodular penalties (FLPSP), improving not only the previous best combinatorial ratio 3, but also the previous best non-combinatorial ratio 2.488. We achieve this improved ratio by combining the primal-dual scheme with the greedy augmentation technique. (C) 2012 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Facility location problem Linear programming Submodular function

来源：评论

学校读者我要写书评

暂无评论

Scheduling double-track gantry cranes to minimize the overall loading/unloading time

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2023年第5期40卷 2340021-2340021页

作者： Wang, Jie Chen, Guangting Xuan, Xinle Zhang, An Chen, Yong Wang, Yuehuan Zhang, Hecheng Taizhou Univ Sch Elect & Informat Engn Linhai 317000 Peoples R China Zhejiang Univ Water Resources & Elect Power Hangzhou 310018 Zhejiang Peoples R China Hangzhou Dianzi Univ Dept Math Hangzhou 310018 Peoples R China Zhejiang Gongshang Univ Sch Stat & Math Hangzhou 310018 Peoples R China

In this paper, we consider the gantry crane scheduling problem at a single storage block where a total of m gantry cranes are mounted on double tracks so that cranes on different tracks can pass each other while those on the same track cannot. Containers at the storage block are divided into bays and each bay of containers has to be loaded/unloaded together due to the same shipping destination or the same customer. To minimize the overall loading/unloading time of containers, we first formulate the problem to a mixed integer linear programming (MILP) model, and compute the optimal solutions of small instances by the Gurobi solver. Then we design several heuristic algorithms and test their efficiency and performance by a series of large instances. In particular, we present a polynomial time approximation algorithm for the case where all but one gantry crane is mounted on the same track. We show that the algorithm has a worst case ratio of 2 - 2 m, outperforming the partition-based algorithms in the single-track scenario.

关键词： Gantry cranes non-crossing constraint MILP model approximation algorithm worst case analysis computational experiments

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：