您的检索：
学者姓名：徐大川
精炼检索结果：
年份
成果类型
收录类型
来源
综合
曾用名
合作者
语言
清除所有精炼条件
引用：
复制并粘贴一种已设定好的引用格式，或利用其中一个链接导入到文献管理软件中。
| GB/T 7714 | Cai, Xingju , Li, Min , Wang, Guanghui et al. "Special Issue on Frontiers of Operations Research of YFORSC 2020" Preface [J]. | ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH , 2021 , 38 (05) . |
| MLA | Cai, Xingju et al. ""Special Issue on Frontiers of Operations Research of YFORSC 2020" Preface" . | ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 38 . 05 (2021) . |
| APA | Cai, Xingju , Li, Min , Wang, Guanghui , Xu, Dachuan . "Special Issue on Frontiers of Operations Research of YFORSC 2020" Preface . | ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH , 2021 , 38 (05) . |
| 导入链接 | NoteExpress RIS BibTex |
摘要 ：
Team formation plays an essential role in the labor market. In this paper, we propose two bicriteria algorithms to construct a balance between gain and cost in a team formation problem under the streaming model, subject to a cardinality constraint. We formulate the problem as maximizing the difference of a non-negative normalized monotone submodular function and a non-negative linear function. As an extension, we also consider the case where the first function is gamma-weakly submodular. Combining the greedy technique with the threshold method, we present bicriteria streaming algorithms and give detailed analysis for both of these models. Our analysis is competitive with that in Ene's work.
关键词 ：
Linear function Linear function Bicriteria Bicriteria Approximately submodular Approximately submodular Streaming algorithm Streaming algorithm
引用：
复制并粘贴一种已设定好的引用格式，或利用其中一个链接导入到文献管理软件中。
| GB/T 7714 | Wang, Yijing , Xu, Dachuan , Du, Donglei et al. Bicriteria streaming algorithms to balance gain and cost with cardinality constraint [J]. | JOURNAL OF COMBINATORIAL OPTIMIZATION , 2021 . |
| MLA | Wang, Yijing et al. "Bicriteria streaming algorithms to balance gain and cost with cardinality constraint" . | JOURNAL OF COMBINATORIAL OPTIMIZATION (2021) . |
| APA | Wang, Yijing , Xu, Dachuan , Du, Donglei , Jiang, Yanjun . Bicriteria streaming algorithms to balance gain and cost with cardinality constraint . | JOURNAL OF COMBINATORIAL OPTIMIZATION , 2021 . |
| 导入链接 | NoteExpress RIS BibTex |
摘要 ：
We study stable instances of the k-means problem with penalties in fixed-dimensional Euclidean space. An instance of the problem is called alpha-stable if this instance exists a sole optimal solution and the solution keeps unchanged when distances and penalty costs are scaled by a factor of no more than alpha. Stable instances of clustering problem have been used to explain why certain heuristic algorithms with poor theoretical guarantees perform quite well in practical. For any fixed epsilon > 0, we show that when using a common multi-swap local-search algorithm, a (1 + epsilon)-stable instance of the k-means problem with penalties in fixed-dimensional Euclidean space can be solved accurately in polynomial time.
关键词 ：
Local search Local search stable instance stable instance approximation algorithm approximation algorithm fixed-dimensional Euclidean space fixed-dimensional Euclidean space k-means k-means
引用：
复制并粘贴一种已设定好的引用格式，或利用其中一个链接导入到文献管理软件中。
| GB/T 7714 | Yuan, Fan , Xu, Dachuan , Du, Donglei et al. AN EXACT ALGORITHM FOR STABLE INSTANCES OF THE k-MEANS PROBLEM WITH PENALTIES IN FIXED-DIMENSIONAL EUCLIDEAN SPACE [J]. | JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION , 2021 . |
| MLA | Yuan, Fan et al. "AN EXACT ALGORITHM FOR STABLE INSTANCES OF THE k-MEANS PROBLEM WITH PENALTIES IN FIXED-DIMENSIONAL EUCLIDEAN SPACE" . | JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION (2021) . |
| APA | Yuan, Fan , Xu, Dachuan , Du, Donglei , Li, Min . AN EXACT ALGORITHM FOR STABLE INSTANCES OF THE k-MEANS PROBLEM WITH PENALTIES IN FIXED-DIMENSIONAL EUCLIDEAN SPACE . | JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION , 2021 . |
| 导入链接 | NoteExpress RIS BibTex |
摘要 ：
In this paper, we study the problem of maximizing a sequence submodular function in the streaming setting, where the utility function is defined on sequences instead of sets of elements. We encode the sequence submodular maximization with a weighted digraph, in which the weight of a vertex reveals the utility value in selecting a single element and the weight of an edge reveals the additional profit with respect to a certain selection sequence. The edges are visited in a streaming fashion and the aim is to sieve a sequence of at most k elements from the stream, such that the utility is maximized. In this work, we present an edge-based threshold procedure, which makes one pass over the stream, attains an approximation ratio of (1 / (2 Δ+ 1) - O()) , consumes O(kΔ/ ) memory source in total and O(log (kΔ) / ) update time per edge, where Δ is the minimum of the maximal outdegree and indegree of the directed graph. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.
关键词 ：
Directed graphs Directed graphs Combinatorial mathematics Combinatorial mathematics Mathematical techniques Mathematical techniques
引用：
复制并粘贴一种已设定好的引用格式，或利用其中一个链接导入到文献管理软件中。
| GB/T 7714 | Yang, Ruiqi , Xu, Dachuan , Guo, Longkun et al. Sequence submodular maximization meets streaming [J]. | Journal of Combinatorial Optimization , 2021 , 41 (1) : 43-55 . |
| MLA | Yang, Ruiqi et al. "Sequence submodular maximization meets streaming" . | Journal of Combinatorial Optimization 41 . 1 (2021) : 43-55 . |
| APA | Yang, Ruiqi , Xu, Dachuan , Guo, Longkun , Zhang, Dongmei . Sequence submodular maximization meets streaming . | Journal of Combinatorial Optimization , 2021 , 41 (1) , 43-55 . |
| 导入链接 | NoteExpress RIS BibTex |
摘要 ：
In this paper, we consider the Bregman k-means problem (BKM) which is a variant of the classical k-means problem. For an n-point set S and k <= n with respect to mu-similar Bregman divergence, the BKM problem aims first to find a center subset C subset of S with vertical bar C vertical bar= k and then separate S into k clusters according to C, such that the sum of mu-similarBregman divergence from each point in S to its nearest center is minimized. We propose a mu-similar BregMeans++ algorithm by employing the local search scheme, and prove that the algorithm deserves a constant approximation guarantee. Moreover, we extend our algorithm to solve a variant of BKM called noisy mu-similar Bregman k-means++ (noisy mu-BKM++) which is BKM in the noisy scenario. For the same instance and purpose as BKM, we consider the case of sampling a point with an imprecise probability by a factor between 1- epsilon(1) and 1+ epsilon(2) for epsilon(1) is an element of epsilon[0, 1) and epsilon(2) >= 0, and obtain an approximation ratio of O(log(2) k) in expectation.
关键词 ：
k-means k-means m-similar Bregman divergences m-similar Bregman divergences Local search Local search Seeding algorithm Seeding algorithm
引用：
复制并粘贴一种已设定好的引用格式，或利用其中一个链接导入到文献管理软件中。
| GB/T 7714 | Tian, Xiaoyun , Xu, Dachuan , Guo, Longkun et al. Improved local search algorithms for Bregman k-means and its variants [J]. | JOURNAL OF COMBINATORIAL OPTIMIZATION , 2021 . |
| MLA | Tian, Xiaoyun et al. "Improved local search algorithms for Bregman k-means and its variants" . | JOURNAL OF COMBINATORIAL OPTIMIZATION (2021) . |
| APA | Tian, Xiaoyun , Xu, Dachuan , Guo, Longkun , Wu, Dan . Improved local search algorithms for Bregman k-means and its variants . | JOURNAL OF COMBINATORIAL OPTIMIZATION , 2021 . |
| 导入链接 | NoteExpress RIS BibTex |
摘要 ：
We investigate the price of anarchy (PoA) in nonatomic congestion games when the total demand T gets very large. First results in this direction have recently been obtained by Colini-Baldeschi et al. (2016, 2017, 2020) for routing games and show that the PoA converges to one when the growth of the total demand T satisfies certain regularity conditions. We extend their results by developing a new framework for the limit analysis of the PoA that offers strong techniques such as the limit of games and applies to arbitrary growth patterns of T.We show that the PoA converges to one in the limit game regardless of the type of growth of T for a large class of cost functions that contains all polynomials and all regularly varying functions. For routing games with Bureau of Public Road (BPR) cost functions, we show in addition that socially optimal strategy profiles converge to equilibria in the limit game and that the PoA converges to one at a power law with exponent β, where β > 0 is the degree of the BPR functions. However, the precise convergence rate depends crucially on the the growth of T, which shows that a conjecture proposed by O'Hare et al. (2016) need not hold. Copyright: © 2021 INFORMS.
关键词 ：
Cost functions Cost functions Cost benefit analysis Cost benefit analysis
引用：
复制并粘贴一种已设定好的引用格式，或利用其中一个链接导入到文献管理软件中。
| GB/T 7714 | Wu, Zijun , Möhring, Rolf H. , Chen, Yanyan et al. Selfishness need not be bad [J]. | Operations Research , 2021 , 69 (2) : 410-435 . |
| MLA | Wu, Zijun et al. "Selfishness need not be bad" . | Operations Research 69 . 2 (2021) : 410-435 . |
| APA | Wu, Zijun , Möhring, Rolf H. , Chen, Yanyan , Xu, Dachuan . Selfishness need not be bad . | Operations Research , 2021 , 69 (2) , 410-435 . |
| 导入链接 | NoteExpress RIS BibTex |
摘要 ：
Submodular maximization is well studied in the fields of data mining and machine learning. We study the submodular maximization subject to a cardinality constraint k for large scale scenarios applications under two combined settings. One is that all elements arrive in a streaming fashion, and the other is that some elements may be invalid at last. For this problem, which is called streaming robust submodular maximization (SRSM) problem, we explore an approximation algorithm, returning a subset S from the ground set V with a limit size, such that it represents V and is robust to a broken set E well. Our algorithm only makes one pass over data, and achieves a constant-factor 0.1224 approximation guarantee, independent of the cardinality constraint parameter k. Based on the algorithm for SRSM problem, we continue to discuss this problem over sliding windows, in which we are asked to obtain a proper set that only considers the last W elements, and derive an algorithm with a constant (0.0612-epsilon)-approximation guarantee. At last we also propose numerical experiments on some applications to well demonstrate our algorithm for SRSM problem over sliding windows. (C) 2020 Elsevier B.V. All rights reserved.
关键词 ：
Performance guarantee Performance guarantee Sliding windows Sliding windows Streaming robust submodular maximization Streaming robust submodular maximization
引用：
复制并粘贴一种已设定好的引用格式，或利用其中一个链接导入到文献管理软件中。
| GB/T 7714 | Yang, Ruiqi , Xu, Dachuan , Cheng, Yukun et al. Streaming algorithms for robust submodular maximization [J]. | DISCRETE APPLIED MATHEMATICS , 2021 , 290 : 112-122 . |
| MLA | Yang, Ruiqi et al. "Streaming algorithms for robust submodular maximization" . | DISCRETE APPLIED MATHEMATICS 290 (2021) : 112-122 . |
| APA | Yang, Ruiqi , Xu, Dachuan , Cheng, Yukun , Wang, Yishui , Zhang, Dongmei . Streaming algorithms for robust submodular maximization . | DISCRETE APPLIED MATHEMATICS , 2021 , 290 , 112-122 . |
| 导入链接 | NoteExpress RIS BibTex |
引用：
复制并粘贴一种已设定好的引用格式，或利用其中一个链接导入到文献管理软件中。
| GB/T 7714 | Chen, Bo , Xu, Dachuan , Zhang, Guochuan . Preface "Advances in Combinatorial Optimization": Special Issue of Journal of Combinatorial Optimization [J]. | JOURNAL OF COMBINATORIAL OPTIMIZATION , 2021 . |
| MLA | Chen, Bo et al. "Preface "Advances in Combinatorial Optimization": Special Issue of Journal of Combinatorial Optimization" . | JOURNAL OF COMBINATORIAL OPTIMIZATION (2021) . |
| APA | Chen, Bo , Xu, Dachuan , Zhang, Guochuan . Preface "Advances in Combinatorial Optimization": Special Issue of Journal of Combinatorial Optimization . | JOURNAL OF COMBINATORIAL OPTIMIZATION , 2021 . |
| 导入链接 | NoteExpress RIS BibTex |
摘要 ：
In the paper, we consider the problem of maximizing the multilinear extension of a nonsubmodular set function subject to a k-cardinality constraint with adaptive rounds of evaluation queries. We devise an algorithm which achieves a ratio of ( 1- e-(gamma 2)- epsilon) and requires O (logn/epsilon(2)) adaptive rounds and O(logn/epsilon(2)) queries, where gamma is the continuous generic submodularity ratio that compares favorably in flexibility to the traditional submodularity ratio proposed by Das and Kempe. The key idea of our algorithm is originated from the parallel-greedy algorithm proposed by Chekuri et al., but incorporating with two major changes to retain the performance guarantee: First, identify all good coordinates with the continuous generic submodularity ratio and gradient values approximately as large as the best coordinate, and increase along all these coordinates uniformly; Second, increase xalong these coordinates by a dynamical increment whose value depends on gamma. The key difficulty of our algorithm is that when the function is nonsubmodular, the set of the best coordinate does not decrease during iterations; while provided submodularity, the decreasing can be ensured by the parallel-greedy algorithm. Our algorithms slightly compromise performance guarantee for the sake of extending to constrained nonsubmodular maximization with parallelism, provided that the state-of-art algorithm for the corresponding submodular version attains an approximation ratio of (1 - 1/e- epsilon) and requires O (logn/epsilon(2)) adaptive rounds. (C) 2021 Elsevier B.V. All rights reserved.
关键词 ：
Nonsubmodular Nonsubmodular Continuous generic submodularity ratio Continuous generic submodularity ratio Multilinear relaxation Multilinear relaxation Adaptive Adaptive
引用：
复制并粘贴一种已设定好的引用格式，或利用其中一个链接导入到文献管理软件中。
| GB/T 7714 | Zhang, Hongxiang , Xu, Dachuan , Guo, Longkun et al. Parallelized maximization of nonsubmodular function subject to a cardinality constraint [J]. | THEORETICAL COMPUTER SCIENCE , 2021 , 864 : 129-137 . |
| MLA | Zhang, Hongxiang et al. "Parallelized maximization of nonsubmodular function subject to a cardinality constraint" . | THEORETICAL COMPUTER SCIENCE 864 (2021) : 129-137 . |
| APA | Zhang, Hongxiang , Xu, Dachuan , Guo, Longkun , Tan, Jingjing . Parallelized maximization of nonsubmodular function subject to a cardinality constraint . | THEORETICAL COMPUTER SCIENCE , 2021 , 864 , 129-137 . |
| 导入链接 | NoteExpress RIS BibTex |
摘要 ：
In this paper, we study the prize-collecting k-Steiner tree problem (PC k-ST), which is an interesting generalization of both the k-Steiner tree problem (k-ST) and the prize-collecting Steiner tree problem (PCST). In the PC k-ST, we are given an undirected connected graph G= (V, E), a subset R⊆ V called terminals, a root vertex r∈ V and an integer k. Every edge has a non-negative edge cost and every vertex has a non-negative penalty cost. We wish to find an r-rooted tree F that spans at least k vertices in R so as to minimize the total edge costs of F as well as the penalty costs of the vertices not in F. As our main contribution, we propose two approximation algorithms for the PC k-ST with ratios of 5.9672 and 5. The first algorithm is based on an observation of the solutions for the k-ST and the PCST, and the second one is based on the technique of primal-dual. © 2021, Springer Nature Switzerland AG.
关键词 ：
Approximation algorithms Approximation algorithms Trees (mathematics) Trees (mathematics)
引用：
复制并粘贴一种已设定好的引用格式，或利用其中一个链接导入到文献管理软件中。
| GB/T 7714 | Han, Lu , Wang, Changjun , Xu, Dachuan et al. The Prize-Collecting k-Steiner Tree Problem [C] . 2021 : 371-378 . |
| MLA | Han, Lu et al. "The Prize-Collecting k-Steiner Tree Problem" . (2021) : 371-378 . |
| APA | Han, Lu , Wang, Changjun , Xu, Dachuan , Zhang, Dongmei . The Prize-Collecting k-Steiner Tree Problem . (2021) : 371-378 . |
| 导入链接 | NoteExpress RIS BibTex |
导出
| 数据： |
选中 到 |
| 格式： |
