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

Improving the Integrality Gap for Multiway Cut 1

20th international conference on integer programming and combinatorial optimization (IPCO)

作者： Berczi, Kristof Chandrasekaran, Karthekeyan Kiraly, Tamas Madan, Vivek Eotvos Lorand Univ Dept Operat Res MTA ELTE Egervary Res Grp Budapest Hungary Univ Illinois Urbana IL 61801 USA

ISBN: (数字)9783030179533

ISBN: (纸本)9783030179533;9783030179526

In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal so that the total weight of the edges crossing the partition is minimized. the multiway cut problem for k >= 3 is APX-hard. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrak [12] while the best known inapproximability result due to Angelidakis, Makarychev and Manurangsi [1] rules out efficient algorithms to achieve an approximation factor that is less than 1.2. In this work, we improve on the lower bound to 1.20016 by constructing an integrality gap instance for the CKR relaxation. A technical challenge in improving the gap has been the lack of geometric tools to understand higher-dimensional simplices. Our instance is a non-trivial 3-dimensional instance that overcomes this technical challenge. We analyze the gap of the instance by viewing it as a convex combination of 2-dimensional instances and a uniform 3-dimensional instance. We believe that this technique could be exploited further to construct instances with larger integrality gap. One of the ingredients of our proof technique is a generalization of a result on Sperner admissible labelings due to Mirzakhani and Vondrak [11] that might be of independent combinatorial interest.

关键词： combinatorial optimization Multiway cut Integrality gap Approximation

来源：评论

学校读者我要写书评

暂无评论

Distributed Resource Allocation Using Iterative combinatorial Auction for Device-to-Device Underlay Cellular Networks 15

Distributed Resource Allocation Using Iterative Combinatoria...

引用

15th IEEE international Wireless Communications and Mobile Computing conference (IEEE IWCMC)

作者： Mahfoudhi, Mohamed Hamdi, Monia Zaied, Mourad Gabes Univ RTIM Gabes Tunisia Princess Nourah bint Abdulrahman Univ Coll Comp & Informat Sci Riyadh Saudi Arabia

ISBN: (纸本)9781538677476

Device-to-Device communications underlaying cellular networks have great potential to provide a significant improvement in network performance. It allows better resource utilization, increases user throughput and extends the battery life of user equipment compared the conventional cellular network. the fundamental challenge in D2D communications is how to allocate spectral bands and control transmission power optimally, in order to ensure the quality of service (QoS) and increase the energy efficiency. this problem is mixed integer non-linear programming (MINLP) due to the discrete variables. In this paper, we consider the joint power control and channel allocation for underlying D2D communications. We formulated the optimization problem in the form of an iterative combinatorial auction. the proposed algorithm is designed with two rounds. In the first round, each bidder submits its offer for each channel. In the second round, the goal is to improve the results obtained in the first round by considering the interference received from other users. the system power consumption and network lifetime were evaluated through simulations.

关键词： Device-to-Device communications resource allocation power control iterative combinatorial auction energy efficiency

来源：评论

学校读者我要写书评

暂无评论

combinatorial attacks on binarized neural networks 7

Combinatorial attacks on binarized neural networks

引用

7th international conference on Learning Representations, ICLR 2019

作者： Khalil, Elias B. Gupta, Amrita Dilkina, Bistra College of Computing Georgia Tech United States Department of Computer Science University of Southern California United States

Binarized Neural Networks (BNNs) have recently attracted significant interest due to their computational efficiency. Concurrently, it has been shown that neural networks may be overly sensitive to "attacks" - tiny adversarial changes in the input - which may be detrimental to their use in safety-critical domains. Designing attack algorithms that effectively fool trained models is a key step towards learning robust neural networks. the discrete, non-differentiable nature of BNNs, which distinguishes them from their full-precision counterparts, poses a challenge to gradient-based attacks. In this work, we study the problem of attacking a BNN through the lens of combinatorial and integer optimization. We propose a Mixed integer Linear programming (MILP) formulation of the problem. While exact and flexible, the MILP quickly becomes intractable as the network and perturbation space grow. To address this issue, we propose IProp, a decomposition-based algorithm that solves a sequence of much smaller MILP problems. Experimentally, we evaluate both proposed methods against the standard gradient-based attack (PGD) on MNIST and Fashion-MNIST, and show that IProp performs favorably compared to PGD, while scaling beyond the limits of the MILP. © 7th international conference on Learning Representations, ICLR 2019. All Rights Reserved.

关键词： Computational efficiency

来源：评论

学校读者我要写书评

暂无评论

Online Submodular Maximization: Beating 1/2 Made Simple 1

引用

20th international conference on integer programming and combinatorial optimization (IPCO)

作者： Buchbinder, Niv Feldman, Moran Filmus, Yuval Garg, Mohit Tel Aviv Univ Tel Aviv Israel Open Univ Israel Raanana Israel Technion Haifa Israel

