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

approximations for Throughput Maximization

algorithmICA 2024年第5期86卷 1545-1577页

作者： Hyatt-Denesik, Dylan Rahgoshay, Mirmahdi Salavatipour, Mohammad R. Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada Univ Alberta Dept Comp Sci Edmonton AB Canada Eindhoven Univ Technol Eindhoven Netherlands

In this paper we study the classical problem of throughput maximization. In thisproblem we have a collectionJofnjobs, each having a release timerj, deadlinedj,and processing timepj. They have to be scheduled non-preemptively onmidenticalparallel machines. The goal is to find a schedule which maximizes the number of jobsscheduled entirely in their[rj,dj]window. This problem has been studied extensively(even for the case ofm=1). Several special cases of the problem remain open. Bar-Noy et al. (Proceedings of the Thirty-First Annual ACM Symposium on Theory ofComputing, May 1-4, 1999, Atlanta, Georgia, USA, pp. 622-631. ACM, 1999,https://***/10.1145/301250.301420) presented an algorithm with ratio 1-1/(1+1/m)mformmachines, which approaches 1-1/easmincreases. Form=1, Chuzhoy et al.(42nd Annual Symposium on Foundations of Computer Science (FOCS) 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pp. 348-356. IEEE Computer Society,2001) presented an algorithm with approximation with ratio 1-1e-epsilon(for any epsilon>0). Recently Im et al. (SIAM J Discrete Math 34(3):1649-1669, 2020) presented analgorithm with ratio 1-1/e+epsilon 0for some absolute constant epsilon 0>0 for any fixedm. They also presented an algorithm with ratio 1-O(root logm/m)-epsilon for generalmwhich approaches 1 asmgrows. The approximability of the problem form=O(1)remains a major open question. Even for the case ofm=1 andc=O(1)distincprocessing times the problem is open (Sgall in: algorithms - ESA 2012 - 20th AnnualEuropean Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, pp2-11, 2012). In this paper we study the case ofm=O(1)and show that if therearecdistinct processing times, ***'s come from a set of sizec, then there is arandomized(1-epsilon)-approximation that runs in timeO(nmc7 epsilon-6logT), whereTisthe largest deadline. Therefore, for constantmand constantcthis yields a PTAS. Ouralgorithm is based on proving structural properties for a near optimum solution thatallows

关键词： approximation algorithm Scheduling Throughput Maximization approximation Scheme

来源：评论

学校读者我要写书评

暂无评论

Online non-monotone diminishing return submodular maximization in the bandit setting

引用

JOURNAL OF GLOBAL OPTIMIZATION 2024年第3期90卷 619-649页

作者： Ju, Jiachen Wang, Xiao Xu, Dachuan Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Peng Cheng Lab Shenzhen 518066 Peoples R China

In this paper, we study online diminishing return submodular (DR-submodular for short) maximization in the bandit setting. Our focus is on problems where the reward functions can be non-monotone, and the constraint set is a general convex set. We first present the Single-sampling Non-monotone Frank-Wolfe algorithm. This algorithm only requires a single call to each reward function, and it computes the stochastic gradient to make it suitable for large-scale settings where full gradient information might not be available. We provide an analysis of the approximation ratio and regret bound of the proposed algorithm. We then propose the Bandit Online Non-monotone Frank-Wolfe algorithm to adjust for problems in the bandit setting, where each reward function returns the function value at a single point. We take advantage of smoothing approximations to reward functions to tackle the challenges posed by the bandit setting. Under mild assumptions, our proposed algorithm can reach 14(1-minx is an element of P '& Vert;x & Vert;infinity)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\fracapproximation{4} (1- \min _{x\in {\mathcal {P}}'}\Vert x\Vert _\infty )$$\end{document}-approximation with regret bounded by O(T5min{1,gamma}+56min{1,gamma}+5)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O (T<^>{\frac{5 \min \{1, \gamma \}+5 }{6 \min \{1, \gamma \}+5}})$$\end{document}, where the positive parameter gamma\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}

关键词： approximation algorithm Bandit setting DR submodular maximization Non-monotone function Regret bound

来源：评论

学校读者我要写书评

暂无评论

Mobility-Aware Utility Maximization in Digital Twin-Enabled Serverless Edge Computing

引用

IEEE TRANSACTIONS ON COMPUTERS 2024年第7期73卷 1837-1851页

