-
作者：Thomson, William; Velez, Rodrigo A.
作者单位：University of Rochester
摘要：In a queueing problem , a group of agents are waiting for a service. Each agent incurs a cost of waiting that is proportional to the time they wait. Monetary transfers can take place. We study the subsolutions of the no-envy solution that are anonymous, consistent, conversely consistent, and continuous. We show that there are infinitely many proper consistent subsolutions from the no-envy solution and characterize a class of these solutions on the basis of basic requirements of continuity, ano...
-
作者：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...
-
作者：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.
-
作者：Ahookhosh, Masoud; Nesterov, Yurii
作者单位：University of Antwerp
摘要：We introduce a Bi-level OPTimization (BiOPT) framework for minimizing the sum of two convex functions, where one of them is smooth enough. The BiOPT framework offers three levels of freedom: (i) choosing the order p of the proximal term; (ii) designing an inexact pth-order proximal-point method in the upper level; (iii) solving the auxiliary problem with a lower-level non-Euclidean method in the lower level. We here regularize the objective by a (p+1)\documentclass[12pt]{minimal} \usepackage{a...
-
作者：Abdi, Ahmad; Cornuejols, Gerard; Guenin, Bertrand; Tuncel, Levent
作者单位：University of London; London School Economics & Political Science; Carnegie Mellon University; University of Waterloo
摘要：A vector is dyadic if each of its entries is a dyadic rational number, i.e. of the form (a)/(2)k for some integers a, k with k = 0. A linear system Ax = b with integral data is totally dual dyadic if whenever min{b(T)y : A(T)y = w, y = 0J for w integral, has an optimal solution, it has a dyadic optimal solution. In this paper, we study total dual dyadicness, and give a co-NP characterization of it in terms of dyadic generating sets for cones and subspaces, the former being the dyadic analogue ...
-
作者：Averkov, Gennadiy; Schymura, Matthias
作者单位：Brandenburg University of Technology Cottbus
摘要：We study the maximal number of pairwise distinct columns in a ?-modular integer matrix with m rows. Recent results by Lee et al. provide an asymptotically tight upper bound of O (m(2)) for fixed ?. We complement this and obtain an upper bound of the form O(?) for fixed m, and with the implied constant depending polynomially on m.