ISBN: (数字)9783030179533

ISBN: (纸本)9783030179533;9783030179526

the problem of Submodular Welfare Maximization (SWM) captures an important subclass of combinatorial auctions and has been studied extensively from both computational and economic perspectives. In particular, it has been studied in a natural online setting in which items arrive one-by-one and should be allocated irrevocably upon arrival. In this setting, it is well known that the greedy algorithm achieves a competitive ratio of 1/2, and recently Kapralov et al. [22] showed that this ratio is optimal for the problem. Surprisingly, despite this impossibility result, Korula et al. [25] were able to show that the same algorithm is 0.5052-competitive when the items arrive in a uniformly random order, but unfortunately, their proof is very long and involved. In this work, we present an (arguably) much simpler analysis that provides a slightly better guarantee of 0.5096-competitiveness for the greedy algorithm in the random-arrival model. Moreover, this analysis applies also to a generalization of online SWM in which the sets defining a (simple) partition matroid arrive online in a uniformly random order, and we would like to maximize a monotone submodular function subject to this matroid. Furthermore, for this more general problem, we prove an upper bound of 0.576 on the competitive ratio of the greedy algorithm, ruling out the possibility that the competitiveness of this natural algorithm matches the optimal offline approximation ratio of 1 - 1/e.

关键词： Submodular optimization Online auctions Greedy algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal Application Deployment in Mobile Edge Computing Environment

Optimal Application Deployment in Mobile Edge Computing Envi...

引用

IEEE international conference on Cloud Computing, CLOUD

作者： Feifei Chen Jingwen Zhou Xiaoyu Xia Hai Jin Qiang He School of Information Technology Deakin University Geelong Australia School of Computer Science and Technology Huazhong University of Science and Technology China School of Computer Science Chengdu University of Information Technology China

ISBN: (数字)9781728187808

ISBN: (纸本)9781728187815

Mobile edge computing has emerged as a new distributed computing paradigm that overcomes the limitations of traditional cloud computing. In an edge computing environment, an app vendor can hire computing and storage resources on edge servers for deploying their applications to deliver lower-latency services to their app users. Under a budget constraint, an optimal edge application deployment strategy allows an app vendor to deploy application instances on edge servers in a specific area and provide services to the most app users in the area. In this paper, we make the first attempt to tackle this edge application deployment (EAD) problem. Specifically, we formulate the EAD problem as a constrained optimization problem and prove its NP-hardness. then, we propose an optimal approach named EAD-opt to find the optimal solution of EAD based on integer programming, and an approximation approach named EAD-apx to find approximate solutions in large-scale EAD scenarios efficiently. We evaluate our approaches by conducting experiments on a widely used real-world data set and a synthetic data set with comparison against two baseline approaches. the experimental results demonstrate that our approaches can solve the EAD problem effectively and efficiently.

关键词： integer programming Cloud computing conferences Servers Distributed computing optimization Edge computing

来源：评论

学校读者我要写书评

暂无评论

Maximizing Profit in Energy-Efficient Moldable Task Execution with Deadline

Maximizing Profit in Energy-Efficient Moldable Task Executio...

引用

Euromicro conference on Parallel, Distributed and Network-Based Processing

作者： Sebastian Litzinger Jörg Keller Christoph Kessler Faculty of Mathematics and Computer Science FernUniversität in Hagen Hagen Germany Dept. of Computer and Information Science (IDA) Linköping University Linköping Sweden

ISBN: (数字)9781728165820

ISBN: (纸本)9781728165837

We consider static scheduling of parallelizable tasks onto machines with frequency scaling for the case that not all tasks can be executed prior to a deadline. We model this scenario from a HPC cluster operator's perspective. We solve the combinatorial optimization problem to maximize the operator's profit by integer linear programming and by a heuristic. We evaluate the heuristic with synthetic benchmark task sets and demonstrate that it achieves at most 20 % less profit than the solution via linear programming, so that it can be used for large task sets where the latter is not feasible anymore.

关键词： Task analysis Schedules optimization Parallel machines Program processors Runtime Radio spectrum management

来源：评论

学校读者我要写书评

暂无评论

Poster: Space and Time Optimal DNN Primitive Selection with integer Linear programming 28

Poster: Space and Time Optimal DNN Primitive Selection with ...

引用

28th international conference on Parallel Architectures and Compilation Techniques (PACT)

作者： Wen, Yuan Anderson, Andrew Radu, Valentin O'Boyle, Michael F. P. Gregg, David Trinity Coll Dublin Dublin Ireland Univ Edinburgh Edinburgh Midlothian Scotland

ISBN: (纸本)9781728136134

Convolutional neural networks (CNNs) are used in many applications, from industrial robotics to biometric identification on mobile devices. But they can be too resource-hungry for mobile and embedded devices with tightly constrained memory and energy budgets. We propose an aheadof-time primitive selection for CNNs, based on integer linear programming (ILP). Under a tight memory budget, our ILP solver selects the optimal primitive for each layer such that the entire network is optimized for execution time subject to a memory budget, or vice versa. Our method yields significant speedup and memory reduction compared to existing methods.