作者： Li, Jing Guo, Song Liang, Weifa Wang, Jianping Chen, Quan Xu, Wenchao Wei, Kang Jia, Xiaohua City Univ Hong Kong Dept Comp Sci Hong Kong 999077 Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong 999077 Peoples R China Hong Kong Polytech Univ Dept Comp Hong Kong 999077 Peoples R China Guangdong Univ Technol Sch Comp Guangzhou 510006 Peoples R China

Driven by data and models, the digital twin technique presents a new concept of optimizing system design, process monitoring, decision-making and more, through performing comprehensive virtual-reality interaction and continuous mapping. By introducing serverless computing to Mobile Edge Computing (MEC) environments, the emerging serverless edge computing paradigm facilitates the communication-efficient digital twin services, and promises agile, fine-grained and cost-efficient provisioning of limited edge resources, where serverless functions are implemented by containers in cloudlets (edge servers). However, the nonnegligible cold start delay of containers deteriorates the responsiveness of digital twin services dramatically and the perceived user service experience. In this paper, we investigate delay-sensitive query service provisioning in digital twin-empowered serverless edge computing by considering user mobility. With digital twins of users deployed in the remote cloud, referred to as primary digital twins, we deploy their digital twin replicas based on serverless functions in cloudlets to mitigate the query service delay while enhancing user service satisfaction that is expressed as a utility function. We study two optimization problems with the aim of maximizing the accumulative utility gain: the digital twin replica placement problem per time slot, and the dynamic digital twin replica placement problem over a finite time horizon. We first formulate an Integer Linear Program (ILP) solution for the digital twin replica placement problem when the problem size is small;otherwise, we propose an approximation algorithm for the problem with a provable approximation ratio. We then design an online algorithm for the dynamic digital twin replica placement problem, and a performance-guaranteed online algorithm for a special case of the problem by assuming each user issues a query at each time slot. Finally, we evaluate the performance of the proposed algorithms for pl

关键词： Digital twins Heuristic algorithms approximation algorithms Delays Edge computing Containers Computers Digital twin serverless computing mobile edge computing user mobility approximation algorithm online algorithm user service satisfaction delay-sensitive service utility maximization resource allocation and optimization

来源：评论

学校读者我要写书评

暂无评论

Budget-Constrained Ego Network Extraction With Maximized Willingness

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2024年第12期36卷 7692-7707页

作者： Hsu, Bay-Yuan Lu, Chia-Hsun Chang, Ming-Yi Tseng, Chih-Ying Shen, Chih-Ya Natl Tsing Hua Univ Dept Ind Engn & Engn Management Hsinchu Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan Fu Jen Catholic Univ Dept Sociol New Taipei City Taiwan

Many large-scale machine learning approaches and graph algorithms are proposed recently to address a variety of problems in online social networks (OSNs). To evaluate and validate these algorithms and models, the data of ego-centric networks (ego networks) are widely adopted. Therefore, effectively extracting large-scale ego networks from OSNs becomes an important issue, particularly when privacy policies become increasingly strict nowadays. In this paper, we study the problem of extracting ego network data by considering jointly the user willingness, crawling cost, and structure of the network. We formulate a new research problem, named Structure and Willingness Aware Ego Network Extraction (SWAN) and analyze its NP-hardness. We first propose a (1-1/e) -approximation algorithm, named Tristar-Optimized Ego Network Identification with Maximum Willingness (TOMW) . In addition to the deterministic approximation algorithm, we also propose to automatically learn an effective heuristic approach with machine learning, to avoid the huge efforts for human to devise a good algorithm. The learning approach is named Willingness-maximized and Structure-aware Ego Network Extraction with Reinforcement Learning (WSRL) , in which we propose a novel constrastive learning strategy, named Contrastive Learning with Performance-boosting Graph Augmentation . We recruited 1,810 real-world participants and conducted an evaluation study to validate our problem formulation and proposed approaches. Moreover, experimental results on real social network datasets show that the proposed approaches outperform the other baselines significantly.

关键词： Costs Machine learning algorithms Data mining approximation algorithms Social networking (online) Recruitment Data models Willingness approximation algorithm crawling ego networks online social networks

来源：评论

学校读者我要写书评

暂无评论

The mixed integer trust region problem

引用

MATHEMATICAL PROGRAMMING 2024年 1-38页

作者： Del Pia, Alberto Univ Wisconsin Madison Dept Ind & Syst Engn Madison WI 53706 USA Univ Wisconsin Madison Wisconsin Inst Discovery Madison WI 53706 USA

