skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Facets, weak facets, and extreme functions of the Gomory–Johnson infinite group problem
Award ID(s):
2012764 1320051 2012429
PAR ID:
10279694
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Mathematical Programming
Volume:
187
Issue:
1-2
ISSN:
0025-5610
Page Range / eLocation ID:
195 to 252
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Gaussian random polytopes have received a lot of attention, especially in the case where the dimension is fixed and the number of points goes to infinity. Our focus is on the less-studied case where the dimension goes to infinity and the number of points is proportional to the dimensiond. We study several natural quantities associated with Gaussian random polytopes in this setting. First, we show that the expected number of facets is equal to$$C(\alpha)^{d+o(d)}$$, where$$C(\alpha)$$is some constant which depends on the constant of proportionality$$\alpha$$. We also extend this result to the expected number ofk-facets. We then consider the more difficult problem of the asymptotics of the expected number of pairs ofestranged facetsof a Gaussian random polytope. When the number of points is 2d, we determine the constantCsuch that the expected number of pairs of estranged facets is equal to$$C^{d+o(d)}$$. 
    more » « less
  2. Costa, Constantinos; Pitoura, Evaggelia (Ed.)
    Data-driven systems can be unfair, in many different ways. All too often, as data scientists, we focus narrowly on one technical aspect of fairness. In this paper, we attempt to address equity broadly, and identify the many different ways in which it is manifest in data-driven systems. 
    more » « less