-
作者：Brosch, Daniel; Polak, Sven C.
作者单位：University of Klagenfurt; Tilburg University
摘要：In this paper, we use semidefinite programming and representation theory to compute new lower bounds on the crossing number of the complete bipartite graph K-m,K-n, extending a method from de Klerk et al. [SIAM J. Discrete Math. 20 (2006), 189--202] and the subsequent reduction by De Klerk, Pasechnik and Schrijver [Math. Prog. Ser. A and B, 109 (2007) 613--624]. We exploit the full symmetry of the problem using a novel decomposition technique. This results in a full block-diagonalization of th...
-
作者：Iwamasa, Yuni
作者单位：Kyoto University
摘要：In this paper, we consider the problem of computing the entire sequence of the maximum degree of minors of a block-structured symbolic matrix (a generic partitioned polynomial matrix) A = ( Aa ss xa ss t(da ss)), where A(a ss) is a 2x2 matrix over a field F, x(a ss) is an indeterminate, and d(a ss) is an integer for a = 1, 2,..., mu and ss = 1, 2,...,., and t is an additional indeterminate. This problem can be viewed as an algebraic generalization of the maximum weight bipartite matching probl...
-
作者：Del Pia, Alberto; Linderoth, Jeff; Zhu, Haoran
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We close three open problems on the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cover inequalities, (1, k)-configuration inequalities, and weight inequalities are all NP-complete. We also show that, when the number of constraints of the LP relaxation is constant and its optimal solution is an extreme point, then the separation problems of both extended cover inequalities and weight inequalities can ...
-
作者：Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin
作者单位：Technical University of Berlin; University of Warwick; University of Virginia; Uppsala University; Technische Universitat Wien
摘要：In the late 19th century, Swedish mathematician Edvard Phragmen proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants-one minimizing the maximum load and one minimizing the variance of loads-and a sequential variant. We study Phragmen 's methods from an axiomatic point of view, focusing on properties capturing proportional representation. We show that the sequential...
-
作者：Brill, Markus; Golz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai
作者单位：Technical University of Berlin; Carnegie Mellon University; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine
摘要：In the apportionment problem, a fixed number of seats must be distributed among parties in proportion to the number of voters supporting each party. We study a generalization of this setting, in which voters can support multiple parties by casting approval ballots. This approval-based apportionment setting generalizes traditional apportionment and is a natural restriction of approval-based multiwinner elections, where approval ballots range over individual candidates instead of parties. Using ...
-
作者：Khan, Arindam; Subramanian, Aditya; Wiese, Andreas
作者单位：Indian Institute of Science (IISC) - Bangalore; Technical University of Munich
摘要：We study rectangle stabbing problems in which we are given n axis-aligned rectangles in the plane that we want to stab, that is, we want to select line segments such that for each given rectangle there is a line segment that intersects two opposite edges of it. In the horizontal rectangle stabbing problem (Stabbing), the goal is to find a set of horizontal line segments of minimum total length such that all rectangles are stabbed. In the horizontal-vertical stabbing problem (HV-Stabbing), the ...
-
作者：Brianski, Marcin; Koutecky, Martin; Kral, Daniel; Pekarkova, Kristyna; Schroder, Felix
作者单位：Jagiellonian University; Charles University Prague; Masaryk University; Charles University Prague
摘要：An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of A, and when parameterized by the dual tree-depth and the entry complexity of A; both these parameterization imply that A is sparse, in particul...
-
作者：Del Pia, Alberto; Khajavirad, Aida
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Lehigh University
摘要：We consider the multilinear polytope defined as the convex hull of the set of binary points z, satisfying a collection of equations of the form z(e) = Pi (upsilon is an element of e) z(upsilon) for all e is an element of E. The complexity of the facial structure of the multilinear polytope is closely related to the acyclicity degree of the underlying hypergraph. We obtain a polynomial-size extended formulation for the multilinear polytope of ss-acyclic hypergraphs, hence characterizing the acy...
-
作者：Zhang, Haixiang; Yalcin, Baturalp; Lavaei, Javad; Sojoudi, Somayeh
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：In this work, we develop a new complexity metric for an important class of low-rank matrix optimization problems in both symmetric and asymmetric cases, where the metric aims to quantify the complexity of the nonconvex optimization landscape of each problem and the success of local search methods in solving the problem. The existing literature has focused on two recovery guarantees. The RIP constant is commonly used to characterize the complexity of matrix sensing problems. On the other hand, ...
-
作者：Grimmer, Benjamin
作者单位：Johns Hopkins University
摘要：The first part of this work established the foundations of a radial duality between nonnegative optimization problems, inspired by the work of Renegar (SIAM J Optim 26(4): 2649-2676, 2016). Here we utilize our radial duality theory to design and analyze projection-free optimization algorithms that operate by solving a radially dual problem. In particular, we consider radial subgradient, smoothing, and accelerated methods that are capable of solving a range of constrained convex and nonconvex o...
