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

LP-Based approximation algorithms for Facility Location in Buy-at-Bulk Network Design

algorithmICA 2019年第3期81卷 1075-1095页

作者： Friggstad, Zachary Rezapour, Mohsen Salavatipour, Mohammad R. Soto, Jose A. Univ Alberta Dept Comp Sci Edmonton AB Canada KN Toosi Univ Technol Dept Math POB 16315-1618 Tehran Iran Univ Chile DIM Santiago Chile Univ Chile CMM Santiago Chile

We study problems that integrate buy-at-bulk network design into the classical (connected) facility location problem. In such problems, we need to open facilities, build a routing network, and route every client demand to an open facility. Furthermore, capacities of the edges can be purchased in discrete units from K different cable types with costs that satisfy economies of scale. We extend the linear programming framework of Talwar (IPCO 2002) for the single-source buy-at-bulk problem to these variants and prove integrality gap upper bounds for both facility location and connected facility location buy-at-bulk problems. For the unconnected variant we prove an integrality gap bound of O(K), and for the connected version, we get the first LP-based bound of O(1).

关键词： Buy-at-bulk network design Facility location approximation algorithm LP rounding

来源：评论

学校读者我要写书评

暂无评论

Using the minimum maximum flow degree to approximate the flow coloring problem

引用

ANNALS OF OPERATIONS RESEARCH 2022年第2期316卷 1267-1278页

作者： Campelo, Manoel Matias, Jhonata A. S. Univ Fed Ceara Dept Estat & Matemat Aplicada Fortaleza Ceara Brazil Univ Fed Ceara Programa Mestrado & Doutorado Ciencia Comp Fortaleza Ceara Brazil

Consider an arc-capacitated network N through which an integer-valued flow must be sent from several source nodes to a sink node. Each feasible flow defines a corresponding multi-graph with the same vertices as N and an edge for each arc ofN, where the edge multiplicity is the flow in the respective arc. The maximum flow degree of a feasible flow is the maximum sum of the flow entering and leaving a node of N, i.e. the maximum degree of the corresponding multigraph. The minimum maximum flow degree problem (MMFDP) consists in determining on N a feasible flow such that its maximum flow degree is minimum. We present a polynomial time algorithm for this problem. We use its optimum value to derive an improved upper bound for the flow coloring problem (FCP), which consists in finding a feasible flow whose corresponding multigraph has the minimum chromatic index. Based on this procedure, we design an approximation algorithm for the FCP that improves the best known approximation factor.

关键词： Graph algorithms Network flow Flow degree Flow coloring problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Connected Feedback Vertex Set on AT-Free Graphs 34th

Connected Feedback Vertex Set on AT-Free Graphs

引用

34th International Workshop on Combinatorial algorithms (IWOCA)

作者： Mukherjee, Joydeep Saha, Tamojit Ramakrishna Mission Vivekananda Educ & Res Inst Howrah India TCG CREST Inst Adv Intelligence Kolkata India

ISBN: (纸本)9783031343469;9783031343476

A connected feedback vertex set of a graph is a connected subgraph of the graph whose removal makes the graph cycle free. In this paper, we give an approximation algorithm that computes a connected feedback vertex set of size (1.9091OPT + 6) on 2-connected AT-free graphs with running time O(n(8)m(2)). Also, we give another approximation algorithm that computes a connected feedback vertex set of size (2.9091OPT + 6) on the same graph class with more efficient running time O(min{m(log(n)), n(2)}).

关键词： Graph algorithm approximation algorithm AT-free graph Feedback Vertex Set Combinatorial Optimization

来源：评论

学校读者我要写书评

暂无评论

No-Dimensional Tverberg Theorems and algorithms

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2022年第4期68卷 964-996页

作者： Choudhary, Aruni Mulzer, Wolfgang Free Univ Berlin Inst Informat Berlin Germany

