-
作者：Benedek, Marton; Biro, Peter; Kern, Walter; Palvolgyi, Domotor; Paulusma, Daniel
作者单位：Corvinus University Budapest; University of Twente; Eotvos Lorand University; Durham University
摘要：We introduce partitioned matching games as a suitable model for international kidney exchange programmes, where in each round the total number of available kidney transplants needs to be distributed amongst the participating countries in a fair way. A partitioned matching game (N, v) is defined on a graph G = (V, E) with an edge weighting w and a partition V = V-1 boolean OR center dot center dot center dot boolean OR V-n. The player set is N = {1,..., n}, and player p is an element of N owns ...
-
作者：Santiago, Richard; Sergeev, Ivan; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：The Matroid Secretary Conjecture is a notorious open problem in online optimization. It claims the existence of an O(1)-competitive algorithm for the Matroid Secretary Problem (MSP). Here, the elements of a weighted matroid appear one-by-one, revealing their weight at appearance, and the task is to select elements online with the goal to get an independent set of largest possible weight. O(1)-competitive MSP algorithms have so far only been obtained for restricted matroid classes and for MSP v...
-
作者：Kim, Do Sang; Nguyen, Minh Tung; Pham, Tien-Son
作者单位：Pukyong National University; Ho Chi Minh University of Banking (HUB); Dalat University
摘要：In this work, the notions of normal cones at infinity to unbounded sets and limiting and singular subdifferentials at infinity for extended real value functions are introduced. Various calculus rules for these notions are established. A complete characterization of the Lipschitz continuity at infinity for lower semicontinuous functions is given. The obtained results are aimed ultimately at applications to diverse problems of optimization, such as optimality conditions, coercive properties, wea...
-
作者：Kazachkov, Aleksandr M.; Balas, Egon
作者单位：State University System of Florida; University of Florida; Carnegie Mellon University
摘要：Disjunctive cutting planes can tighten a relaxation of a mixed-integer linear program. Traditionally, such cuts are obtained by solving a higher-dimensional linear program, whose additional variables cause the procedure to be computationally prohibitive. Adopting a nu-polyhedral perspective is a practical alternative that enables the separation of disjunctive cuts via a linear program with only as many variables as the original problem. The drawback is that the classical approach of monoidal s...
-
作者：Del Pia, Alberto; Kaibel, Volker
作者单位：University of Wisconsin System; University of Wisconsin Madison
-
作者：Evens, Brecht; Pas, Pieter; Latafat, Puya; Patrinos, Panagiotis
作者单位：KU Leuven; IMT School for Advanced Studies Lucca
摘要：The proximal point algorithm (PPA) is the most widely recognized method for solving inclusion problems and serves as the foundation for many numerical algorithms. Despite this popularity, its convergence results have been largely limited to the monotone setting. In this work, we study the convergence of (relaxed) preconditioned PPA for a class of nonmonotone problems that satisfy an oblique weak Minty condition. Additionally, we study the (relaxed) Douglas-Rachford splitting (DRS) method in th...
-
作者：Gao, Bin; Peng, Renfeng; Yuan, Ya-xiang
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS
摘要：In the realm of tensor optimization, the low-rank Tucker decomposition is crucial for reducing the number of parameters and for saving storage. We explore the geometry of Tucker tensor varieties-the set of tensors with bounded Tucker rank-which is notably more intricate than the well-explored matrix varieties. We give an explicit parametrization of the tangent cone of Tucker tensor varieties and leverage its geometry to develop provable gradient-related line-search methods for optimization on ...
-
作者：Chandrasekaran, Karthekeyan; Chekuri, Chandra; Fiorini, Samuel; Kulkarni, Shubhang; Weltge, Stefan
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Universite Libre de Bruxelles; Technical University of Munich
摘要：We consider the feedback vertex set problem in undirected graphs (FVS). The input to FVS is an undirected graph G=(V,E) with non-negative vertex costs. The goal is to find a minimum cost subset of vertices S subset of V such that G-S is acyclic. FVS is a well-known NP-hard problem and does not admit a (2-& varepsilon;)-approximation for any fixed & varepsilon;>0 assuming the Unique Games Conjecture. There are combinatorial 2-approximation algorithms (Bafna et al., in: Algorithms and computatio...
-
作者：Feng, Fuxiaoyue; Ding, Chao; Li, Xudong
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Fudan University
摘要：We introduce a quadratically convergent semismooth Newton method for nonlinear semidefinite programming that eliminates the need for the generalized Jacobian regularity, a common yet stringent requirement in existing approaches. Our strategy involves identifying a single nonsingular element within the Bouligand generalized Jacobian, thus avoiding the standard requirement for nonsingularity across the entire generalized Jacobian set, which is often too restrictive for practical applications. Th...
-
作者：Poremba, Joseph; Shepherd, F. Bruce
作者单位：University of British Columbia
摘要：In multicommodity network flows, a supply-demand graph pair (G, H) (called a multiflow topology) is cut-sufficient if, for all capacity and demand weights, the cut condition is enough to guarantee the existence of a feasible multiflow. We characterize cut-sufficiency for two classes of directed 2-commodity flows: roundtrip demands, where H is a 2-cycle, and 2-path demands, where H is a directed path of length two. We then extend these characterizations to some larger demand graphs, namely dire...
