Mathematics of Operations Research
SCIE-ISI SCOPUS (1976-1989,1995-2023)
1526-5471
0364-765X
Mỹ
Cơ quản chủ quản: INFORMS Institute for Operations Research and the Management Sciences , INFORMS
Lĩnh vực:
Mathematics (miscellaneous)Management Science and Operations ResearchComputer Science Applications
Các bài báo tiêu biểu
Optimal Auction Design This paper considers the problem faced by a seller who has a single object to sell to one of several possible buyers, when the seller has imperfect information about how much the buyers might be willing to pay for the object. The seller's problem is to design an auction game which has a Nash equilibrium giving him the highest possible expected utility. Optimal auctions are derived in this... ... hiện toàn bộ
Tập 6 Số 1 - Trang 58-73 - 1981
A Greedy Heuristic for the Set-Covering Problem Let A be a binary matrix of size m × n, let cT be a positive row vector of length n and let e be the column vector, all of whose m components are ones. The set-covering problem is to minimize cT x subject to Ax ≥ e and x binary. We compare the value of the objective function at a feasible solution found by a simple greedy heuristic to the true opti... ... hiện toàn bộ
Tập 4 Số 3 - Trang 233-235 - 1979
Robust Convex Optimization We study convex optimization problems for which the data is not specified exactly and it is only known to belong to a given uncertainty set U, yet the constraints must hold for all possible values of the data from U. The ensuing optimization problem is called robust optimization. In this paper we lay the foundation of robust convex optimization. In the main part of the paper we show that ... ... hiện toàn bộ
Tập 23 Số 4 - Trang 769-805 - 1998
The Complexity of Flowshop and Jobshop Scheduling NP-complete problems form an extensive equivalence class of combinatorial problems for which no nonenumerative algorithms are known. Our first result shows that determining a shortest-length schedule in an m-machine flowshop is NP-complete for m ≥ 3. (For m = 2, there is an efficient algorithm for finding such schedules.) The second result shows that determining a minimum mean-flow-time s... ... hiện toàn bộ
Tập 1 Số 2 - Trang 117-129 - 1976
Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming The theory of the proximal point algorithm for maximal monotone operators is applied to three algorithms for solving convex programs, one of which has not previously been formulated. Rate-of-convergence results for the “method of multipliers,” of the strong sort already known, are derived in a generalized form relevant also to problems beyond the compass of the standard second-order condi... ... hiện toàn bộ
Tập 1 Số 2 - Trang 97-116 - 1976
Minimizing Total Tardiness on One Machine is NP-Hard The problem of minimizing the total tardiness for a set of independent jobs on one machine is considered. Lawler has given a pseudo-polynomial-time algorithm to solve this problem. In spite of extensive research efforts for more than a decade, the question of whether it can be solved in polynomial time or it is NP-hard (in the ordinary sense) remained open. In this paper the problem is sh... ... hiện toàn bộ
Tập 15 Số 3 - Trang 483-495 - 1990
Best Algorithms for Approximating the Maximum of a Submodular Set Function A real-valued function z whose domain is all of the subsets of N = {1, …, n) is said to be submodular if z(S) + z(T) ≥ z(S ∪ T) + z(S ∩ T), ∀S, T ⊆ N, and nondecreasing if z(S) ≤ z(T), ∀S ⊂ T ⊆ N. We consider the problem maxS⊂N {z(S): |S| ≤ K, z submodular and nondecreasing, z(Ø) = 0}. Many combinatorial optimization problems can be posed in this fra... ... hiện toàn bộ
Tập 3 Số 3 - Trang 177-188 - 1978
Robust Dynamic ProgrammingIn this paper we propose a robust formulation for discrete time dynamic programming (DP). The objective of the robust formulation is to systematically mitigate the sensitivity of the DP optimal policy to ambiguity in the underlying transition probabilities. The ambiguity is modeled by associating a set of conditional measures with each state-action pair. Consequently, in the robust formula... ... hiện toàn bộ
Tập 30 Số 2 - Trang 257-280 - 2005
A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming Sherali and Adams (1990), Lovász and Schrijver (1991) and, recently, Lasserre (2001b) have constructed hierarchies of successive linear or semidefinite relaxations of a 0–1 polytope P ⫅ ℝn converging to P in n steps. Lasserre's approach uses results about representations of positive polynomials as sums of squares and the dual theory of moments. We present the three me... ... hiện toàn bộ
Tập 28 Số 3 - Trang 470-496 - 2003
Finding Minimum-Cost Circulations by Successive Approximation We develop a new approach to solving minimum-cost circulation problems. Our approach combines methods for solving the maximum flow problem with successive approximation techniques based on cost scaling. We measure the accuracy of a solution by the amount that the complementary slackness conditions are violated. We propose a simple minimum-cost circulation algorithm, one ... ... hiện toàn bộ
Tập 15 Số 3 - Trang 430-466 - 1990