Tverberg's theorem states that for any k >= 2 and any set P subset of R-d of at least (d 1)(k - 1) + 1 points in d dimensions, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem of finding the partition lies in the complexity class CLS = PPAD boolean AND PLS, but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Barany, and Mustafa (SODA 2019) gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any n-point set P subset of R-d and any k is an element of {2, ..., n} in O (nd inverted right perpendicular log k inverted left perpendicular) time a k-partition of P such that there is a ball of radius O ((k/ root n) diam(P)) that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria's method (Israel Journal Math., 1992) to reduce the Tverberg problem to the colorful Caratheodory problem (in the simplified tensor product interpretation of Barany and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem.

关键词： Tverberg theorem Colorful Caratheodory theorem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Two-Stage Method for Routing in Field-Programmable Gate Arrays with Time-Division Multiplexing

引用

Tsinghua Science and Technology 2022年第6期27卷 902-911页

作者： Peihuang Huang Longkun Guo Long Sun Xiaoyan Zhang College of Mathematics and Data Science Minjiang UniversityFuzhou 350116China School of Mathematics Science Nanjing Normal UniversityNanjing 210024China College of Mathematics and Computer Science Fuzhou UniversityFuzhou 350116China School of Mathematics Science and Institute of Mathematics Nanjing Normal UniversityNanjing 210024China

Emerging applications widely use field-programmable gate array(FPGA)prototypes as a tool to verify modern very-large-scale integration(VLSI)circuits,imposing many problems,including routing failure caused by the limited number of connections among blocks of FPGAs *** a shortage of connections can be alleviated through time-division multiplexing(TDM),by which multiple signals sharing an identical routing channel can be *** this context,the routing quality dominantly decides the performance of such systems,proposing the requirement of minimizing the signal delay between FPGA *** paper proposes algorithms for the routing problem in a multi-FPGA system with TDM support,aiming to minimize the maximum TDM *** algorithm consists of two major stages:(1)A method is proposed to set the weight of an edge according to how many times it is shared by the routing requirements and consequently to compute a set of approximate minimum Steiner trees.(2)A ratio assignment method based on the edge-demand framework is devised for assigning ratios to the edges respecting the TDM ratio *** were conducted against the public benchmarks to evaluate our proposed approach as compared with all published works,and the results manifest that our method achieves a better TDM ratio in comparison.

关键词： Field-programmable gate array(FPGA)routing time-division multiplexing minimum Steiner tree exact algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Norm Minimization-Based Convex Vector Optimization algorithm

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2022年第2期194卷 681-712页

作者： Ararat, Cagin Ulus, Firdevs Umer, Muhammad Bilkent Univ Dept Ind Engn Ankara Turkey

We propose an algorithm to generate inner and outer polyhedral approximations to the upper image of a bounded convex vector optimization problem. It is an outer approximation algorithm and is based on solving norm-minimizing scalarizations. Unlike Pascoletti-Serafini scalarization used in the literature for similar purposes, it does not involve a direction parameter. Therefore, the algorithm is free of direction-biasedness. We also propose a modification of the algorithm by introducing a suitable compact subset of the upper image, which helps in proving for the first time the finiteness of an algorithm for convex vector optimization. The computational performance of the algorithms is illustrated using some of the benchmark test problems, which shows promising results in comparison to a similar algorithm that is based on Pascoletti-Serafini scalarization.

关键词： Convex vector optimization Multiobjective optimization approximation algorithm Scalarization Norm minimization

来源：评论

学校读者我要写书评

暂无评论

k-Transmitter Watchman Routes 17th

k-Transmitter Watchman Routes

引用

17th International Conference and Workshops on algorithms and Computation

作者： Nilsson, Bengt J. Schmidt, Christiane Malmo Univ Dept Comp Sci & Media Technol Malmo Sweden Linkoping Univ Dept Sci & Technol Norrkoping Sweden

ISBN: (纸本)9783031270505;9783031270512

We consider the watchman route problem for a k-transmitter watchman: standing at point p in a polygon P, the watchman can see q is an element of P if (pq) over bar intersects P's boundary at most k times-q is k-visible to p. Traveling along the k-transmitter watchman route, either all points in P or a discrete set of points S subset of P must be k-visible to the watchman. We aim for minimizing the length of the k-transmitter watchman route. We show that even in simple polygons the shortest k-transmitter watchman route problem for a discrete set of points S subset of P is NP-complete and cannot be approximated to within a logarithmic factor (unless P=NP), both with and without a given starting point. Moreover, we present a polylogarithmic approximation for the k-transmitter watchman route problem for a given starting point and S. P with approximation ratio O(log(2) (|S| center dot n) log log(|S| center dot n) log |S|) (with |P| = n).

关键词： Watchman route k-Transmitter k-Transmitter watchman route NP-Hardness approximation algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Adaptive multi-feature budgeted profit maximization in social networks

引用

SOCIAL NETWORK ANALYSIS AND MINING 2022年第1期12卷 1-17页

作者： Chen, Tiantian Guo, Jianxiong Wu, Weili Univ Texas Dallas Erik Jonsson Sch Engn & Comp Sci Dept Comp Sci Richardson TX 75080 USA Beijing Normal Univ Adv Inst Nat Sci Zhuhai 519087 Peoples R China BNU HKBU United Int Coll Guangdong Key Lab AI & Multimodal Data Proc Zhuhai 519087 Peoples R China

Online social network has been one of the most important platforms for viral marketing. Most of existing researches about diffusion of adoptions of new products on networks are about one diffusion. That is, only one piece of information about the product is spread on the network. However, in fact, one product may have multiple features and the information about different features may spread independently in social network. When a user would like to purchase the product, he would consider all of the features of the product comprehensively not just consider one. Based on this, we propose a novel problem, multi-feature budgeted profit maximization (MBPM) problem, which first considers budgeted profit maximization under multiple features propagation of one product. Given a social network with each node having an activation cost and a profit, MBPM problem seeks for a seed set with expected cost no more than the budget to make the total expected profit as large as possible. We mainly consider MBPM problem under the adaptive setting, where seeds are chosen iteratively and next seed is selected according to current diffusion results. We study adaptive MBPM problem under two models, oracle model and noise model. The oracle model assumes conditional expected marginal profit of any node could be obtained in O(1) time, and a (1 - 1/e) expected approximation policy is proposed. Under the noise model, we estimate conditional expected marginal profit of a node by modifying the EPIC algorithm and propose an efficient policy, which could achieve a (1 - e(-(1- e))) expected approximation ratio. Several experiments are conducted on six realistic datasets to compare our proposed policies with their corresponding non-adaptive algorithms and some heuristic adaptive policies. Experimental results show efficiencies and superiorities of our policies.

关键词： Multi-feature diffusion Adaptive budgeted profit maximization approximation algorithm Social network

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation Framework for Attribute Recommendation

引用

Proceedings of the ACM on Management of Data 2023年第4期1卷 1-26页

作者： Xingguang Chen Fangyuan Zhang Jinchao Huang Sibo Wang The Chinese University of Hong Kong Hong Kong China

Trend analysis is a fundamental type of analytical query in online analytical processing (OLAP) systems. In trend analysis, a key step is to identify k valuable attributes whose distributions in two subsets under different predicates significantly differ for further investigation, where the difference is measured by metric functions. However, the exact solution that involves scanning all records is prohibitively expensive, particularly when handling large datasets in the era of big data. To minimize unnecessary data access, the existing state-of-the-art solution TopKAttr adopts sampling to avoid the expensive data scan. However, their solution still has two main drawbacks. Firstly, their solution is tailored only for two limited metric functions: the Earth Mover distance and Euclidean distance, and cannot be generalized to more complicated metric functions. Besides, their solution still aims to return the exact top-k answers via the sampling method, which still causes high running costs as shown in our *** by these limitations, we propose a general approximation framework for attribute recommendation that efficiently returns the top-k attributes with theoretical guarantees while supporting an extensive range of metric functions, such as the Kolmogorov-Smirnov test (KS-test), Chebyshev distance, the Earth Mover distance, Euclidean distance, and with the potential to more metrics. The key to our framework is a new bound estimation strategy that can be applied to a wide spectrum of metrics, as we listed above. Based on our estimation framework, we further devise an efficient approximation algorithm with theoretical guarantees to answer the top-k queries, which is widely used in attribute recommendation. Extensive experiments on four real large datasets show that our framework gains up to an order of magnitude speed-up and consistently high accuracy compared to TopKAttr, providing a promising alternative for attribute recommendation in OLAP systems.

关键词： approximation algorithm attribute recommendation sampling

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Capacitated Perishable Inventory Systems with Positive Lead Times

引用

MANAGEMENT SCIENCE 2018年第11期64卷 5038-5061页

作者： Chao, Xiuli Gong, Xiting Shi, Cong Yang, Chaolin Zhang, Huanan Zhou, Sean X. Univ Michigan Dept Ind & Operat Engn Ann Arbor MI 48109 USA Chinese Univ Hong Kong Fac Engn Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Chinese Univ Hong Kong CUHK Business Sch Dept Decis Sci & Managerial Econ Shatin Hong Kong Peoples R China Shanghai Univ Finance & Econ Sch Informat Management & Engn Res Inst Interdisciplinary Sci Shanghai 200433 Peoples R China Penn State Univ Harold & Inge Marcus Dept Ind & Mfg Engn University Pk PA 16802 USA

Managing perishable inventory systems with positive lead times and finite ordering capacities is important but notoriously difficult in both theory and computation. The optimal control policy is extremely complicated, and no effective heuristic policy has been proposed in the literature. In this paper, we develop an easy-to-compute approximation algorithm for this class of problems and prove that it admits a theoretical worst-case performance guarantee under independent and many commonly used positively correlated demand processes. Our worst-case analysis departs significantly from those in the previous studies, requiring several novel ideas. In particular, we introduce a transient unit-matching rule to dynamically match the supply and demand units, and the notion of associated demand processes that provides the right future demand information to establish the desired results. Our numerical study demonstrates the effectiveness of the proposed algorithm.

关键词： approximation algorithm perishable inventory finite capacity positive lead time correlated demand worst-case performance guarantee

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：