-
作者：Goel, Gagan; Vazirani, Vijay V.
作者单位：Alphabet Inc.; Google Incorporated; University System of Georgia; Georgia Institute of Technology
摘要：Recent results showing PPAD-completeness of the problem of computing an equilibrium for Fisher's market model under additively separable, piecewise-linear, concave (PLC) utilities have dealt a serious blow to the program of obtaining efficient algorithms for computing equilibria in traditional market models, and has prompted a search for alternative models that are realistic as well as amenable to efficient computation. In this paper, we show that introducing perfect price discrimination into ...
-
作者：Ye, Yinyu
作者单位：Stanford University
摘要：We prove that the classic policy-iteration method [Howard, R. A. 1960. Dynamic Programming and Markov Processes. MIT, Cambridge] and the original simplex method with the most-negative-reduced-cost pivoting rule of Dantzig are strongly polynomial-time algorithms for solving the Markov decision problem (MDP) with a fixed discount rate. Furthermore, the computational complexity of the policy-iteration and simplex methods is superior to that of the only known strongly polynomial-time interior-poin...
-
作者：Liu, Yongchao; Xu, Huifu; Ye, Jane J.
作者单位：Dalian Maritime University; University of Southampton; University of Victoria
摘要：This paper considers a one-stage stochastic mathematical program with a complementarity constraint (SMPCC), where uncertainties appear in both the objective function and the complementarity constraint, and an optimal decision on both upper- and lower-level decision variables must be made before the realization of the uncertainties. A partially exactly penalized sample average approximation (SAA) scheme is proposed to solve the problem. Asymptotic convergence of optimal solutions and stationary...
-
作者：Jansen, Klaus; Solis-Oba, Roberto
作者单位：University of Kiel; Western University (University of Western Ontario)
摘要：In the cutting stock problem, we are given a set of objects of different types, and the goal is to pack them all in the minimum possible number of identical bins. All objects have integer lengths, and objects of different types have different sizes. The total length of the objects packed in a bin cannot exceed the capacity of the bin. In this paper, we consider the version of the problem in which the number of different object types is constant, and we present a polynomial-time algorithm that ...
-
作者：Ambuehl, Christoph; Mastrolilli, Monaldo; Mutsanas, Nikolaus; Svensson, Ola
作者单位：University of Liverpool; Universita della Svizzera Italiana; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We consider the single-machine scheduling problem to minimize the weighted sum of completion times under precedence constraints. In a series of recent papers, it was established that this scheduling problem is a special case of minimum weighted vertex cover. In this paper, we show that the vertex cover graph associated with the scheduling problem is exactly the graph of incomparable pairs defined in the dimension theory of partial orders. Exploiting this relationship allows us to present a fra...
-
作者：Averkov, Gennadiy; Wagner, Christian; Weismantel, Robert
作者单位：Otto von Guericke University; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：A convex set with nonempty interior is maximal lattice-free if it is inclusion maximal with respect to the property of not containing integer points in its interior. Maximal lattice-free convex sets are known to be polyhedra. The precision of a rational polyhedron P in R-d is the smallest natural number s such that sP is an integral polyhedron. In this paper we show that, up to affine mappings preserving Z(d), the number of maximal lattice-free rational polyhedra of a given precision s is fini...
-
作者：Kabadi, Santosh N.; Punnen, Abraham P.
作者单位：University of New Brunswick; Simon Fraser University
摘要：An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, the QAP and LAP objective function values are identical. Several sufficiency conditions are known that guarantee linearizability of a QAP. However, no polynomial time algorithm is known to test if a given instance of QAP is linearizable. In this paper, we give a necessary and suff...
-
作者：Chang, Mou-Hsiung; Pang, Tao; Yang, Yipeng
作者单位：North Carolina State University; University of Missouri System; University of Missouri Columbia
摘要：This paper considers a portfolio management problem of Merton's type in which the risky asset return is related to the return history. The problem is modeled by a stochastic system with delay. The investor's goal is to choose the investment control as well as the consumption control to maximize his total expected, discounted utility. Under certain situations, we derive the explicit solutions in a finite dimensional space.
-
作者：Deng, Xiaotie; Qi, Qi; Saberi, Amin; Zhang, Jie
作者单位：University of Liverpool; Stanford University; City University of Hong Kong
摘要：We study three discrete fixed point concept (SPERNER, DPZP, BROUWER) under two different models: the polynomial-time function model and the oracle function model. We fully characterize the computational complexities of these three problems. The computational complexity unification of the above problems gives us more choices in the study of different applications. As an example, by a reduction from DPZP, we derive asymptotically equal lower and upper bound for TUCKER in the oracle model. The sa...
