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

Product Selection Problem: Improve Market Share by Learning Consumer Behavior

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2016年第4期10卷 34-34页

作者： Xu, Silei Lui, John C. S. Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

It is often crucial for manufacturers to decide what products to produce so that they can increase their market share in an increasingly fierce market. To decide which products to produce, manufacturers need to analyzethe consumers' requirements and how consumers make their purchase decisions so that the new products will be competitive in the market. In this paper, we first present a general distance-based product adoption model to capture consumers' purchase behavior. Using this model, various distance metrics can be used to describe different real life purchase behavior. We then provide a learning algorithm to decide which set of distance metrics one should use when we are given some accessible historical purchase data. Based on the product adoption model, we formalize the k most marketable products (or k-MMP) selection problem and formally prove that the problem is NP-hard. To tackle this problem, we propose an efficient greedy-based approximation algorithm with a provable solution guarantee. Using submodularity analysis, we prove that our approximation algorithm can achieve at least 63% of the optimal solution. We apply our algorithm on both synthetic datasets and real-world datasets (***), and show that our algorithm can easily achieve five or more orders of speedup over the exhaustive search and achieve about 96% of the optimal solution on average. Our experiments also demonstrate the robustness of our distance metric learning method, and illustrate how one can adopt it to improve the accuracy of product selection.

关键词： Product selection consumer behavior model learning submodular set function approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Streaming adaptive submodular maximization*

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期944卷

作者： Tang, Shaojie Yuan, Jing Univ Texas Dallas Naveen Jindal Sch Management Richardson TX 75080 USA Univ North Texas Dept Comp Sci & Engn Denton TX USA

Adaptive submodular maximization has been extensively studied in the literature. However, most of existing studies in this field focus on pool-based setting, where one is allowed to pick items in any order, and there have been few studies for the stream-based setting where items arrive in an arbitrary order and one must immediately decide whether to select an item or not upon its arrival. In this paper, we introduce a new class of utility functions, semi-policywise submodular functions. We develop a series of effective algorithms to maximize a semi-policywise submodular function under the stream-based setting.(c) 2022 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Adaptive submodularity Streaming setting

来源：评论

学校读者我要写书评

暂无评论

PLANAR GRAPH DECOMPOSITION AND ALL PAIRS SHORTEST PATHS

引用

JOURNAL OF THE ACM 1991年第1期38卷 162-204页

作者： FREDERICKSON, GN Purdue Univ. West Lafayette IN

An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. The algorithm runs in O(pn) time, where n is the number of vertices in G, and p is the minimum cardinality of a subset of the faces that cover all vertices, taken over all planar embeddings of G. The algorithm is based on a decomposition of the graph into O(pn) outerplanar subgraphs satisfying certain separator properties. Linear-time algorithms are presented for various subproblems including that of finding an appropriate embedding of G and a corresponding face-on-vertex covering of cardinality O(p), and of generating all pairs shortest path information in a directed outerplanar graph.

关键词： algorithmS THEORY ALL PAIRS SHORTEST PATHS approximation algorithm COMPACT ROUTING TABLE GRAPH EMBEDDING NP-COMPLETENESS OUTERPLANAR GRAPH PLANAR GRAPH SUCCINCT ENCODING

来源：评论

学校读者我要写书评

暂无评论

algorithmic results in Roman dominating functions on graphs

引用

INFORMATION PROCESSING LETTERS 2023年 182卷

作者： Poureidi, Abolfazl Fathali, Jafar Shahrood Univ Technol Fac Math Sci Shahrood Iran

Given a graph G = (V, E), a subset D subset of V (respectively, function f : V -> {0, 1, 2}) is a dominating set (DS) (respectively, Roman dominating function (RDF)) of G if each vertex v is an element of V\D (respectively, v is an element of V with f (v) = 0) is adjacent to a vertex u is an element of D (respectively, u is an element of V with f (u) = 2). The domination number of G is the minimum cardinality of an DS of G and the Roman domination number of G is the minimum weight of an RDF f of G, where the weight of f is Ev is an element of V f (v). The (Roman) domination problem is to compute the (Roman) domination number of a given graph. In this paper, we study the Roman domination problem. We show that the complexity of the problem differs from the complexity of the domination problem and the problem is NP-complete for circle graphs and undirected path graphs and is APX-complete for graphs of degree at most 4. We also propose an integer linear programming (ILP) formulation with polynomial number of constraints for the problem. Additionally, we use the ILP formulation to give an H(Delta(G) + 1)-approximation algorithm for solving the problem for any graph G, where Delta(G) is the maximum degree of G. Furthermore, we show that the optimization version of the problem on split and chordal graphs cannot be approximated in polynomial time within (1/2 - epsilon) ln | V | for any epsilon > 0, unless NP subset of DTIME (| V |O (log log | V |)).(c) 2023 Elsevier B.V. All rights reserved.

