-
作者：Jaillet, Patrick; Lu, Xin
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider variants of the online stochastic bipartite matching problem motivated by Internet advertising display applications, as introduced in Feldman et al. [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 - 1/e. FOCS '09: Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Washington, DC), 117-126]. In this setting, advertisers express specific interests into requests for impressions of different types. Advertisers are fixed and kno...
-
作者：Li, Yanjun
作者单位：Purdue University System; Purdue University
摘要：Given a simple and undirected graph, nonnegative node weights, a nonnegative integer j, and a positive integer k, a k-matching in the graph is a subgraph with no isolated nodes and with maximum degree no more than k, a j-restricted k-matching is a k-matching with each connected component having at least j + 1 edges, and the total node weight of a j-restricted k-matching is the total weight of the nodes covered by the edges in the j-restricted k-matching. When j = 1 and k = 2, Kaneko [Kaneko A ...
-
作者：Eaves, B. Curtis; Rothblum, Uriel G.
作者单位：Stanford University; Technion Israel Institute of Technology
摘要：A linear problem is completely solved by a randomizing linear algorithm if the set of data-solution pairs of the problem equals the set of input-output pairs of the algorithm over all randomizations. Linear problems are based on the predicate language over ordered fields. This class contains, for example, all linear programs, all bounded variable integer programs, all satisfiability problems in sentential logic, and models of conflict. Randomizing linear algorithms are based on a tree, arithme...
-
作者：Jiang, Bo; He, Simai; Li, Zhening; Zhang, Shuzhong
作者单位：University of Minnesota System; University of Minnesota Twin Cities; City University of Hong Kong; University of Portsmouth
摘要：In this paper, we introduce a notion to be called k-wise uncorrelated random variables, which is similar but not identical to the so-called k-wise independent random variables in the literature. We show how to construct k-wise uncorrelated random variables by a simple procedure. The constructed random variables can be applied, e.g., to express the quartic polynomial (x(T)Qx)(2), where Q is an n x n positive semidefinite matrix, by a sum of fourth powered polynomial terms, known as Hilbert's id...
-
作者：Ok, Efe A.; Riella, Gil
作者单位：New York University; Universidade de Brasilia
摘要：Our primary query is to find conditions under which the closure of a preorder on a topological space remains transitive. We study this problem for translation invariant preorders on topological groups. The results are fairly positive; we find that the closure of preorders and normal orders remain as such in this context. The same is true for factor orders as well under quite general conditions. In turn, in the context of topological linear spaces, these results allow us to obtain a simple cond...
-
作者：den Boer, Arnoud V.
作者单位：University of Twente
摘要：We study a dynamic pricing problem with multiple products and infinite inventories. The demand for these products depends on the selling prices and on parameters unknown to the seller. Their value can be learned from accumulating sales data using statistical estimation techniques. The quality of the parameter estimates is influenced by the amount of price dispersion; however, a large amount of variation in the selling prices can be costly since it means that suboptimal prices are used. The sel...
-
作者：Saari, Donald G.
作者单位：University of California System; University of California Irvine
摘要：The importance of paired comparisons has led to the development of several approaches. Missing is a common analytical way to compare techniques and explain properties. To do so, the approach developed here creates a data space coordinate system where data aspects that satisfy a strong transitivity condition are separated from those that represent noise as characterized by cyclic effects. With this system, paired comparison rules can be compared and paradoxical behavior explained.
-
作者：Eirinakis, Pavlos; Magos, Dimitrios; Mourtos, Ioannis; Miliotis, Panayiotis
作者单位：Athens University of Economics & Business; University of West Attica
摘要：In the setting of the stable matching (SM) problem, it has been observed that some of the man-woman pairs cannot be removed although they participate in no stable matching, since such a removal would alter the set of solutions. These pairs are yet to be identified. Likewise (and despite the sizeable literature), some of the fundamental characteristics of the SM polytope (e.g., its dimension, its facets, etc.) have not been established. In the current work, we show that these two seemingly dist...
-
作者：Chen, Ning; Gravin, Nick; Lu, Pinyan
作者单位：Nanyang Technological University; Microsoft; Microsoft Research Asia; Microsoft; Microsoft China
摘要：In the generalized assignment problem (gap), a set of jobs seek to be assigned to a set of machines. For every job-machine pair, there are a specific value and an accommodated capacity for the assignment. The objective is to find an assignment that maximizes the total sum of values given that the capacity constraint of every machine is satisfied. The GAP is a classic optimization problem and has been studied extensively from the algorithmic perspective. Dughmi and Ghosh [Dughmi S, Ghosh A (201...
-
作者：Aardal, Karen; von Heymann, Frederik
作者单位：Delft University of Technology; University of Cologne
摘要：Lattice-based reformulation techniques have been used successfully both theoretically and computationally. One such reformulation is obtained from the kernel lattice associated with an input matrix. Some of the hard instances in the literature that have been successfully tackled by lattice-based techniques have randomly generated input. Since the considered instances are very hard even in low dimension, less experience is available for larger instances. Recently, we have studied larger instanc...
