The Experts below are selected from a list of 9663 Experts worldwide ranked by ideXlab platform
Edwin K. P. Chong - One of the best experts on this subject based on the ideXlab platform.
-
Submodular optimization problems and Greedy strategies: A survey
Discrete Event Dynamic Systems, 2020Co-Authors: Yajing Liu, Edwin K. P. Chong, Ali Pezeshki, Zhenliang ZhangAbstract:The Greedy Strategy is an approximation algorithm to solve optimization problems arising in decision making with multiple actions. How good is the Greedy Strategy compared to the optimal solution? In this survey, we mainly consider two classes of optimization problems where the objective function is submodular. The first is set submodular optimization, which is to choose a set of actions to optimize a set submodular objective function, and the second is string submodular optimization, which is to choose an ordered set of actions to optimize a string submodular function. Our emphasis here is on performance bounds for the Greedy Strategy in submodular optimization problems. Specifically, we review performance bounds for the Greedy Strategy, more general and improved bounds in terms of curvature, performance bounds for the batched Greedy Strategy, and performance bounds for Nash equilibria.
-
polynomial time methods to solve unimodular quadratic programs with performance guarantees
IEEE Transactions on Aerospace and Electronic Systems, 2019Co-Authors: Shankarachary Ragi, Edwin K. P. Chong, Hans D. MittelmannAbstract:We develop polynomial-time heuristic methods to solve unimodular quadratic program (UQP) approximately, which is a known non-deterministic polynomial-time hard (NP-hard) problem. Several problems in active sensing and wireless communication applications boil down to UQPs. First, we derive a performance bound for a known UQP approximation method called dominant eigenvector matching heuristic. Next, we present two new polynomial-time heuristic methods inspired from the Greedy Strategy, and we provide performance guarantees for these methods with respect to the optimal objective.
-
improved bounds for the Greedy Strategy in optimization problems with curvature
Journal of Combinatorial Optimization, 2019Co-Authors: Yajing Liu, Edwin K. P. Chong, Ali PezeshkiAbstract:Consider the problem of choosing a set of actions to optimize a real-valued polymatroid function subject to matroid constraints. The Greedy Strategy, an approximate solution, is known to satisfy some bounds in terms of the total curvature. The total curvature depends on function values on sets outside the constraint matroid. If the function is defined only on the matroid, the problem still makes sense, but the existing bounds involving the total curvature do not apply, which is puzzling. This motivates an alternative formulation of such bounds. The first question we address is whether it is possible to extend a polymatroid function defined on a matroid to one on the entire power set. This was recently shown to be negative in general. Here, we provide necessary and sufficient conditions for the existence of an incremental extension of a polymatroid function defined on the uniform matroid of rank k to one with rank \(k+1\), together with an algorithm for constructing the extension. Whenever a polymatroid function defined on a matroid can be extended to the entire power set, the bounds involving the total curvature of the extension apply. However, these bounds still depend on sets outside the constraint matroid. Motivated by this, we define a new notion of curvature called partial curvature, involving only sets in the matroid. We derive necessary and sufficient conditions for an extension to have a total curvature equal to the partial curvature. Moreover, we prove that the bounds in terms of the partial curvature are in general improved over the previous ones. We illustrate our results with two contrasting examples motivated by practical problems.
-
extending polymatroid set functions with curvature and bounding the Greedy Strategy
IEEE Signal Processing Workshop on Statistical Signal Processing, 2018Co-Authors: Yajing Liu, Edwin K. P. Chong, Ali PezeshkiAbstract:Consider the problem of choosing a set of actions to optimize a real-valued polymatroid function subject to matroid constraints. The Greedy Strategy provides an approximate solution to the optimization problem, and it is known to satisfy some performance bounds in terms of the total curvature. But the total curvature depends on the values of the objective function on sets outside the matroid. If we are given a function defined only on the matroid, the problem still makes sense, but the existing bounds involving the total curvature do not apply. This motivates an alternative formulation of such bounds. We provide necessary and sufficient conditions for the existence of an extension of a polymatroid function defined on the matroid to one defined on the whole power set. Our results give rise to bounds for systems satisfying the necessary and sufficient conditions, which apply to problems where the objective function is defined only on the matroid. When the objective function is defined on the entire power set, the bounds we derive in general improve over the previous ones. To illustrate our results, we present a task scheduling problem.
-
improved bounds for the Greedy Strategy in optimization problems with curvatures
arXiv: Optimization and Control, 2017Co-Authors: Yajing Liu, Edwin K. P. Chong, Ali PezeshkiAbstract:Consider the problem of choosing a set of actions to optimize an objective function that is a real-valued polymatroid function subject to matroid constraints. The Greedy Strategy provides an approximate solution to the optimization problem, and it is known to satisfy some performance bounds in terms of the total curvature. The total curvature depends on the value of objective function on sets outside the constraint matroid. If we are given a function defined only on the matroid, the problem still makes sense, but the existing bounds involving the total curvature do not apply. This is puzzling: If the optimization problem is perfectly well defined, why should the bounds no longer apply? This motivates an alternative formulation of such bounding techniques. The first question that comes to mind is whether it is possible to extend a polymatroid function defined on a matroid to one on the entire power set. This was recently shown to be negative in general. Here, we provide necessary and sufficient conditions for the existence of an \emph{incremental} extension of a polymatroid function defined on the uniform matroid of rank $k$ to one defined on the uniform matroid of rank $k+1$, together with an algorithm for constructing the extension. Whenever a polymatroid objective function defined on a matroid can be extended to the entire power set, the Greedy approximation bounds involving the total curvature of the extension apply. However, these bounds still depend on sets outside the constraint matroid. Motivated by this, we define a new notion of curvature called \emph{partial curvature}, involving only sets in the matroid. We derive necessary and sufficient conditions for an extension of the function to have a total curvature that is equal to the partial curvature. Moreover, we prove that the bounds in terms of the partial curvature are in general improved over the previous ones......
Tung Khac Truong - One of the best experts on this subject based on the ideXlab platform.
-
A New Hybrid Particle Swarm Optimization and Greedy for 0-1 Knapsack Problem
Indonesian Journal of Electrical Engineering and Computer Science, 2016Co-Authors: Phuong Hoai Nguyen, Dong Wang, Tung Khac TruongAbstract:This paper proposes a new binary particle swarm optimization with a Greedy Strategy to solve 0-1 knapsack problem. Two constraint handling techniques are consider to cooperation with binary particle swarm optimization that are penalty function and Greedy. The sigmoid transfer function is used to convert real code to binary code. The experimental results have proven the superior performance of the proposed algorithm. Full Text: PDF DOI: http://dx.doi.org/10.11591/ijeecs.v1.i3.pp411-418
-
Solving 0−1 knapsack problem by artificial chemical reaction optimization algorithm with a Greedy Strategy
Journal of Intelligent & Fuzzy Systems, 2015Co-Authors: Tung Khac Truong, Aijia Ouyang, Tien Trong NguyenAbstract:This paper proposes a new artificial chemical reaction optimization algorithm with a Greedy Strategy to solve 0-1 knapsack problem. The artificial chemical reaction optimization (ACROA) inspiring the chemical reaction process is used to implement the local and global search. A new repair operator integrating a Greedy Strategy and random selection is used to repair the infeasible solutions. The experimental results have proven the superior performance of ACROA compared to genetic algorithm, and quantum-inspired evolutionary algorithm.
-
chemical reaction optimization with Greedy Strategy for the 0 1 knapsack problem
Applied Soft Computing, 2013Co-Authors: Tung Khac Truong, Kenli Li, Yuming XuAbstract:The 0-1 knapsack problem (KP01) is a well-known combinatorial optimization problem. It is an NP-hard problem which plays important roles in computing theory and in many real life applications. Chemical reaction optimization (CRO) is a new optimization framework, inspired by the nature of chemical reactions. CRO has demonstrated excellent performance in solving many engineering problems such as the quadratic assignment problem, neural network training, multimodal continuous problems, etc. This paper proposes a new chemical reaction optimization with Greedy Strategy algorithm (CROG) to solve KP01. The paper also explains the operator design and parameter turning methods for CROG. A new repair function integrating a Greedy Strategy and random selection is used to repair the infeasible solutions. The experimental results have proven the superior performance of CROG compared to genetic algorithm (GA), ant colony optimization (ACO) and quantum-inspired evolutionary algorithm (QEA).
Xu Peng - One of the best experts on this subject based on the ideXlab platform.
-
efficient and reliable multicast routing protocol based on Greedy Strategy
Computer Engineering, 2012Co-Authors: Xu PengAbstract:The vast majority of multicast route protocols are achieved by multicast tree,which ignore some available transmissions of neighbour links after establishing multicast tree.The procession of establishing multicast tree spends much time and space resource,and the whole information of the network is needed.In order to improve the QoS,Greedy Strategy is added to Mesh networks route,does not establish multicast tree and let the most efficient node send data packet in local area.The protocol can make use of the efficient links fully with local area information between neighbour nodes,and distribute achievement.Simulation experimental results show that the protocol has more improvement than Pacifier protocol.
Ali Pezeshki - One of the best experts on this subject based on the ideXlab platform.
-
Submodular optimization problems and Greedy strategies: A survey
Discrete Event Dynamic Systems, 2020Co-Authors: Yajing Liu, Edwin K. P. Chong, Ali Pezeshki, Zhenliang ZhangAbstract:The Greedy Strategy is an approximation algorithm to solve optimization problems arising in decision making with multiple actions. How good is the Greedy Strategy compared to the optimal solution? In this survey, we mainly consider two classes of optimization problems where the objective function is submodular. The first is set submodular optimization, which is to choose a set of actions to optimize a set submodular objective function, and the second is string submodular optimization, which is to choose an ordered set of actions to optimize a string submodular function. Our emphasis here is on performance bounds for the Greedy Strategy in submodular optimization problems. Specifically, we review performance bounds for the Greedy Strategy, more general and improved bounds in terms of curvature, performance bounds for the batched Greedy Strategy, and performance bounds for Nash equilibria.
-
improved bounds for the Greedy Strategy in optimization problems with curvature
Journal of Combinatorial Optimization, 2019Co-Authors: Yajing Liu, Edwin K. P. Chong, Ali PezeshkiAbstract:Consider the problem of choosing a set of actions to optimize a real-valued polymatroid function subject to matroid constraints. The Greedy Strategy, an approximate solution, is known to satisfy some bounds in terms of the total curvature. The total curvature depends on function values on sets outside the constraint matroid. If the function is defined only on the matroid, the problem still makes sense, but the existing bounds involving the total curvature do not apply, which is puzzling. This motivates an alternative formulation of such bounds. The first question we address is whether it is possible to extend a polymatroid function defined on a matroid to one on the entire power set. This was recently shown to be negative in general. Here, we provide necessary and sufficient conditions for the existence of an incremental extension of a polymatroid function defined on the uniform matroid of rank k to one with rank \(k+1\), together with an algorithm for constructing the extension. Whenever a polymatroid function defined on a matroid can be extended to the entire power set, the bounds involving the total curvature of the extension apply. However, these bounds still depend on sets outside the constraint matroid. Motivated by this, we define a new notion of curvature called partial curvature, involving only sets in the matroid. We derive necessary and sufficient conditions for an extension to have a total curvature equal to the partial curvature. Moreover, we prove that the bounds in terms of the partial curvature are in general improved over the previous ones. We illustrate our results with two contrasting examples motivated by practical problems.
-
extending polymatroid set functions with curvature and bounding the Greedy Strategy
IEEE Signal Processing Workshop on Statistical Signal Processing, 2018Co-Authors: Yajing Liu, Edwin K. P. Chong, Ali PezeshkiAbstract:Consider the problem of choosing a set of actions to optimize a real-valued polymatroid function subject to matroid constraints. The Greedy Strategy provides an approximate solution to the optimization problem, and it is known to satisfy some performance bounds in terms of the total curvature. But the total curvature depends on the values of the objective function on sets outside the matroid. If we are given a function defined only on the matroid, the problem still makes sense, but the existing bounds involving the total curvature do not apply. This motivates an alternative formulation of such bounds. We provide necessary and sufficient conditions for the existence of an extension of a polymatroid function defined on the matroid to one defined on the whole power set. Our results give rise to bounds for systems satisfying the necessary and sufficient conditions, which apply to problems where the objective function is defined only on the matroid. When the objective function is defined on the entire power set, the bounds we derive in general improve over the previous ones. To illustrate our results, we present a task scheduling problem.
-
improved bounds for the Greedy Strategy in optimization problems with curvatures
arXiv: Optimization and Control, 2017Co-Authors: Yajing Liu, Edwin K. P. Chong, Ali PezeshkiAbstract:Consider the problem of choosing a set of actions to optimize an objective function that is a real-valued polymatroid function subject to matroid constraints. The Greedy Strategy provides an approximate solution to the optimization problem, and it is known to satisfy some performance bounds in terms of the total curvature. The total curvature depends on the value of objective function on sets outside the constraint matroid. If we are given a function defined only on the matroid, the problem still makes sense, but the existing bounds involving the total curvature do not apply. This is puzzling: If the optimization problem is perfectly well defined, why should the bounds no longer apply? This motivates an alternative formulation of such bounding techniques. The first question that comes to mind is whether it is possible to extend a polymatroid function defined on a matroid to one on the entire power set. This was recently shown to be negative in general. Here, we provide necessary and sufficient conditions for the existence of an \emph{incremental} extension of a polymatroid function defined on the uniform matroid of rank $k$ to one defined on the uniform matroid of rank $k+1$, together with an algorithm for constructing the extension. Whenever a polymatroid objective function defined on a matroid can be extended to the entire power set, the Greedy approximation bounds involving the total curvature of the extension apply. However, these bounds still depend on sets outside the constraint matroid. Motivated by this, we define a new notion of curvature called \emph{partial curvature}, involving only sets in the matroid. We derive necessary and sufficient conditions for an extension of the function to have a total curvature that is equal to the partial curvature. Moreover, we prove that the bounds in terms of the partial curvature are in general improved over the previous ones......
-
Performance bounds for the k-batch Greedy Strategy in optimization problems with curvature
2016 American Control Conference (ACC), 2016Co-Authors: Zhenliang Zhang, Edwin K. P. Chong, Ali PezeshkiAbstract:The k-batch Greedy Strategy is an approximate algorithm to solve optimization problems where the optimal solution is hard to obtain. Starting with the empty set, the k-batch Greedy Strategy adds a batch of k elements to the current solution set with the largest gain in the objective function while satisfying the constraints. In this paper, we bound the performance of the k-batch Greedy Strategy with respect to the optimal Strategy by defining the total curvature αk. We show that when the objective function is nondecreasing and submodular, the k-batch Greedy Strategy satisfies a harmonic bound 1/(1 + αk) for a general matroid constraint and an exponential bound (1 - (1 - αk/t)t/αk for a uniform matroid constraint, where k divides the cardinality of the maximal set in the general matroid, t = K/k is an integer, and K is the rank of the uniform matroid. We also compare the performance of the k-batch Greedy Strategy with that of the k1-batch Greedy Strategy when k1 divides k. Specifically, we prove that when the objective function is nondecreasing and submodular, the k-batch Greedy Strategy has better harmonic and exponential bounds in terms of the total curvature. Finally, we illustrate our results by considering a task-assignment problem.
Hans D. Mittelmann - One of the best experts on this subject based on the ideXlab platform.
-
polynomial time methods to solve unimodular quadratic programs with performance guarantees
IEEE Transactions on Aerospace and Electronic Systems, 2019Co-Authors: Shankarachary Ragi, Edwin K. P. Chong, Hans D. MittelmannAbstract:We develop polynomial-time heuristic methods to solve unimodular quadratic program (UQP) approximately, which is a known non-deterministic polynomial-time hard (NP-hard) problem. Several problems in active sensing and wireless communication applications boil down to UQPs. First, we derive a performance bound for a known UQP approximation method called dominant eigenvector matching heuristic. Next, we present two new polynomial-time heuristic methods inspired from the Greedy Strategy, and we provide performance guarantees for these methods with respect to the optimal objective.
-
Polynomial-Time Methods to Solve Unimodular Quadratic Programs With Performance Guarantees
arXiv: Optimization and Control, 2017Co-Authors: Shankarachary Ragi, Edwin K. P. Chong, Hans D. MittelmannAbstract:We develop polynomial-time heuristic methods to solve unimodular quadratic programs (UQPs) approximately, which are known to be NP-hard. In the UQP framework, we maximize a quadratic function of a vector of complex variables with unit modulus. Several problems in active sensing and wireless communication applications boil down to UQP. With this motivation, we present three new heuristic methods with polynomial-time complexity to solve the UQP approximately. The first method is called dominant-eigenvector-matching; here the solution is picked that matches the complex arguments of the dominant eigenvector of the Hermitian matrix in the UQP formulation. We also provide a performance guarantee for this method. The second method, a Greedy Strategy, is shown to provide a performance guarantee of (1-1/e) with respect to the optimal objective value given that the objective function possesses a property called string submodularity. The third heuristic method is called row-swap Greedy Strategy, which is an extension to the Greedy Strategy and utilizes certain properties of the UQP to provide a better performance than the Greedy Strategy at the expense of an increase in computational complexity. We present numerical results to demonstrate the performance of these heuristic methods, and also compare the performance of these methods against a standard heuristic method called semidefinite relaxation.
