Designing and analyzing algorithms with provable performance guarantees enables efficient optimization problem solving in different application domains, e.g. communication networks, transportation, economics, and manu...
详细信息
Designing and analyzing algorithms with provable performance guarantees enables efficient optimization problem solving in different application domains, e.g. communication networks, transportation, economics, and manufacturing. Despite the significant contributions of approximation algorithms in engineering, only limited and isolated works contribute from this perspective in process systems engineering. The current paper discusses three representative, NP-hard problems in process systems engineering: (i) pooling, (ii) process scheduling, and (iii) heat exchanger network synthesis. We survey relevant results and raise major open questions. Further, we present approximation algorithms applications which are relevant to process systems engineering: (i) better mathematical modeling, (ii) problem classification, (iii) designing solution methods, and (iv) dealing with uncertainty. This paper aims to motivate further research at the intersection of approximation algorithms and process systems engineering. (C) 2019 Elsevier Ltd. All rights reserved.
We consider the market mechanism to sell two types of products, A and B, to a set of buyers I={1,2,...n}. . The amounts of products are m(A) and m(B) respectively. Each buyer i has his information including the budget...
详细信息
We consider the market mechanism to sell two types of products, A and B, to a set of buyers I={1,2,...n}. . The amounts of products are m(A) and m(B) respectively. Each buyer i has his information including the budget, the preference and the utility function. On collecting the information from all buyers, the market maker determines the price of each product and allocates some amount of product to each buyer. The objective of the market maker is designing a mechanism to maximize the total utility of the buyers in satisfying the semi market equilibrium. In this paper, we show that this problem is NP-hard and give an iterative algorithm with the approximation ratio 1.5. Moreover, we introduce a PTAS for the problem, which is an (1+epsilon)-approximation algorithm with the running time O(2(1/epsilon) +n log n) for any positive epsilon.
In this paper, we consider the 1-line Euclidean minimum Steiner tree problem, which is a variation of the Euclidean minimum Steiner tree problem and defined as follows. Given a set P=of n points in the Euclidean plane...
详细信息
In this paper, we consider the 1-line Euclidean minimum Steiner tree problem, which is a variation of the Euclidean minimum Steiner tree problem and defined as follows. Given a set P=of n points in the Euclidean plane R2, we are asked to find the location of a line l and an Euclidean Steiner tree T(l) in R2 such that at least one Steiner point is located at such a line l, the objective is to minimize total weight of such an Euclidean Steiner tree T(l), i.e., min{ n-ary sumation e is an element of T(l)w(e)|T(l)\ is an Euclidean Steiner tree as mentioned-above}, where we define weight w(e)=0 if the end-points u, v of each edge e=uv is an element of T(l) are both located at such a line l and otherwise we denote weight w(e) to be the Euclidean distance between u and v. Given a fixed line l as an input in R2, we refer this problem as the 1-line-fixed Euclidean minimum Steiner tree problem;In addition, when Steiner points added are all located at such a fixed line l, we refer this problem as the constrained Euclidean minimum Steiner tree problem. We obtain the following two main results. (1) Using a polynomial-time exact algorithm to find a constrained Euclidean minimum Steiner tree, we can design a 1.214-approximation algorithm to solve the 1-line-fixed Euclidean minimum Steiner tree problem, and this algorithm runs in time O(nlogn);(2) Using a combination of the algorithm designed in Sect. 1 for many times, a technique of finding linear facility location and an important lemma proved by some techniques of computational geometry, we can provide a 1.214-approximation algorithm to solve the 1-line Euclidean minimum Steiner tree problem, and this new algorithm runs in time O(n(3)log n).
An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S subset of V that maximizes the number of edges in the cut delta(S) such that t...
详细信息
An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S subset of V that maximizes the number of edges in the cut delta(S) such that the induced graph G[S] is connected. We present the first non-trivial Omega(1/log n) approximation algorithm for the Connected Maximum Cut problem in general graphs using novel techniques. We then extend our algorithm to edge weighted case and obtain a poly-logarithmic approximation algorithm. Interestingly, in contrast to the classical Max-Cut problem that can be solved in polynomial time on planar graphs, we show that the Connected Maximum Cut problem remains NP-hard on unweighted, planar graphs. On the positive side, we obtain a polynomial time approximation scheme for the Connected Maximum Cut problem on planar graphs and more generally on bounded genus graphs. (C) 2020 Elsevier B.V. All rights reserved.
We consider the a priori traveling repairman problem, which is a stochastic version of the classic traveling repairman problem. Given a metric (V, d) with a root r is an element of V, the traveling repairman problem (...
详细信息
We consider the a priori traveling repairman problem, which is a stochastic version of the classic traveling repairman problem. Given a metric (V, d) with a root r is an element of V, the traveling repairman problem (TRP) involves finding a tour originating from r that minimizes the sum of arrival-times at all vertices. In its a priori version, we are also given independent probabilities of each vertex being active. We want to find a master tour tau originating from r and visiting all vertices. The objective is to minimize the expected sum of arrival-times at all active vertices, when tau is shortcut over the inactive vertices. We obtain the first constant-factor approximation algorithm for a priori TRP under independent non-uniform probabilities. Our result provides a general reduction from non-uniform to uniform probabilities, and uses (in black-box manner) an existing approximation algorithm for a priori TRP under uniform probabilities. (C) 2020 Elsevier B.V. All rights reserved.
We consider the NP-hard twin robot scheduling problem, which was introduced by Erdogan et al. (Naval Res Logist (NRL) 61(2):119-130, 2014). Here, two moving robots positioned at the opposite ends of a rail have to per...
详细信息
We consider the NP-hard twin robot scheduling problem, which was introduced by Erdogan et al. (Naval Res Logist (NRL) 61(2):119-130, 2014). Here, two moving robots positioned at the opposite ends of a rail have to perform automated storage and retrieval jobs at given positions along the gantry rail with a non-crossing constraint. The objective is to minimize the makespan. We extend the original problem by considering pickup and delivery times and present exact and approximation algorithms with a performance ratio of approximate to 1.1716 for large instances. Further, we compare the presented algorithms in a comprehensive numerical study.
In recent years, k-submodular functions have garnered significant attention due to their natural extension of submodular functions and their practical applications, such as influence maximization and sensor placement....
详细信息
In recent years, k-submodular functions have garnered significant attention due to their natural extension of submodular functions and their practical applications, such as influence maximization and sensor placement. Influence maximization involves selecting a set of nodes in a network to maximize the spread of information, while sensor placement focuses on optimizing the locations of sensors to maximize coverage or detection efficiency. This paper first proposes two randomized algorithms aimed at improving the approximation ratio for maximizing monotone k-submodular functions under matroid constraints and individual size constraints. Under the matroid constraints, we design a randomized algorithm with an approximation ratio of nk2nk-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{nk}{2nk-1}$$\end{document} and a complexity of O(rn(RO+kEO))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(rn(\text {RO}+k\text {EO}))$$\end{document}, where n represents the total number of elements in the ground set, k represents the number of disjoint sets in a k-submodular function, r denotes the size of the largest independent set, RO\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {RO}$$\end{document} indicates the time required for the matroid's independence oracle, and EO\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usep
k-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approximate within a factor of 1.93, even in t...
详细信息
ISBN:
(纸本)9781577358763
k-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approximate within a factor of 1.93, even in the plane, if one insists the dependence on k in the running time be polynomial. Without this restriction, a classic algorithm yields a 2(O((k log k)/epsilon)) dn-time (1 + epsilon) -approximation for Euclidean k-center, where d is the dimension. We give a faster algorithm for small dimensions: roughly speaking an O* (2(O((1/epsilon)O(d).k1-1/*** k)))-time (1 + epsilon )-approximation. In particular, the running time is roughly O*(2(O((1/epsilon)O(1)) (root k log k))) in the plane. We complement our algorithmic result with a matching hardness lower bound. We also consider a well-studied generalization of k-center, called Non-uniform k-center (NUkC), where we allow different radii clusters. NUkC is NP-hard to approximate within any factor, even in the Euclidean case. We design a 2(O(k log k))n(2) time 3-approximation for NUkC in general metrics, and a 2(O((k log k)/epsilon))dn time (1 + epsilon)- -approximation for Euclidean NUkC. The latter time bound matches the bound for k-center.
Training a one-node neural network with the ReLU activation function via optimization, which we refer to as the ON-ReLU problem, is a fundamental problem in machine learning. In this paper, we begin by proving the NP-...
详细信息
Training a one-node neural network with the ReLU activation function via optimization, which we refer to as the ON-ReLU problem, is a fundamental problem in machine learning. In this paper, we begin by proving the NP-hardness of the ON-ReLU problem. We then present an approximation algorithm to solve the ON-ReLU problem, whose running time is O(n(k)) where n is the number of samples, and k is a predefined integral constant as an algorithm parameter. We analyze the performance of this algorithm under two regimes and show that: (1) given any arbitrary set of training samples, the algorithm guarantees an (n/k)-approximation for the ON-ReLU problem - to the best of our knowledge, this is the first time that an algorithm guarantees an approximation ratio for arbitrary data scenario;thus, in the ideal case (i.e., when the training error is zero) the approximation algorithm achieves the globally optimal solution for the ON-ReLU problem;and (2) given training sample with Gaussian noise, the same approximation algorithm achieves a much better asymptotic approximation ratiowhich is independent of the number of samples n. Extensive numerical studies show that our approximation algorithm can perform better than the gradient descent algorithm. Our numerical results also show that the solution of the approximation algorithm can provide a good initialization for gradient descent, which can significantly improve the performance.
In this paper we study the min-max cycle cover problem with neighborhoods, which is to find a given number of K cycles to collaboratively visit n Points of Interest (POIs) in a 2D space such that the length of the lon...
详细信息
In this paper we study the min-max cycle cover problem with neighborhoods, which is to find a given number of K cycles to collaboratively visit n Points of Interest (POIs) in a 2D space such that the length of the longest cycle among the K cycles is minimized. The problem arises from many applications, including employing mobile sinks to collect sensor data in wireless sensor networks (WSNs), dispatching charging vehicles to recharge sensors in rechargeable sensor networks, scheduling Unmanned Aerial Vehicles (UAVs) to monitor disaster areas, etc. For example, consider the application of employing multiple mobile sinks to collect sensor data in WSNs. If some mobile sink has a long data collection tour while the other mobile sinks have short tours, this incurs a long data collection latency of the sensors in the long tour. Existing studies assumed that one vehicle needs to move to the location of a POI to serve it. We however assume that the vehicle is able to serve the POI as long as the vehicle is within the neighborhood area of the POI. One such an example is that a mobile sink in a WSN can receive data from a sensor if it is within the transmission range of the sensor (e.g., within 50 meters). It can be seen that the ignorance of neighborhoods will incur a longer traveling length. On the other hand, most existing studies only took into account the vehicle traveling time but ignore the POI service time. Consequently, although the length of some vehicle tour is short, the total amount of time consumed by a vehicle in the tour is prohibitively long, due to many POIs in the tour. In this paper we first study the min-max cycle cover problem with neighborhoods, by incorporating both neighborhoods and POI service time into consideration. We then propose novel approximation algorithms for the problem, by exploring the combinatorial properties of the problem. We finally evaluate the proposed algorithms via experimental simulations. Experimental results show that the propo
暂无评论