检索结果-南通市图书馆

A COST-SHARING METHOD FOR AN UNCAPACITATED FACILITY LOCATION GAME WITH PENALTIES

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Journal of Systems Science & Complexity 2012年第2期25卷 287-292页

作者： Zhen WANG dachuan xu Department of Applied Mathematics Beijing University of Technology

This paper considers a variant of the classical facility location game called the uncapacitared facility location game with penalties （UFLGWP）. Unlike the standard UFLG, each client in the UFLGWP is either assigned to an open facility or rejected by paying a penalty. The authors propose a 3-approximate cross-monotonic cost-sharing method for the UFLGWP.

关键词： Cost-sharing method cross-monotonicity facility location game.

Approximation Algorithms for the Priority Facility Location Problem with Penalties

在线全文

学校读者我要写书评

暂无评论

Journal of Systems Science & Complexity 2015年第5期28卷 1102-1114页

作者： WANG Fengmin xu dachuan WU Chenchen College of Applied Sciences Beijing University of Technology College of Science Tianjin University of Technology

This paper considers the priority facility location problem with penalties. The authors develop a primal-dual 3-approximation algorithm for this problem. Combining with the greedy augmentation procedure, the authors f... 详细信息

关键词： Approximation algorithm facility location problem greedy augmentation primal-dual

Algorithms for the Prize-Collecting k-Steiner Tree Problem

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Tsinghua Science and Technology 2022年第5期27卷 785-792页

作者： Lu Han Changjun Wang dachuan xu Dongmei Zhang School of Science Beijing University of Posts and TelecommunicationsBeijing 100876China Academy of Mathematics and Systems Science Chinese Academy of SciencesBeijing 100190China Beijing Institute for Scientific and Engineering Computing Beijing University of TechnologyBeijing 100124China School of Computer Science and Technology Shandong Jianzhu UniversityJinan 250101China

In this paper,we study the prize-collecting k-Steiner tree(PCkST) *** are given a graph G=(V,E) and an integer *** graph is connected and undirected.A vertex r ∈ V called root and a subset R?V called terminals are also given.A feasible solution for the PCkST is a tree F rooted at r and connecting at least k vertices in *** a vertex from the tree incurs a penalty cost,and including an edge in the tree incurs an edge *** wish to find a feasible solution with minimum total *** total cost of a tree F is the sum of the edge costs of the edges in F and the penalty costs of the vertices not in *** present a simple approximation algorithm with the ratio of 5.9672 for the *** algorithm uses the approximation algorithms for the prize-collecting Steiner tree(PCST) problem and the k-Steiner tree(kST) problem as *** we propose a primal-dual based approximation algorithm and improve the approximation ratio to 5.

关键词： prize-collecting Steiner tree approximation algorithm

Regularized two-stage submodular maximization under streaming

在线全文

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2022年第4期65卷 102-111页

作者： Ruiqi YANG dachuan xu Longkun GUO Dongmei ZHANG Beijing Institute for Scientific and Engineering Computing Beijing University of Technology School of Mathematical Sciences University of Chinese Academy Sciences School of Computer Science and Technology Qilu University of Technology School of Computer Science and Technology Shandong Jianzhu University

In the problem of maximizing regularized two-stage submodular functions in streams, we assemble a family ■ of m functions each of which is submodular and is visited in a streaming style that an element is visited for only once. The aim is to choose a subset S of size at most ■ from the element stream ■, so as to maximize the average maximum value of these functions restricted on S with a regularized modular term. The problem can be formally cast as ■, where c:■ is a non-negative modular function and ■ is a non-negative monotone non-decreasing submodular function. The well-studied regularized problem of ■ is exactly a special case of the above regularized two-stage submodular maximization by setting m=1 and ■=k. Although f(·)-c(·) is submodular, it is potentially negative and non-monotone and admits no constant multiplicative factor approximation. Therefore, we adopt a slightly weaker notion of approximation which constructs S such that f(S)-c(S)≥ρ·f(O)-c(O) holds against optimum solution O for some ρ∈(0, 1). Eventually, we devise a streaming algorithm by employing the distorted threshold technique, achieving a weaker approximation ratio with ρ=0.2996 for the discussed regularized two-stage model.

