-
作者：Eden, Alon; Feldman, Michal; Fiat, Amos; Goldner, Kira; Karlin, Anna R.
作者单位：Hebrew University of Jerusalem; Tel Aviv University; Boston University; University of Washington; University of Washington Seattle
摘要：. We study combinatorial auctions with interdependent valuations, where each agent i has a private signal si that captures her private information and the valuation func-tion of every agent depends on the entire signal profile, s(s1,:::,sn). The literature in eco-nomics shows that the interdependent model gives rise to strong impossibility results and identifies assumptions under which optimal solutions can be attained. The computer sci-ence literature provides approximation results for simple...
-
作者：Kruk, Lukasz
作者单位：Maria Curie-Sklodowska University
摘要：A single-server queue with renewal arrivals and generally distributed independent and identically distributed service times is considered. Customers are served using the longest remaining time first scheduling algorithm. In case of a tie, processor sharing is utilized. We introduce a fluid model for the evolution of a measure-valued state descriptor of this queue, and we investigate its properties. We also prove a fluid limit theorem justifying our fluid model as the first-order approximation ...
-
作者：Branzei, Simina; Sandomirskiy, Fedor
作者单位：Purdue University System; Purdue University; California Institute of Technology
摘要：We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities when monetary transfers are not allowed. The competitive rule is known for its remarkable fairness and efficiency properties in the case of goods. This rule was extended to chores by Bogomolnaia, Moulin, Sandomirskiy, and Yanovskaya. For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily ...
-
作者：Csoka, Peter; Heringsc, Jean-Jacques
作者单位：Corvinus University Budapest; Tilburg University
摘要：We study bankruptcy problems in financial networks in the presence of general bankruptcy laws. The set of clearing payment matrices is shown to be a lattice, which guarantees the existence of a greatest clearing payment and a least clearing payment. Multiplicity of clearing payment matrices is both a theoretical and a practical concern. We present a new condition for uniqueness that generalizes all the existing conditions proposed in the literature. Our condition depends on the decomposition o...
-
作者：Li, Jiaxiang; Ma, Shiqian; Srivastava, Tejes
作者单位：University of Minnesota System; University of Minnesota Twin Cities; Rice University; University of Chicago
摘要：We consider a class of Riemannian optimization problems where the objective is the sum of a smooth function and a nonsmooth function considered in the ambient space. This class of problems finds important applications in machine learning and statistics, such as sparse principal component analysis, sparse spectral clustering, and orthogonal dictionary learning. We propose a Riemannian alternating direction method of multipliers (ADMM) to solve this class of problems. Our algorithm adopts easily...
-
作者：Charisopoulos, Vasileios; Davis, Damek
作者单位：Cornell University
摘要：Subgradient methods comprise a fundamental class of nonsmooth optimization algorithms. Classical results show that certain subgradient methods converge sublinearly for general Lipschitz convex functions and converge linearly for convex functions that grow sharply away from solutions. Recent work has moreover extended these results to certain nonconvex problems. In this work, we seek to improve the complexity of these algorithms by asking the following question. Is it possible to design a super...
-
作者：Chen, Yiwen; Hare, Warren; Jarry-Bolduc, Gabriel
作者单位：University of British Columbia
摘要：Model-based methods are popular in derivative-free optimization (DFO). In most of them, a single model function is built to approximate the objective function. This is generally based on the assumption that the objective function is one black box. However, some real-life and theoretical problems show that the objective function may consist of sev-eral black boxes. In those problems, the information provided by each black box may not be equal. In this situation, one can build multiple submodels...
-
作者：Zhou, Junpeng; Zhang, Na; Li, Qia
作者单位：Sun Yat Sen University; South China Agricultural University; Sun Yat Sen University
摘要：We consider a class of structured fractional programs, where the numerator is the sum of a block-separable (possibly nonsmooth nonconvex) function and a locally Lipschitz differentiable (possibly nonconvex) function, and the denominator is a convex (possibly nonsmooth) function. We first present a novel reformulation for the original problem and show the relationship of their optimal solutions, critical points, and Kurdyka & Lstrok;ojasiewicz (KL) exponents. Inspired by the reformulation, we p...
-
作者：Naegele, Martin; Zenklusen, Rico
作者单位：University of Bonn; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Short spanning trees subject to additional constraints are important building blocks in various approximation algorithms, and moreover, they capture interesting problem settings on their own. Especially in the context of the traveling salesman problem (TSP), new techniques for finding spanning trees with well-defined properties have been crucial in recent progress. We consider the problem of finding a spanning tree subject to constraints on the edges in a family of cuts forming a laminar famil...
-
作者：Biro, Peter; Klijn, Flip; Klimentova, Xenia; Viana, Ana
作者单位：Corvinus University Budapest; Consejo Superior de Investigaciones Cientificas (CSIC); Barcelona School of Economics; INESC TEC; Instituto Politecnico do Porto
摘要：In a housing market of Shapley and Scarf, each agent is endowed with one indivisible object and has preferences over all objects. An allocation of the objects is in the (strong) core if there exists no (weakly) blocking coalition. We show that, for strict preferences, the unique strong core allocation respects improvement-if an agent's object becomes more desirable for some other agents, then the agent's allotment in the unique strong core allocation weakly improves. We extend this result to w...