关键词： Roman dominating function approximation algorithm Integer linear program NP-complete APX-complete

来源：评论

学校读者我要写书评

暂无评论

Delay Optimization for Wireless Powered Mobile Edge Computing with Computation Offloading via Deep Learning

引用

APPLIED SCIENCES-BASEL 2024年第16期14卷 7190页

作者： Lei, Ming Fu, Zhe Yu, Bocheng Shaanxi Normal Univ Sch Comp Sci & Technol Xian 710119 Peoples R China Xi An Jiao Tong Univ Dept Comp Sci & Technol Xian 710049 Peoples R China AVIC Xian Aeronaut Comp Tech Res Inst Xian 710068 Peoples R China

Mobile edge computing (MEC), specifically wireless powered mobile edge computing (WPMEC), can achieve superior real-time data analysis and intelligent processing. In WPMEC, different user nodes (UNs) harvest significantly different amounts of energy, which results in longer delays for lower-energy UNs when data are offloaded to MEC servers. This study involves quantifying the delays in energy harvesting and task offloading to edge servers in WPMEC via user cooperation. In this paper, a method for transferring the tasks that need to be offloaded to edge servers as quickly as possible is investigated. The problem is formulated as an optimization model to minimize the delay, including the time required for the energy harvesting and offloading tasks. Because the problem was non-deterministic polynomial hard (NP-hard), a delay-optimal approximation algorithm (DOPA) is proposed. Finally, with the training data generated based on the DOPA, a deep learning-based online offloading (DLOO) framework is designed for predicting the transmission power of each UN. After each UN's transmission power is obtained, the original model is converted to a linear programming problem, which substantially reduces the computational complexity of the DOPA for solving the mixed-integer linear programming problem, especially in large-scale networks. The numerical results show that compared with the non-cooperation methods for WPMEC, the proposed algorithm significantly reduces the total delay. Additionally, in the delay optimization process for a scale of six UNs, the average computation time of the DLOO is only 0.2% that of the DOPA.

关键词： WPMEC user cooperation deep learning approximation algorithm delay optimization

来源：评论

学校读者我要写书评

暂无评论

A semidefinite relaxation approach for the offloading problem in edge computing

引用

COMPUTERS & ELECTRICAL ENGINEERING 2022年 98卷 107728-107728页

作者： Han, Xinxin Gao, Guichen Ning, Li Wang, Yang Zhang, Yong Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen Peoples R China Univ Chinese Acad Sci Beijing Peoples R China Guangxi Key Lab Cryptog & Informat Secur Guilin Peoples R China

In traditional cloud computing, tasks will be offloaded to the could, which often leads to high latency and low quality of service. To avoid this disadvantage, edge computing was introduced. The fundamental issue in edge computing is selecting some tasks to be computed in the edge, which is called the offloading problem. In most previous studies, the communication cost between any two tasks is often assumed to be symmetric in different sides and is often ignored within the same side. In this paper, we consider a heterogeneous offloading model, where the communication cost exists everywhere and is asymmetric. With the help of semidefinite relaxation, we give an algorithm for the offloading problem. If the Laplacian matrix with respect to the offloading problem is positive semidefinite, the theoretical guarantee can be proved to be 2/pi. The performance of the proposed algorithm is also evaluated via numerical analysis. The experimental results show that the algorithm is very effective.

关键词： Edge computing Offloading approximation algorithm Semidefinite relaxation Performance ratio

来源：评论

学校读者我要写书评

暂无评论

Facility Location with Hierarchical Facility Costs

引用

ACM TRANSACTIONS ON algorithmS 2010年第2期6卷 1–22页

作者： Svitkina, Zoya Tardos, Eva Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Cornell Univ Dept Comp Sci Ithaca NY 14853 USA

We introduce a facility location problem with submodular facility cost functions, and give an O(log n) approximation algorithm for it. Then we focus on a special case of submodular costs, called hierarchical facility costs, and give a (4.237 + epsilon)-approximation algorithm using local search. The hierarchical facility costs model multilevel service installation. Shmoys et al. [ 2004] gave a constant factor approximation algorithm for a two-level version of the problem. Here we consider a multilevel problem, and give a constant factor approximation algorithm, independent of the number of levels, for the case of identical costs on all facilities.