关键词： neural network optimization computing operators primitive selection optimal convolutional layer

来源：评论

学校读者我要写书评

暂无评论

Co-optimizing Core Allocation, Mapping and DVFS in Streaming Programs with Moldable Tasks for Energy Efficient Execution on Manycore Architectures 19

Co-optimizing Core Allocation, Mapping and DVFS in Streaming...

引用

19th international conference on Application of Concurrency to System Design (ACSD)

作者： Melot, Nicolas Kessler, Christoph Eitschberger, Patrick Keller, Joerg Linkoping Univ Dept Comp & Informat Sci IDA Linkoping Sweden Fernuniv Fac Math & Comp Sci Hagen Germany

ISBN: (纸本)9781728138435

Stream programming abstracts parallelism complexity by modeling a program as a set of streaming tasks. Tasks run repeatedly and can even be internally parallel, i.e., use one or multiple cores simultaneously (moldable). the throughput of the streaming application, as well as its energy consumption, depends strongly on scheduling, i.e., on how tasks are mapped to cores, and on the frequency at which they run. Crown scheduling is a scheduling method that reduces this problem's combinatorial complexity considerably by introducing a few additional restrictions especially on tasks' core allocation sizes and mapping. While it has previously been shown to outperform competing methods, the impact of these restrictions on the schedule quality has, up to now, never been analyzed quantitatively. In this paper, we first propose several crown scheduler improvements toward fewer restrictions. Also, we provide an integer Linear programming formulation that solves the same optimization problem without the inherent restrictions of crown scheduling. While in an extreme case an unrestricted schedule might use 3.7 times less energy than a crown schedule for a realistic execution platform model, we show that in practical benchmarks the difference is small while crown schedulers are significantly faster than unrestricted scheduling. We experimentally confirm this with benchmarks derived from random task collections, classic parallel algorithms as well as the Streamit benchmark suite.

关键词： scheduling energy many-core optimization scaling

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for maximum coverage with group budget constraints

引用

thEORETICAL COMPUTER SCIENCE 2019年 788卷 53-65页

作者： Guo, Longkun Li, Min Xu, Dachuan Fuzhou Univ Coll Math & Comp Sci Fuzhou 350116 Fujian Peoples R China Shandong Normal Univ Sch Math & Stat Jinan 250014 Shandong Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China

Given a ground set U with a non -negative weight wi for each i E U, a positive integer k and a collection of sets 8, which is partitioned into a family of disjoint groups g. the goal of the Maximum Coverage problem with Group budget constraints (MCG) is to select k sets from S, such that the total weight of the union of the k sets is maximized and at most one set is selected from each group Q E We first present an approximation algorithm with a factor 1 a and an exponential time via randomized linear programming rounding technique. then we improve the time complexity of the algorithm to 0((m + n)3.5L + k3.5q7L) for ISM = m, IU I = n, and L being the length of the input, by the key idea of modeling the selection of groups as computing a constrained flow in a corresponding auxiliary graph. the algorithm is later shown can be extended to solve two generalizations of MCG. Last but not the least, we present another algorithm with a time complexity 0 ((m +n)3.5L +1(81.5L) and a slightly increased approximation ratio 1 ei-1 mainly based on the idea of partition, where iS > 2 is a parameter tuning which can balance the time complexity and the ratio. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Maximum coverage problem with group budget constraints Approximation algorithm Auxiliary graph Network flow Randomized linear programming rounding

来源：评论

学校读者我要写书评

暂无评论

optimization of production system with environmental consideration: the effect of worker learning in a metallurgy factory

Optimization of production system with environmental conside...

引用

international conference on Logistics (LOGISTIQUA)

作者： Djazia Nadjat Sekkal Fayçal Belkaid Manufacturing Engineering Laboratory of Tlemcen University of Tlemcen Tlemcen Algeria

ISBN: (数字)9781728198811

ISBN: (纸本)9781728198828

Over the last few years, energy consumption and carbon emissions have been the subject of a great deal of attention, due to the ever-increasing climate change and diminishing of fossil energy resources. In this context, this article aims to minimize the maximum completion time (makespan) by taking into account environmental aspects in a production system. In particular, we consider a flow shop group scheduling problem with sequence-dependent setup times, learning effect related to the ability of each operator as well as machine speeds and the various carbon emissions associated with them, inspired by a real case study of the manufacture of forged connecting rods in a metallurgy factory. the objective is to determine both an optimal scheduling of the groups and the jobs within the groups in order to minimize the makespan by restricting the carbon emissions of the system. A mixed integer linear programming model is formulated, the computational results are also presented and discussed through the different scenarios.

关键词： Production systems Job shop scheduling Optimal scheduling Carbon dioxide Simulated annealing Minimization Production facilities

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：