-
作者：Sziklai, Balazs; Fleiner, Tamas; Solymosi, Tamas
作者单位：HUN-REN; HUN-REN Centre for Economic & Regional Studies; Hungarian Academy of Sciences; Corvinus University Budapest; Budapest University of Technology & Economics; Hungarian Academy of Sciences
摘要：We introduce directed acyclic graph (DAG) games, a generalization of standard tree games, to study cost sharing on networks. This structure has not been previously analyzed from a cooperative game theoretic perspective. Every monotonic and subadditive cost game-including monotonic minimum cost spanning tree games-can be modeled as a DAG-game. We provide an efficiently verifiable condition satisfied by a large class of directed acyclic graphs that is sufficient for the balancedness of the assoc...
-
作者：Bernath, Attila; Pap, Gyula
作者单位：Eotvos Lorand University
摘要：The problem of covering minimum cost common bases of two matroids is NP-complete, even if the two matroids coincide, and the costs are all equal to 1. In this paper we show that the following special case is solvable in polynomial time: given a digraph with a designated root node and arc-costs , find a minimum cardinality subset H of the arc set A such that H intersects every minimum c-cost r-arborescence. By an r-arborescence we mean a spanning arborescence of root r. The algorithm we give so...
-
作者：Le Bodic, Pierre; Nemhauser, George
作者单位：Monash University; University System of Georgia; Georgia Institute of Technology
摘要：The selection of branching variables is a key component of branch-and-bound algorithms for solving mixed-integer programming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their LP gains, which is the dual bound improvement obtained after branching on a variable. There are various ways of selecting variables depending on their LP gains. However...
-
作者：Liu, Hongcheng; Yao, Tao; Li, Runze; Ye, Yinyu
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Stanford University
摘要：This paper concerns the folded concave penalized sparse linear regression (FCPSLR), a class of popular sparse recovery methods. Although FCPSLR yields desirable recovery performance when solved globally, computing a global solution is NP-complete. Despite some existing statistical performance analyses on local minimizers or on specific FCPSLR-based learning algorithms, it still remains open questions whether local solutions that are known to admit fully polynomial-time approximation schemes (F...
-
作者：Basu, Amitabh; Hildebrand, Robert; Koppe, Matthias
作者单位：Johns Hopkins University; International Business Machines (IBM); IBM USA; University of California System; University of California Davis
摘要：We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, we present the general regular solution to Cauchy's additive functional equation on restricted lower-dimensional convex domains. This provides a k-dimensional generalization of the so-called Interval Lemma, allowing us to deduce affine properties of the function from certain additivity relations. Next, we study the discrete geometry of additivity domains of pie...
-
作者：Sitters, Rene
作者单位：Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI)
摘要：We show that minimizing the average job completion time on unrelated machines is -hard if preemption of jobs is allowed. This provides one of the last missing pieces in the complexity classification of machine scheduling with (weighted) sum of completion times objective. The proof is based on a mixed integer linear program. This means that verification of the reduction is partly done by an ILP-solver. This gives a concise proof which is easy to verify. In addition, we give a deterministic 1.69...
-
作者：Le Bodic, Pierre; Nemhauser, George
作者单位：Monash University; University System of Georgia; Georgia Institute of Technology
-
作者：Rosat, Samuel; Elhallaoui, Issmail; Soumis, Francois; Lodi, Andrea
作者单位：Universite de Montreal; Universite de Montreal; Polytechnique Montreal
摘要：This paper concentrates on the addition of cutting planes to the integral simplex using decomposition (ISUD) of Zaghrouti et al. (Oper Res 62(2):435-449, 2014). This method solves the set partitioning problem by iteratively improving an existing feasible solution. We present the algorithm in a primal language and relate it to existing augmenting methods. The resulting theoretical properties, stronger than the ones already known, simplify termination proofs and deepen the geometrical insights o...
-
作者：Modaresi, Sina; Vielma, Juan Pablo
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Massachusetts Institute of Technology (MIT)
摘要：In this paper we consider an aggregation technique introduced by YA +/- ldA +/- ran (J Math Control Inf 26:417-450, 2009) to study the convex hull of regions defined by two quadratic inequalities or by a conic quadratic and a quadratic inequality. YA +/- ldA +/- ran (2009) shows how to characterize the convex hull of open sets defined by two strict quadratic inequalities using Linear Matrix Inequalities. We show how this aggregation technique can be easily extended to yield valid conic quadrat...
-
作者：Toriello, Alejandro; Uhan, Nelson A.
作者单位：University System of Georgia; Georgia Institute of Technology; United States Department of Defense; United States Navy; United States Naval Academy
摘要：Motivated by situations in which independent agents wish to cooperate in some uncertain endeavor over time, we study dynamic linear programming games, which generalize classical linear production games to multi-period settings under uncertainty. We specifically consider that players may have risk-averse attitudes towards uncertainty, and model this risk aversion using coherent conditional risk measures. For this setting, we study the strong sequential core, a natural extension of the core to d...