关键词： submodular maximization streaming model two-stage threshold technique approximation algorithms

An Approximation Algorithm for the Risk-Adjusted Two-Stage Stochastic Facility Location Problem with Penalties

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2013年第3期1卷 339-346页

作者： Jiating Shao dachuan xu Department of Applied Mathematics Beijing University of Technology100 PingleyuanChaoyang DistrictBeijing 100124P.R.China

In this paper,we consider the risk-adjusted two-stage stochastic facility location problem with penalties(RSFLPP).Using the monotonicity and positive homogeneity of the risk measure function,we present an LP-roundin... 详细信息

关键词： Facility location Approximation algorithm LP-rounding Risk-adjusted

Approximation Algorithm for the Balanced 2-Correlation Clustering Problem

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Tsinghua Science and Technology 2022年第5期27卷 777-784页

作者： Sai Ji dachuan xu Donglei Du Ling Gai Zhongrui Zhao Department of Operations Research and Information Engineering Beijing University of TechnologyBeijing 100124China Beijing Institute for Scientific and Engineering Computing Beijing University of TechnologyBeijing 100124China Faculty of Business Administration University of New BrunswickFrederictonNB E3B 5A3Canada Glorious Sun School of Business and Management Donghua UniversityShanghai 200051China

The Correlation Clustering Problem(CorCP) is a significant clustering problem based on the similarity of *** has significant applications in different fields,such as machine learning,biology,and data mining,and many different problems in other *** this paper,the Balanced 2-CorCP(B2-CorCP) is introduced and examined,and a new interesting variant of the CorCP is *** goal of this clustering problem is to partition the vertex set into two clusters with equal size,such that the number of disagreements is *** first present a polynomial time algorithm for the B2-CorCP on M-positive edge dominant graphs(M≥ 3).Then,we provide a series of numerical experiments,and the results show the effectiveness of our algorithm.

关键词： balanced clustering k-correlation clustering positive edge dominant graphs approximation algorithm

An approximation algorithm for the k-median warehouse-retailer network design problem

在线全文

学校读者我要写书评

暂无评论

Science China Mathematics 2013年第11期56卷 2381-2388页

作者： LI Yu XIU NaiHua xu dachuan Department of Mathematics Beijing Jiaotong University Department of Applied Mathematics Beijing University of Technology

We study the generalizedk-median version of the warehouse-retailer network design problem(kWRND).We formulate the k-WRND as a binary integer program and propose a 6-approximation randomized algorithm based on Lagrangi... 详细信息

关键词： approximation algorithm warehouse-retailer network design problem k-median

An Approximation Algorithm for the Stochastic Fault-Tolerant Facility Location Problem

在线全文

学校读者我要写书评

暂无评论

Journal of the Operations Research Society of China 2013年第4期1卷 511-522页

作者： Chenchen Wu dachuan xu Jia Shu School of Mathematical Sciences Nankai UniversityTianjing 300071P.R.China Department of Applied Mathematics Beijing University of Technology100 PingleyuanChaoyang DistrictBeijing 100124P.R.China Department of Management Science and Engineering School of Economics and ManagementSoutheast UniversityNanjing 211189P.R.China

In this paper,we study a stochastic version of the fault-tolerant facility location *** exploiting the stochastic structure,we propose a 5-approximation algorithm which uses the LP-rounding technique based on the revised optimal solution to the linear programming relaxation of the stochastic fault-tolerant facility location problem.

关键词： Facility location problem Approximation algorithm LP rounding

A cost-sharing method for the multi-level economic lot-sizing game

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2014年第1期57卷 259-267页

作者： LI GaiDi DU DongLei xu dachuan ZHANG RuYao Department of Applied Mathematics Beijing University of Technology Faculty of Business Administration University of New BrunswickFredericton School of Mathematical Sciences Fudan University

Multi-level economic lot-sizing models have been extensively investigated under diferent multi-level structure *** this paper,we consider the cooperative game associated with the multi-level economic lot-sizing *** present a cost-sharing method for the multi-level economic lot-sizing game,under a mild condition,which is cross-monotonic,competitive,and approximate cost recovery.

关键词： multi-level economic lot-sizing game cross-monotonic competitive approximate cost recovery