In this paper we consider the problem of minimizing a general quadratic function over the mixed integer points in an ellipsoid. This problem is strongly NP-hard, NP-hard to approximate within a constant factor, and optimal solutions can be irrational. In our main result we show that an arbitrarily good solution can be found in polynomial time, if we fix the number of integer variables. This algorithm provides a natural extension to the mixed integer setting, of the polynomial solvability of the trust region problem proven by Ye, Karmarkar, Vavasis, and Zippel. As a result, our findings pave the way for designing efficient trust region methods for mixed integer nonlinear optimization problems. The techniques that we introduce are of independent interest and can be used in other mixed integer nonlinear optimization problems. As an example, we consider the problem of minimizing a general quadratic function over the mixed integer points in a polyhedron. For this problem, we show that a solution satisfying weak bounds with respect to optimality can be computed in polynomial time, provided that the number of integer variables is fixed. It is well known that finding a solution satisfying stronger bounds cannot be done in polynomial time, unless P = NP.

关键词： Trust region problem Mixed integer quadratic programming approximation algorithm Polynomial time algorithm Ellipsoid constraint

来源：评论

学校读者我要写书评

暂无评论

Combinatorial Benders decomposition for single machine scheduling in additive manufacturing with two-dimensional packing constraints

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第3期317卷 890-905页

作者： Mao, Zhaofang Fu, Enyuan Huang, Dian Fang, Kan Chen, Lin Tianjin Univ Coll Management & Econ Tianjin 300072 Peoples R China Tianjin Univ Lab Computat & Analyt Complex Management Syst CACMS Tianjin 300072 Peoples R China Tianjin Univ Sch New Media & Commun Tianjin 300072 Peoples R China Zhejiang Univ Coll Comp Sci Hangzhou 310027 Peoples R China

This paper addresses a single -machine scheduling problem in additive manufacturing (AM). We focus on the direct metal laser sintering (DMLS) technology of an AM process, where parts can be produced simultaneously in a batch. In this problem, we consider simultaneously the assignment of parts to batches and the packing of parts onto two-dimensional surfaces of the build chamber to minimize the makespan objective. To solve this problem, a mixed integer linear programming model is formulated, and an approximation algorithm is proposed, followed by an exact algorithm based on combinatorial Benders decomposition method with various Benders cuts and acceleration strategies (algorithm CBD). Finally, we conduct a comprehensive computational study to verify the efficiency of our proposed algorithm CBD. The computational results show that our proposed algorithm CBD can effectively solve the test instances with different sizes.

关键词： Scheduling Additive manufacturing Two-dimensional packing approximation algorithm Combinatorial benders decomposition

来源：评论

学校读者我要写书评

暂无评论

algorithms for a two-machine no-wait flow shop scheduling problem with two competing agents

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第1期48卷 6-6页

作者： Yang, Qi-Xia Liu, Long-Cheng Huang, Min Wang, Tian-Run Xiamen Univ Sch Math Sci Xiamen 361005 Peoples R China

In this paper, we consider the following two-machine no-wait flow shop scheduling problem with two competing agents F2 | M-1 -> M-2, M-2, p(ij)(A)=p, no- wait | CmaxA: CmaxB <= Q: Given a set of n jobs J={J(1),J(2), . . . ,J(n)} and two competing agents A and B. Agent A is associated with a set of nA jobs JA={J(1)A,J(2)A, . . . ,J(n)(A)A} to be processed on the machine M-1 first and then on the machine M-2 with no-wait constraint, and agent B is associated with a set of n(B) jobs J(B)={J(1)B,J(2)B, . . . ,J(nB)(B)} to be processed on the machine M-2 only, where the processing times for the jobs of agent A are all the same (i.e., p(ij)A=p), J=J(A)boolean OR J(B) and n=n(A)+n(B). The objective is to build a schedule pi of the n jobs that minimizing the makespan of agent A while maintaining the makespan of agent B not greater than a given value Q. We first show that the problem is polynomial time solvable in some special cases. For the non-solvable case, we present an O(nlog n)-time (1+1/n(A)+1)-approximation algorithm and show that this ratio of (1+1/n(A)+1) is asymptotically tight. Finally, (1+epsilon)-approximation algorithms are provided.

关键词： Scheduling with two agents No-wait flow shop Optimal algorithm approximation algorithm Makespan

来源：评论

学校读者我要写书评

暂无评论

Polynomial-time equivalences and refined algorithms for longest common subsequence variants

