-
作者：Giner, Emmanuel; Penot, Jean-Paul
作者单位：Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Paris Cite; Sorbonne Universite
摘要：We examine how the subdifferentials of nonconvex integral functionals can be deduced from the subdifferentials of the corresponding integrand or at least be estimated with the help of them. In fact, assuming some regularity properties of the integrands, we obtain exact expressions for the subdifferentials of the integral functionals. We draw some consequences in terms of duality for such integral functionals, extending in this way the early work of Rockafellar to the nonconvex case.
-
作者：Braun, Gabor; Pokutta, Sebastian; Roy, Aurko
作者单位：University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology
摘要：We generalize the reduction mechanism for linear programming problems and semidefinite programming problems from Braun et al. (Inapproximability of combinatorial problems via small LPs and SDPs, 2015) in two ways (1) relaxing the requirement of affineness, and (2) extending to fractional optimization problems. As applications we provide several new LP-hardness and SDP-hardness results, e.g., for the SparsestCut problem, the BalancedSeparator problem, and the MaxCut problem and show how to exte...
-
作者：Svensson, Ola; Tarnawski, Jakub; Vegh, Laszlo A.
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of London; London School Economics & Political Science
摘要：We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we s...
-
作者：Cseh, Agnes; Kavitha, Telikepalli
作者单位：Hungarian Academy of Sciences; Corvinus University Budapest; Tata Institute of Fundamental Research (TIFR)
摘要：Given a bipartite graph G = (A. B, E) with strict preference lists and given an edge e *. E, we ask if there exists a popular matching in G that contains e *. We call this the popular edge problem. Amatching M is popular if there is no matching M such that the vertices that prefer M to M outnumber those that prefer M to M . It is known that every stable matching is popular; however G may have no stable matching with the edge e *. In this paper we identify another natural subclass of popular ma...
-
作者：Adam, Lukas; Henrion, Rene; Outrata, Jiri
作者单位：Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics
摘要：Depending on whether a mathematical program with equilibrium constraints (MPEC) is considered in its original or its enhanced (via KKT conditions) form, the assumed qualification conditions as well as the derived necessary optimality conditions may differ significantly. In this paper, we study this issue when imposing one of the weakest possible qualification conditions, namely the calmness of the perturbation mapping associated with the respective generalized equations in both forms of the MP...
-
作者：Del Pia, Alberto
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：Concave mixed- integer quadratic programming is the problem of minimizing a concave quadratic polynomial over the mixed- integer points in a polyhedral region. In this work we describe an algorithm that finds an - approximate solution to a concave mixed- integer quadratic programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in 1/ , provided that the number of integer variables and the number of negative eigenvalues of the objective functi...
-
作者：Ioffe, Alexander D.
作者单位：Technion Israel Institute of Technology
摘要：The results on regularity behavior of solutions to variational inequalities over polyhedral sets proved in a series of papers by Robinson, Ralph and Dontchev-Rockafellar in the 90s has long become classics of variational analysis. But the available proofs are very complicated and practically do not use techniques of variational analysis. The only exception is the proof by Dontchev and Rockafellar of their critical face regularity criterion. In the paper we offer a different approach completely...
-
作者：Kim, Youngdae; Huber, Olivier; Ferris, Michael C.
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：Affine variational inequalities (AVI) are an important problem class that subsumes systems of linear equations, linear complementarity problems and optimality conditions for quadratic programs. This paper describes PathAVI, a structure-preserving pivotal approach, that can efficiently process (solve or determine infeasible) large-scale sparse instances of the problem with theoretical guarantees and at high accuracy. PathAVI implements a strategy known to process models with good theoretical pr...
-
作者：Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim
作者单位：Max Planck Society; Maastricht University; University of Bonn; University of Wurzburg
摘要：We study the classical NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/MaxNDP is currently not well understood; the best known lower bound is 2(Omega(root log n)), assuming NP not subset of DTIME(n(O(log n))). This constitutes a significant gap to the best known approximation upper bound of O(root n) due to Chekuri et al. (Theo...
-
作者：Gottschalk, Corinna; Koster, Arie M. C. A.; Liers, Frauke; Peis, Britta; Schmand, Daniel; Wierz, Andreas
作者单位：RWTH Aachen University; RWTH Aachen University; University of Erlangen Nuremberg
摘要：We study dynamic network flows with uncertain input data under a robust optimization perspective. In the dynamic maximum flow problem, the goal is to maximize the flow reaching the sink within a given time horizon T, while flow requires a certain travel time to traverse an edge. In our setting, we account for uncertain travel times of flow. We investigate maximum flows over time under the assumption that at most travel times may be prolonged simultaneously due to delay. We develop and study a ...
