排序方式: 共有6条查询结果,搜索用时 15 毫秒
1
1.
Adam Kurpisz Monaldo Mastrolilli Claire Mathieu Tobias Mömke Victor Verdugo Andreas Wiese 《Mathematical Programming》2018,172(1-2):231-248
Sherali and Adams (SIAM J Discrete Math 3:411–430, 1990) and Lovász and Schrijver (SIAM J Optim 1:166–190, 1991) developed systematic procedures to construct the hierarchies of relaxations known as lift-and-project methods. They have been proven to be a strong tool for developing approximation algorithms, matching the best relaxations known for problems like Max-Cut and Sparsest-Cut. In this work we provide lower bounds for these hierarchies when applied over the configuration LP for the problem of scheduling identical machines to minimize the makespan. First we show that the configuration LP has an integrality gap of at least 1024/1023 by providing a family of instances with 15 different job sizes. Then we show that for any integer n there is an instance with n jobs in this family such that after \(\varOmega (n)\) rounds of the Sherali–Adams (\(\text {SA}\)) or the Lovász–Schrijver (\(\text {LS}_+\)) hierarchy the integrality gap remains at least 1024/1023. 相似文献
2.
Monaldo Mastrolilli 《Operations Research Letters》2010,38(5):390-395
We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal-dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than 6/5 if P≠NP, or strictly less than 4/3 if the Unique Games Conjecture also holds. 相似文献
3.
4.
In this expository article, we study optimization problems specified via linear and relative entropy inequalities. Such relative entropy programs (REPs) are convex optimization problems as the relative entropy function is jointly convex with respect to both its arguments. Prominent families of convex programs such as geometric programs (GPs), second-order cone programs, and entropy maximization problems are special cases of REPs, although REPs are more general than these classes of problems. We provide solutions based on REPs to a range of problems such as permanent maximization, robust optimization formulations of GPs, and hitting-time estimation in dynamical systems. We survey previous approaches to some of these problems and the limitations of those methods, and we highlight the more powerful generalizations afforded by REPs. We conclude with a discussion of quantum analogs of the relative entropy function, including a review of the similarities and distinctions with respect to the classical case. We also describe a stylized application of quantum relative entropy optimization that exploits the joint convexity of the quantum relative entropy function. 相似文献
5.
Monaldo Mastrolilli 《Discrete Applied Mathematics》2006,154(4):640-649
We address the classical knapsack problem and a variant in which an upper bound is imposed on the number of items that can be selected. We show that appropriate combinations of rounding techniques yield novel and more powerful ways of rounding. Moreover, we present a linear-storage polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS) that compute an approximate solution, of any fixed accuracy, in linear time. These linear complexity bounds give a substantial improvement of the best previously known polynomial bounds [A. Caprara, et al., Approximation algorithms for knapsack problems with cardinality constraints, European J. Oper. Res. 123 (2000) 333-345]. 相似文献
6.
Leonora Bianchi Mauro Birattari Marco Chiarandini Max Manfrin Monaldo Mastrolilli Luis Paquete Olivia Rossi-Doria Tommaso Schiavinotto 《Journal of Mathematical Modelling and Algorithms》2006,5(1):91-110
This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The
problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances
are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended
exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly
helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related
problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized
solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that,
for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions
than state-of-the-art algorithms. 相似文献
1