引用

DISCRETE APPLIED MATHEMATICS 2024年 353卷 44-64页

作者： Asahiro, Yuichi Jansson, Jesper Lin, Guohui Miyano, Eiji Ono, Hirotaka Utashima, Tadatoshi Kyushu Sangyo Univ Fukuoka Japan Kyoto Univ Kyoto Japan Univ Alberta Edmonton AB Canada Kyushu Inst Technol Iizuka Japan Nagoya Univ Nagoya Japan

The problem of computing the longest common subsequence of two sequences (LCS for short) is a classical and fundamental problem in computer science. In this article, we study four variants of LCS: the REPETITION-BOUNDED LONGEST COMMON SUBSEQUENCE problem (RBLCS), the MULTISET-RESTRICTED COMMON SUBSEQUENCE problem (MRCS), the TWO-SIDE-FILLED LONGEST COMMON SUBSEQUENCE problem (2FLCS), and the ONE-SIDEFILLED LONGEST COMMON SUBSEQUENCE problem (1FLCS). Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O(1.44225n)-time, dynamic programming (DP) based algorithm for RBLCS was proposed, where the two input sequences have lengths n and poly(n). Here, we first establish that each of MRCS, 1FLCS, and 2FLCS is polynomially equivalent to RBLCS. Then, we design a refined DP-based algorithm for RBLCS that runs in O(1.41422n) time, which implies that MRCS, 1FLCS, and 2FLCS can also be solved in O(1.41422n) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS. (c) 2024 Elsevier B.V. All rights reserved.

关键词： Longest common subsequence Repetition-bounded Multiset-restricted One-side-filled Two-side-filled Dynamic programming Exact algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Theoretical Analysis of Git Bisect

引用

algorithmICA 2024年第5期86卷 1365-1399页

作者： Courtiel, Julien Dorbec, Paul Lecoq, Romain Normandie Univ UNICAEN CNRS ENSICAENGREYC F-14000 Caen France

In this paper, we consider the problem of finding a regression in a version control system (VCS), such as git. The set of versions is modelled by a directed acyclic graph (DAG) where vertices represent versions of the software, and arcs are the changes between different versions. We assume that somewhere in the DAG, a bug was introduced, which persists in all of its subsequent versions. It is possible to query a vertex to check whether the corresponding version carries the bug. Given a DAG and a bugged vertex, the Regression Search Problem consists in finding the first vertex containing the bug in a minimum number of queries in the worst-case scenario. This problem is known to be NP-complete. We study the algorithm used in git to address this problem, known as git bisect. We prove that in a general setting, git bisect can use an exponentially larger number of queries than an optimal algorithm. We also consider the restriction where all vertices have indegree at most 2 (i.e. where merges are made between at most two branches at a time in the VCS), and prove that in this case, git bisect is a 1/log(2)(3/2)-approximation algorithm, and that this bound is tight. We also provide a better approximation algorithm for this case. Finally, we give an alternative proof of the NP-completeness of the Regression Search Problem, via a variation with bounded indegree.

关键词： Graph algorithm approximation algorithm Regression search Worst-case complexity Version control system

来源：评论

学校读者我要写书评

暂无评论

algorithms for Scheduling Problems with Rejection

引用

Tsinghua Science and Technology 2025年第2期30卷 561-568页

作者： Quanchang Zheng Fanyu Kong Jianfeng Ren Yuzhong Zhang School of Management Science Qufu Normal UniversityRizhao 276826China Institute of Operations Research Qufu Normal UniversityRizhao 276826China

We study scheduling problems with rejection on *** job consists of a processing time,a rejection cost,and a release *** goal is to minimize the makespan of the jobs accepted when the total rejection cost is not larger than a given ***,we verify that these problems are ***,for the multiprocessor scheduling problem with rejection,we give a pseudo-polynomial algorithm and two fully polynomial approximation schemes(FPTAS for short)for fixed positive integer m,where m is the number of *** the scheduling problem with rejection and the job with non-identical release time on m machines,we also design a pseudo-polynomial algorithm and a fully polynomial approximation scheme when m is a fixed positive *** provide an approximation algorithm with the worst case performance 2 for arbitrary positive integer ***,we discuss the online scheduling problem with *** show that even if there are just two distinct arrive times for the jobs,there is not any online algorithm whose competitive ratio is constant for it.

关键词： approximation algorithm dynamic programming fully polynomial approximation scheme scheduling rejection

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：