-
作者：Bian, Wei; Chen, Xiaojun
作者单位：Harbin Institute of Technology; Hong Kong Polytechnic University
摘要：In this paper, we focus on a class of convexly constrained nonsmooth convex-concave saddle point problems with cardinality penalties. Although such nonsmooth nonconvex-nonconcave and discontinuous min-max problems may not have a saddle point, we show that they have a local saddle point and a global minimax point, and some local saddle points have the lower bound properties. We define a class of strong local saddle points based on the lower bound properties for stability of variable selection. ...
-
作者：Drees, Martin
作者单位：University of Bonn
摘要：A clutter is a family of sets, called members, such that no member contains another. It is called intersecting if every two members intersect, but not all members have a common element. Dense clutters additionally do not have a fractional packing of value 2. We are looking at certain substructures of clutters, namely minors and restrictions. For a family of clutters we introduce a general sufficient condition such that for every clutter we can decide whether the clutter has a restriction in th...
-
作者：Kimura, Kei; Nakayama, Kotaro
作者单位：Kyushu University
摘要：For an integer linear optimization (ILO) problem, persistency of its linear optimization (LO) relaxation is a property that for every optimal solution of the relaxation that assigns integer values to some variables, there exists an optimal solution of the ILO problem in which these variables retain the same values. Although persistency has been used to develop heuristic, approximation, and fixed-parameter algorithms for special cases of ILO, its applicability remains unknown in the literature....
-
作者：Bui, Quang Minh; Carvalho, Margarida; Neto, Jose
作者单位：Universite de Montreal; Universite de Montreal; IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom SudParis
摘要：The network pricing problem (NPP) is a bilevel problem, where the leader optimizes its revenue by deciding on the prices of certain arcs in a graph, while expecting the followers (also known as the commodities) to choose a shortest path based on those prices. In this paper, we investigate the complexity of the NPP with respect to two parameters: the number of tolled arcs, and the number of commodities. We devise a simple algorithm showing that if the number of tolled arcs is fixed, then the pr...
-
作者：Grimmer, Benjamin
作者单位：Johns Hopkins University
摘要：Renegar (SIAM J Optim 26(4):2649-2676, https://doi.org/10.1137/15M1027371 2016) introduced a novel approach to transforming generic conic optimization problems into unconstrained, uniformly Lipschitz continuous minimization. We introduce radial transformations generalizing these ideas, equipped with an entirely new motivation and development that avoids any reliance on convex cones or functions. Of practical importance, this facilitates the development of new families of projection-free first-...
-
作者：Behling, Roger; Bello-Cruz, Yunier; Iusem, Alfredo N. N.; Santos, Luiz-Rafael
作者单位：Getulio Vargas Foundation; Northern Illinois University; Universidade Federal de Santa Catarina (UFSC)
摘要：This paper is devoted to deriving the first circumcenter iteration scheme that does not employ a product space reformulation for finding a point in the intersection of two closed convex sets. We introduce a so-called centralized version of the circumcentered-reflection method (CRM). Developed with the aim of accelerating classical projection algorithms, CRM is successful for tracking a common point of a finite number of affine sets. In the case of general convex sets, CRM was shown to possibly...
-
作者：Smeulders, B.; Blom, D. A. M. P.; Spieksma, F. C. R.
作者单位：Eindhoven University of Technology
摘要：In Kidney Exchange Games, agents (e.g. hospitals or national organizations) have control over a number of incompatible recipient-donor pairs whose recipients are in need of a transplant. Each agent has the opportunity to join a collaborative effort which aims to maximize the total number of transplants that can be realized. However, the individual agent is only interested in maximizing the number of transplants within the set of recipients under its control. Then, the question becomes: which r...
-
作者：Balinski, Michel; Ramirez, Victoriano
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Centre National de la Recherche Scientifique (CNRS); University of Granada
摘要：Several different arguments support the use of Webster's method when seats in a parliament are to be apportioned proportionally according to populations. This note-instigated by a new property-summarizes the reasons.
-
作者：Gonzalez-Rodriguez, Brais; Froger, Aurelien; Jabali, Ola; Naoum-Sawaya, Joe
作者单位：Western University (University of Western Ontario); Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Bordeaux; Inria; Polytechnic University of Milan; Universite de Montreal; HEC Montreal
摘要：Establishing the size of an EV fleet is a vital decision for logistics operators. In urban settings, this issue is often dealt with by partitioning the geographical area around a depot into service zones, each served by a single vehicle. Such zones ultimately guide daily routing decisions. We study the problem of determining the optimal partitioning of an urban logistics area served by EVs. We cast this problem in a Continuous Approximation (CA) framework. Considering a ring radial region with...
-
作者：Cela, Eranda; Klinz, Bettina; Lendl, Stefan; Woeginger, Gerhard J.; Wulf, Lasse
作者单位：Graz University of Technology; University of Graz; RWTH Aachen University
摘要：An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides whether a given QSPP instance is linearizable and determines the corresponding SPP instance in the positive case. We provide a novel linear time algorithm for the LinQSPP on acyclic digraphs which runs considerably faster than the previously best...