关键词： algorithms Theory approximation algorithm facility location local search sub-modular function

来源：评论

学校读者我要写书评

暂无评论

Drones Routing with Stochastic Demand

引用

DRONES 2023年第6期7卷 362-362页

作者： Yu, Nan Dong, Bin Qu, Yuben Zhang, Mingwei Wang, Yanyan Dai, Haipeng Yao, Changhua State Key Lab Air Traff Management Syst Nanjing 210007 Peoples R China Nanjing Univ Aeronaut & Astronaut Coll Elect & Informat Engn Nanjing 211106 Peoples R China Hohai Univ Coll Comp & Informat Nanjing 211100 Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210033 Peoples R China Nanjing Univ Informat Sci & Technol Sch Elect & Informat Engn Nanjing 210044 Peoples R China

Motivated by the increasing number of drones used for package delivery, we first study the problem of Multiple drOne collaborative Routing dEsign (MORE) in this article. That is, given a fixed number of drones and customers, determining the delivery trip for drones under capacity constraint with stochastic demand for customers such that the overall expected traveling cost is minimized. To address the MORE problem, we first prove that MORE falls into the realm of the classical vehicle routing problem with stochastic demand and then propose an effective algorithm for MORE. Next, we have a scheme of resplitting customers into different individual delivery trips while the stochastic demands are determined. Moreover, we consider a variety of MORE, MORE-TW, and design an effective algorithm to address it. We conduct simulation experiments for MORE to verify our theoretical findings. The results show that our algorithm outperforms other comparison algorithms by at least 79.60%.

关键词： stochastic demands capacity constraint drone delivery approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Deterministic PTAS for the Commutative Rank of Matrix Spaces

引用

THEORY OF COMPUTING 2018年第3期14卷 1-21页

作者： Blaeser, Markus Jindal, Gorav Pandey, Anurag Saarland Univ Dept Comp Sci Saarland Informat Campus Saarbrucken Germany Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany Saarbrucken Grad Sch Comp Sci Saarland Informat Campus Saarbrucken Germany

We consider the problem of computing the commutative rank of a given matrix space B subset of F-nxn, that is, given a basis of B, find a matrix of maximum rank in B. This problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is n, subsumes problems such as testing perfect matching in graphs and identity testing of algebraic branching programs. Finding an efficient deterministic algorithm for the commutative rank is a major open problem, although there is a simple and efficient randomized algorithm for it. Recently, there has been a series of results on computing the non-commutative rank of matrix spaces in deterministic polynomial time. Since the non-commutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic 1/2-approximation algorithm for the commutative rank It is a natural question whether this approximation ratio can be improved. In this paper, we answer this question affirmatively. We present a deterministic polynomial-time approximation scheme (PTAS) for computing the commutative rank of a given matrix space. More specifically, given a matrix space B subset of F-nxn and a rational number epsilon > 0, we give an algorithm that runs in time O(n(4+3/epsilon)) and computes a matrix A is an element of B such that the rank of A is at least (1 - epsilon) times the commutative rank of B. The algorithm is the natural greedy algorithm. It always takes the first set of k matrices that will increase the rank of the matrix constructed so far until it does not find any improvement, where the size k of the set depends on epsilon.

关键词： approximation algorithm algebraic complexity commutative rank matrix spaces PTAS Wong sequences

来源：评论

学校读者我要写书评

暂无评论

Three-Stage Assembly Flow Shop Scheduling Problem with a Fixed Maintenance Period

引用

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

作者： Yuan, Yuan Han, Xin Zhou, Yong Liu, Xingwu Dalian Minzu Univ Sch Informat & Commun Engn Dalian 116600 Peoples R China Dalian Univ Technol Sch Software Technol Dalian 116620 Peoples R China Dalian Univ Technol Sch Math Sci Dalian 116620 Peoples R China

This paper investigates the three-stage assembly flow shop scheduling problem, provided that there is a fixed maintenance period (MP) imposed on one of the machines in the first stage, the objective is to minimize the makespan. The starting time and duration of MP are known in advance, during MP no job can be processed on the corresponding machine. Only the non-resumable scenario is considered, i.e., if a job fails to finish before MP, it must restart from the beginning after the machine becomes available again, rather than continuing its processing. The problem generalizes the three-stage assembly flow shop scheduling problem without MPs and is therefore strongly NP-hard. To the best of our knowledge, the problem has not been explored so far. We propose three approximation algorithms for the problem.

关键词： Scheduling assembly flow shop maintenance period approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：