Article
Operations Research & Management Science
Manuel Aprile
Summary: This study explores the hitting number of a polytope and its relationship with matroids, providing conclusions on the extended formulation of linear size.
OPERATIONS RESEARCH LETTERS
(2022)
Article
Computer Science, Software Engineering
Yuri Faenza, Gianpaolo Oriolo, Gautier Stauffer
Summary: The paper proposes an algorithmic solution to providing a polynomial-time and computationally attractive separation routine for the stable set polytope of claw-free graphs, avoiding the heavy computational burden of resorting to the ellipsoid method. The separation routine comes with a 'small' extended linear programming formulation and a procedure to derive a linear description of the stable set polytope of claw-free graphs in the original space.
MATHEMATICAL PROGRAMMING
(2021)
Article
Computer Science, Software Engineering
Hiroshi Imai, Keiko Imai, Hidefumi Hiraishi
Summary: In this note, extended formulations of (k,l)-sparsity matroids defined on graphs with n vertices and m edges are investigated, with a focus on interpreting earlier results from the viewpoint of extended formulations. It is shown that when k >= l, the bound is O(mn) and when k < l, a better bound of O(m(2)) is achieved. A unified polymatroidal approach is provided to derive a more general understanding of the topic.
OPTIMIZATION METHODS & SOFTWARE
(2021)
Article
Mathematics, Applied
Guillermo Pineda-Villavicencio, David Yost
Summary: This paper addresses the problem of calculating exact lower bounds for the number of k-faces of dpolytopes with n vertices, for each value of k. The authors have recently solved this problem for n not exceeding 2d and now establish the corresponding result for n = 2d+ 1, showing that the nature of the lower bounds and the minimizing polytopes are quite different in this case. Additionally, they also characterize d-polytopes with d + 3 vertices and only one or two edges more than the minimum.
SIAM JOURNAL ON DISCRETE MATHEMATICS
(2022)
Article
Computer Science, Theory & Methods
Tomasz Kobos
Summary: We establish a uniform lower bound on the norms of all hyperplane projections by using the determinant function of vertices and faces of a centrally symmetric spherical and simplicial polytope. Specifically, for a hyperplane projection P: X -> X, where X is an n-dimensional normed space with a centrally symmetric spherical and simplicial polytope as the unit ball, we prove that ||P(X)|| >= 1 + c(n)N(-(2n2+4n+6)), where N >= n(4n) and x(1), x(2),..., x(N) are independent random points distributed uniformly on the unit sphere. The constant c(n) is explicit and the probability of this inequality holds is at least 1 - 3/N.
DISCRETE & COMPUTATIONAL GEOMETRY
(2023)
Article
Engineering, Electrical & Electronic
Linfeng Yang, Shifei Chen, Zhaoyang Dong
Summary: A systematic approach and framework for unit commitment formulation is proposed in this paper. The approach utilizes locally ideal conceptions to construct strong valid inequalities for multi-period generation polytope subjected to generation condition constraints. The proposed model considers historical unit commitment status and outperforms other commonly used unit commitment models in terms of accuracy and computational cost reduction.
IEEE TRANSACTIONS ON POWER SYSTEMS
(2023)
Article
Physics, Particles & Fields
Shahar Hod
Summary: Using general relativity and quantum field theory, it is shown that the orbital periods of test particles around central compact objects are fundamentally bounded from below. The lower bound on orbital periods becomes universal and can be expressed in terms of fundamental constants of nature. This suggests that it may reflect a fundamental property of the quantum theory of gravity.
EUROPEAN PHYSICAL JOURNAL C
(2023)
Article
Physics, Multidisciplinary
Adam R. Brown
Summary: Differential geometry has a long history in its applications in physics, especially in general relativity and related fields. Recently, Nielsen proposed using the tools of differential geometry to bound the complexity of quantum operations in the unitary group. The Bishop-Gromov bound, a result in differential geometry, gives an upper bound on the growth rate of geodesic ball volumes in terms of Ricci curvature. This paper applies the Bishop-Gromov bound to Nielsen's complexity geometry to establish lower bounds on the quantum complexity of a typical unitary, showing exponential growth in the number of qubits for a broad class of models.
Article
Computer Science, Theory & Methods
Lei Xue
Summary: This paper proves Grunbaum's conjecture from 1967, which states that any d-dimensional polytope with d + s <= 2d vertices has at least [GRAPHICS] k-faces. The paper also establishes several extensions of this result, including the study of lattices with the diamond property and lattices with d + s <= 2d atoms, and provides a characterization of equality cases in certain situations. Additionally, the paper obtains sharp lower bounds on the number of k-faces of certain CW complexes representing normal pseudomanifolds with 2d + 1 vertices, based on the face numbers of corresponding polytopes with 2d + 1 vertices.
DISCRETE & COMPUTATIONAL GEOMETRY
(2023)
Article
Economics
Sophocles Mavroeidis
Summary: The study examines the causal effects of monetary policy due to the zero lower bound on interest rates, suggesting a simple way to test the effectiveness of unconventional policies through a shadow rate model. Applying this method to U.S. monetary policy, it rejects the null hypothesis that unconventional monetary policy has no effect at the ZLB, but indicates it may not be as effective as conventional monetary policy.
Article
Quantum Science & Technology
Leandro R. S. Mendes, Marcos C. de Oliveira
Summary: This paper investigates the lower bound of the strong subadditivity of the von Neumann entropy, which is dependent on the distribution of quantum correlation. It also examines the consequences of the structure of states saturating the bounded subadditivity for the quantum data processing inequality, achieving a lower bound associated with the locally inaccessible information.
QUANTUM INFORMATION PROCESSING
(2022)
Article
Biology
Wenxin Hu, Zhiming Wang, Hongjin Zheng
Summary: The study describes the structure of a bacterial MscS-like channel, YnaI, in its closed state, highlighting the membrane sensor paddle domain and lipid pockets' important roles in mechanosensitive channels.
COMMUNICATIONS BIOLOGY
(2021)
Article
Operations Research & Management Science
Manuel Aprile, Michele Conforti, Marco Di Summa
Summary: A binarization of a bounded variable x is obtained by using linear inequalities involving additional variables y(1), ..., y(t) in [0,1] to imply the integrality of x based on the integrality of y(1), ..., y(t). Binary extended formulations are useful in mixed-integer programming as they impose integrality on 0/1 variables, which has interesting convergence properties. The behavior of binary extended formulations with respect to sequential convexification is studied, particularly in terms of a parameter called rank that measures the progress made in enforcing the integrality of a variable x.
MATHEMATICS OF OPERATIONS RESEARCH
(2023)
Article
Computer Science, Information Systems
Chunyang Wang, Yuping Wang, Xiangjuan Wu, Xiaofang Guo
Summary: This paper proposes a new approach to solve the MLCS problem of multiple sequences, including a time-efficient upper bound estimation method, an adaptive lower bound estimation strategy, and a distributed storage scheme. A comparison with other algorithms demonstrates the efficiency and effectiveness of the proposed method.
INFORMATION SCIENCES
(2022)
Article
Management
Vinicius L. do Forte, Said Hanafi, Abilio Lucena
Summary: In this article, the Perfect Vertex Domination Problem (PVDP) and Perfect Edge Domination Problem (PEDP) are discussed. New formulations for PVDP and PEDP are proposed, utilizing structural properties of perfect dominating sets. The new PEDP formulation shows significant speed-ups compared to the existing formulations. Evaluation of running times using state-of-the-art mixed integer programming codes demonstrates the effectiveness of the new formulation.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Computer Science, Information Systems
David Avis, Hans Raj Tiwary
INFORMATION PROCESSING LETTERS
(2015)
Article
Computer Science, Hardware & Architecture
Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald De Wolf
JOURNAL OF THE ACM
(2015)
Article
Operations Research & Management Science
David Avis, Hans Raj Tiwary
OPTIMIZATION LETTERS
(2017)
Article
Computer Science, Information Systems
Hans Raj Tiwary, Stefan Weltge, Rico Zenklusen
INFORMATION PROCESSING LETTERS
(2017)
Article
Mathematics
David Avis, Hans Raj Tiwary
EUROPEAN JOURNAL OF COMBINATORICS
(2019)
Article
Mathematics, Applied
Jakub Gajarsky, Petr Hlineny, Hans Raj Tiwary
DISCRETE APPLIED MATHEMATICS
(2018)
Article
Mathematics
Hans Raj Tiwary, Khaled Elbassioni
GRAPHS AND COMBINATORICS
(2014)
Article
Physics, Multidisciplinary
Samuel Fiorini, Serge Massar, Manas K. Patra, Hans Raj Tiwary
JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL
(2015)
Article
Computer Science, Software Engineering
David Avis, Hans Raj Tiwary
MATHEMATICAL PROGRAMMING
(2015)
Article
Computer Science, Software Engineering
Yuri Faenza, Samuel Fiorini, Roland Grappe, Hans Raj Tiwary
MATHEMATICAL PROGRAMMING
(2015)
Article
Mathematics, Applied
David Avis, David Bremner, Hans Raj Tiwary, Osamu Watanabe
DISCRETE APPLIED MATHEMATICS
(2019)
Article
Computer Science, Theory & Methods
Hans Raj Tiwary
THEORY OF COMPUTING SYSTEMS
(2020)
Article
Operations Research & Management Science
Hans Raj Tiwary, Victor Verdugo, Andreas Wiese
OPERATIONS RESEARCH LETTERS
(2020)
Proceedings Paper
Computer Science, Theory & Methods
Hans Raj Tiwary
Summary: This article studies the extension complexity of polytope P and its permutation and sorted counterparts, perm(I)(P) and sort(P). The results show that when certain conditions are met, the extension complexity of perm(I)(P) can be expressed as a polynomial of the extension complexity of P; however, when the conditions are not met, the extension complexity of perm(I)(P) and sort(P) can both increase exponentially.
COMBINATORIAL OPTIMIZATION (ISCO 2022)
(2022)
Article
Computer Science, Software Engineering
Petr Kolman, Martin Koutecky, Hans Raj Tiwary
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
(2020)
