HKU Scholars Hubhttp://hub.hku.hkThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Tue, 05 Nov 2024 22:46:42 GMT2024-11-05T22:46:42Z50701- Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroidshttp://hdl.handle.net/10722/241683Title: Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids
Authors: Chan, HTH; Huang, Z; Jiang, S; Kang, N; Tang, Z
Abstract: We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm maintains a feasible set that is independent in the underlying matroid. In each round when a new element arrives, the algorithm may accept the new element into its feasible set and possibly remove elements from it, provided that the resulting set is still independent. The goal is to maximize the value of the final feasible set under some monotone submodular function, to which the algorithm has oracle access.
For k-uniform matroids, we give a deterministic algorithm with competitive ratio at least 0.2959, and the ratio approaches 1/α∞ ≈ 0.3178 as k approaches infinity, improving the previous best ratio of 0.25 by Chakrabarti and Kale (IPCO 2014), Buchbinder et al. (SODA 2015) and Chekuri et al. (ICALP 2015). We also show that our algorithm is optimal among a class of deterministic monotone algorithms that accept a new arriving element only if the objective is strictly increased.
Further, we prove that no deterministic monotone algorithm can be strictly better than 0.25-competitive even for partition matroids, the most modest generalization of k-uniform matroids, matching the competitive ratio by Chakrabarti and Kale (IPCO 2014) and Chekuri et al. (ICALP 2015). Interestingly, we show that randomized algorithms are strictly more powerful by giving a (non-monotone) randomized algorithm for partition matroids with ratio 1/α∞ ≈ 0.3178.
Finally, our techniques can be extended to a more general problem that generalizes both the online sub-modular maximization problem and the online bipartite matching problem with free disposal. Using the techniques developed in this paper, we give constant-competitive algorithms for the submodular online bipartite matching problem.
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/10722/2416832017-01-01T00:00:00Z
- How to match when all vertices arrive onlinehttp://hdl.handle.net/10722/260345Title: How to match when all vertices arrive online
Authors: Huang, Z; Kang, N; Tang, Z; Wu, X; Zhang, Y; Zhu, X
Abstract: We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously-arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors’ arrivals. If a vertex remains unmatched until its deadline, the algorithm must then irrevocably either match it to an unmatched neighbor, or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, etc. We show that the Ranking algorithm by Karp et al. (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step towards solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is between 0.5541 and 0.5671. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317 < 1−1/e-competitive in our model even for bipartite graphs.
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/10722/2603452018-01-01T00:00:00Z
- Optimal Differentially Private Algorithms for k-Means Clusteringhttp://hdl.handle.net/10722/260346Title: Optimal Differentially Private Algorithms for k-Means Clustering
Authors: Huang, Z; Liu, J
Abstract: We consider privacy-preserving k-means clustering. For the objective of minimizing the Wasserstein distance between the output and the optimal solution, we show that there is a polynomial-time (ε,δ)-differentially private algorithm which, for any sufficiently large Φ2 well-separated datasets, outputs k centers that are within Wasserstein distance Ø(Φ2) from the optimal. This result improves the previous bounds by removing the dependence on ε, number of centers k, and dimension d. Further, we prove a matching lower bound that no (ε, δ)-differentially private algorithm can guarantee Wasserstein distance less than Ømega (Φ2) and, thus, our positive result is optimal up to a constant factor. For minimizing the k-means objective when the dimension d is bounded, we propose a polynomial-time private local search algorithm that outputs an αn-additive approximation when the size of the dataset is at least ~Ø (k3/2 · d · ε-1 · poly(α-1)).
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/10722/2603462018-01-01T00:00:00Z
- Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivalshttp://hdl.handle.net/10722/261433Title: Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals
Authors: Huang, Z; Tang, Z; Wu, X; Zhang, Y
Abstract: We introduce a weighted version of the ranking algorithm by Karp et al. (STOC 1990), and prove a competitive ratio of 0.6534 for the vertex-weighted online bipartite matching problem when online vertices arrive in random order. Our result shows that random arrivals help beating the 1-1/e barrier even in the vertex-weighted case. We build on the randomized primal-dual framework by Devanur et al. (SODA 2013) and design a two dimensional gain sharing function, which depends not only on the rank of the offline vertex, but also on the arrival time of the online vertex. To our knowledge, this is the first competitive ratio strictly larger than 1-1/e for an online bipartite matching problem achieved under the randomized primal-dual framework. Our algorithm has a natural interpretation that offline vertices offer a larger portion of their weights to the online vertices as time goes by, and each online vertex matches the neighbor with the highest offer at its arrival.
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/10722/2614332018-01-01T00:00:00Z
- Revisiting the direct sum theorem and space lower bounds in random order streamshttp://hdl.handle.net/10722/188484Title: Revisiting the direct sum theorem and space lower bounds in random order streams
Authors: Guha, S; Huang, Z
Abstract: Estimating frequency moments and L p distances are well studied problems in the adversarial data stream model and tight space bounds are known for these two problems. There has been growing interest in revisiting these problems in the framework of random-order streams. The best space lower bound known for computing the k th frequency moment in random-order streams is Ω(n 1-2.5/k ) by Andoni et al., and it is conjectured that the real lower bound shall be Ω(n 1-2/k ). In this paper, we resolve this conjecture. In our approach, we revisit the direct sum theorem developed by Bar-Yossef et al. in a random-partition private messages model and provide a tight Ω(n 1-2/k /ℓ) space lower bound for any ℓ-pass algorithm that approximates the frequency moment in random-order stream model to a constant factor. Finally, we also introduce the notion of space-entropy tradeoffs in random order streams, as a means of studying intermediate models between adversarial and fully random order streams. We show an almost tight space-entropy tradeoff for L ∞ distance and a non-trivial tradeoff for L p distances. © 2009 Springer Berlin Heidelberg.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/10722/1884842009-01-01T00:00:00Z
- Reconstructing numbers from pairwise function valueshttp://hdl.handle.net/10722/188486Title: Reconstructing numbers from pairwise function values
Authors: Chen, S; Huang, Z; Kannan, S
Abstract: The turnpike problem is one of the few "natural" problems that are neither known to be NP-complete nor solvable by efficient algorithms. We seek to study this problem in a more general setting. We consider the generalized problem which tries to resolve set A={a 1,a 2,⋯,a n } from pairwise function values {f(a i ,a j ) | 1≤i, j≤n} for a given bivariate function f. We call this problem the Number Reconstruction problem. Our results include efficient algorithms when f is monotone and non-trivial bounds on the number of solutions when f is the sum. We also generalize previous backtracking and algebraic algorithms for the turnpike problem such that they work for the family of anti-monotone functions and linear-decomposable functions. Finally, we propose an efficient algorithm for the string reconstruction problem, which is related to an approach to protein reconstruction. © 2009 Springer-Verlag Berlin Heidelberg.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/10722/1884862009-01-01T00:00:00Z
- Dynamic and non-uniform pricing strategies for revenue maximizationhttp://hdl.handle.net/10722/188488Title: Dynamic and non-uniform pricing strategies for revenue maximization
Authors: Chakraborty, T; Huang, Z; Khanna, S
Abstract: We study the ITEM PRICING problem for revenue maximization in the limited supply setting, where a single seller with n distinct items caters to m buyers with unknown subadditive valuation functions who arrive in a sequence. The seller sets the prices on individual items. Each buyer buys a subset of yet unsold items that maximizes her utility. Our goal is to design pricing strategies that guarantee an expected revenue that is within a small multiplicative factor of the optimal social welfare - an upper bound on the maximum revenue that can be generated by any pricing mechanism. Most earlier work has focused on the unlimited supply setting, where selling an item to a buyer does not affect the availability of the item to the future buyers. Recently, Balcan et. al. [4] studied the limited supply setting, giving a randomized pricing strategy that achieves a 2 O(√logn log log n)-approximation; their strategy assigns a single price to all items (uniform pricing), and never changes it (static pricing). They also showed that no pricing strategy that is both static and uniform can give better than 2 Ω(log 1/4 n)-approximation. Our first result is a strengthening of the lower bound on approximation achievable by static uniform pricing to 2 Ω(√log n). We then design dynamic uniform pricing strategies (all items are identically priced but item prices can change over time), that achieves O(log 2 n)-approximation, and also show a lower bound of Ω ((log n/log log n) 2) for this class of strategies. Our strategies are simple to implement, and in particular, one strategy is to smoothly decrease the price over time. We also design a static nonuniform pricing strategy (different items can have different prices but prices do not change over time), that give poly-logarithmic approximation in a more restricted setting with few buyers. Thus in the limited supply setting, our results highlight a strong separation between the power of dynamic and non-uniform pricing strategies versus static uniform pricing strategy. To our knowledge, this is the first non-trivial analysis of dynamic and non-uniform pricing schemes for revenue maximization in a setting with multiple distinct items. © 2009 IEEE.
Thu, 01 Jan 2009 00:00:00 GMThttp://hdl.handle.net/10722/1884882009-01-01T00:00:00Z
- Algorithms for the generalized sorting problemhttp://hdl.handle.net/10722/188497Title: Algorithms for the generalized sorting problem
Authors: Huang, Z; Kannan, S; Khanna, S
Abstract: We study the generalized sorting problem where we are given a set of n elements to be sorted but only a subset of all possible pair wise element comparisons is allowed. The goal is to determine the sorted order using the smallest possible number of allowed comparisons. The generalized sorting problem may be equivalently viewed as follows. Given an undirected graph G(V, E) where V is the set of elements to be sorted and E defines the set of allowed comparisons, adaptively find the smallest subset E′ ⊆ E of edges to probe such that the directed graph induced by E′ contains a Hamiltonian path. When G is a complete graph, we get the standard sorting problem, and it is well-known that Θ(n log n) comparisons are necessary and sufficient. An extensively studied special case of the generalized sorting problem is the nuts and bolts problem where the allowed comparison graph is a complete bipartite graph between two equal-size sets. It is known that for this special case also, there is a deterministic algorithm that sorts using Θ(n log n) comparisons. However, when the allowed comparison graph is arbitrary, to our knowledge, no bound better than the trivial O(n 2) bound is known. Our main result is a randomized algorithm that sorts any allowed comparison graph using Õ(n 3/2) comparisons with high probability (provided the input is sortable). We also study the sorting problem in randomly generated allowed comparison graphs, and show that when the edge probability is p, Õ(min{n/p 2, n 3/2 √p}) comparisons suffice on average to sort. © 2011 IEEE.
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/10722/1884972011-01-01T00:00:00Z
- The exponential mechanism for social welfare: Private, truthful, and nearly optimalhttp://hdl.handle.net/10722/188503Title: The exponential mechanism for social welfare: Private, truthful, and nearly optimal
Authors: Huang, Z; Kannan, S
Abstract: In this paper we show that for any mechanism design problem with the objective of maximizing social welfare, the exponential mechanism can be implemented as a truthful mechanism while still preserving differential privacy. Our instantiation of the exponential mechanism can be interpreted as a generalization of the VCG mechanism in the sense that the VCG mechanism is the extreme case when the privacy parameter goes to infinity. To our knowledge, this is the first general tool for designing mechanisms that are both truthful and differentially private. © 2012 IEEE.
Sun, 01 Jan 2012 00:00:00 GMThttp://hdl.handle.net/10722/1885032012-01-01T00:00:00Z
- On sampling from multivariate distributionshttp://hdl.handle.net/10722/188493Title: On sampling from multivariate distributions
Authors: Huang, Z; Kannan, S
Abstract: Let X 1, X 2,..., X n be a set of random variables. Suppose that in addition to the prior distributions of these random variables we are also given linear constraints relating them. We ask for necessary and sufficient conditions under which we can efficiently sample the constrained distributions, find constrained marginal distributions for each of the random variables, etc. We give a tight characterization of the conditions under which this is possible. The problem is motivated by a number of scenarios where we have separate probabilistic inferences in some domain, but domain knowledge allows us to relate these inferences. When the joint prior distribution is a product distribution, the linear constraints have to be carefully chosen and are crucial in creating the lower bound instances. No such constraints are necessary if arbitrary priors are allowed. © 2011 Springer-Verlag.
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/10722/1884932011-01-01T00:00:00Z
- Whole-page optimization and submodular welfare maximization with online biddershttp://hdl.handle.net/10722/188509Title: Whole-page optimization and submodular welfare maximization with online bidders
Authors: Devanur, NR; Huang, Z; Korula, N; Mirrokni, VS; Yan, Q
Abstract: In the context of online ad serving, display ads may appear on different types of web-pages, where each page includes several ad slots and therefore multiple ads can be shown on each page. The set of ads that can be assigned to ad slots of the same page needs to satisfy various pre-specified constraints including exclusion constraints, diversity constraints, and the like. Upon arrival of a user, the ad serving system needs to allocate a set of ads to the current web-page respecting these per-page allocation constraints. Previous slot-based settings ignore the important concept of a page, and may lead to highly suboptimal results in general. In this paper, motivated by these applications in display advertising and inspired by the submodular welfare maximization problem with online bidders, we study a general class of page-based ad allocation problems, present the first (tight) constant-factor approximation algorithms for these problems, and confirm the performance of our algorithms experimentally on real-world data sets. A key technical ingredient of our results is a novel primal-dual analysis for handling free-disposal, which updates dual variables using a \level function" instead of a single level, and unifies with previous analy- ses of related problems. This new analysis method allows us to handle arbitrarily complicated allocation constraints for each page. Our main result is an algorithm that achieves a 1 1 e o(1) competitive ratio. Moreover, our experiments on real-world data sets show significant improvements of our page-based algorithms compared to the slot-based algorithms. Finally, we observe that our problem is closely related to the submodular welfare maximization (SWM) problem. In particular, we introduce a variant of the SWM problem with online bidders, and show how to solve this problem using our algorithm for whole page optimization. Copyright © 2013 ACM.
Tue, 01 Jan 2013 00:00:00 GMThttp://hdl.handle.net/10722/1885092013-01-01T00:00:00Z
- Black-box reductions in mechanism designhttp://hdl.handle.net/10722/188492Title: Black-box reductions in mechanism design
Authors: Huang, Z; Wang, L; Zhou, Y
Abstract: A central question in algorithmic mechanism design is to understand the additional difficulty introduced by truthfulness requirements in the design of approximation algorithms for social welfare maximization. In this paper, by studying the problem of single-parameter combinatorial auctions, we obtain the first black-box reduction that converts any approximation algorithm to a truthful mechanism with essentially the same approximation factor in a prior-free setting. In fact, our reduction works for the more general class of symmetric single-parameter problems. Here, a problem is symmetric if its allocation space is closed under permutations. As extensions, we also take an initial step towards exploring the power of black-box reductions for general single-parameter and multi-parameter problems by showing several positive and negative results. We believe that the algorithmic and game theoretic insights gained from our approach will help better understand the tradeoff between approximability and the incentive compatibility. © 2011 Springer-Verlag.
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/10722/1884922011-01-01T00:00:00Z
- An Online Stochastic Buy-Sell Mechanism for VNF Chains in the NFV Markethttp://hdl.handle.net/10722/243918Title: An Online Stochastic Buy-Sell Mechanism for VNF Chains in the NFV Market
Authors: ZHANG, X; Huang, Z; Wu, C; Li, Z; Lau, FCM
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/10722/2439182017-01-01T00:00:00Z
- Primal dual gives almost optimal energy efficient online algorithmshttp://hdl.handle.net/10722/201111Title: Primal dual gives almost optimal energy efficient online algorithms
Authors: Devanur, NR; Huang, Z
Abstract: We consider the problem of online scheduling of jobs on unrelated machines with dynamic speed scaling to minimize the sum of energy and weighted flow time. We give an algorithm with an almost optimal competitive ratio for arbitrary power functions. (No earlier results handled arbitrary power functions for minimizing flow time plus energy with unrelated machines.) For power functions of the form f(s) = s^alpha for some constant alpha > 1, we get a competitive ratio of O(alpha/log(alpha)), improving upon a previous competitive ratio of O(alpha^2) by Anand et al., along with a matching lower bound of . Further, in the resource augmentation model, with a 1+epsilon speed up, we give a O(1/epsilon) competitive algorithm, with essentially the same techniques, improving the bound of O(1/epsilon^2) by Gupta et al. and matching the bound of Anand et al. [3] for the special case of fixed speed unrelated machines. Unlike the previous results most of which used an amortized local competitiveness argument or dual fitting methods, we use a primal-dual method, which is useful not only to analyze the algorithms but also to design the algorithm itself. Copyright © 2014 by the Society for Industrial and Applied Mathematics.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/10722/2011112014-01-01T00:00:00Z
- Multi-scale Online Learning: Theory and Applications to Online Auctions and Pricinghttp://hdl.handle.net/10722/273145Title: Multi-scale Online Learning: Theory and Applications to Online Auctions and Pricing
Authors: Bubeck, S; Devanur, N; Huang, Z; Niazadeh, R
Abstract: We consider revenue maximization in online auction/pricing problems. A seller sells an identical item in each period to a new buyer, or a new set of buyers. For the online pricing problem, both when the arriving buyer bids or only responds to the posted price, we design algorithms whose regret bounds scale with the best fixed price in-hindsight, rather than the range of the values. Under the bidding model, we further show our algorithms achieve a revenue convergence rate that matches the offline sample complexity of the single-item single-buyer auction. We also show regret bounds that are scale free, and match the offline sample complexity, when comparing to a benchmark that requires a lower bound on the market share. We further expand our results beyond pricing to multi-buyer auctions, and obtain online learning algorithms for auctions, with convergence rates matching the known sample complexity upper bound of online single-item multi-buyer auctions. These results are obtained by generalizing the classical learning from experts and multi-armed bandit problems to their multi-scale versions. In this version, the reward of each action is in a different range, and the regret with respect to a given action scales with its own range, rather than the maximum range. We obtain almost optimal multi-scale regret bounds by introducing a new Online Mirror Descent (OMD) algorithm whose mirror map is the multi-scale version of the negative entropy function. We further generalize to the bandit setting by introducing the stochastic variant of this OMD algorithm.
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/10722/2731452019-01-01T00:00:00Z
- Making the Most of Your Sampleshttp://hdl.handle.net/10722/260853Title: Making the Most of Your Samples
Authors: Huang, Z; Mansour, Y; Roughgarden, T
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/10722/2608532018-01-01T00:00:00Z
- Bayesian incentive compatibility via fractional assignmentshttp://hdl.handle.net/10722/188491Title: Bayesian incentive compatibility via fractional assignments
Authors: Bei, X; Huang, Z
Abstract: Very recently, Hartline and Lucier [14] studied single- parameter mechanism design problems in the Bayesian setting. They proposed a black-box reduction that converted Bayesian approximation algorithms into Bayesian-Incentive- Compatible (BIC) mechanisms while preserving social welfare. It remains a major open question if one can find similar reduction in the more important multi-parameter setting. In this paper, we give positive answer to this question when the prior distribution has finite and small support. We propose a black-box reduction for designing BIC multi-parameter mechanisms. The reduction converts any algorithm into an ε-BIC mechanism with only marginal loss in social welfare. As a result, for combinatorial auctions with sub-additive agents we get an ε-BIC mechanism that achieves constant approximation.
Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/10722/1884912011-01-01T00:00:00Z
- AdWords in a Panoramahttp://hdl.handle.net/10722/301409Title: AdWords in a Panorama
Authors: Huang, Z; Zhang, Q; Zhang, Y
Abstract: Three decades ago, Karp, Vazirani, and Vazirani (STOC 1990) defined the online matching problem and gave an optimal (1-1/e)-competitive (about 0.632) algorithm. Fifteen years later, Mehta, Saberi, Vazirani, and Vazirani (FOCS 2005) introduced the first generalization called AdWords driven by online advertising and obtained the optimal (1-1/e) competitive ratio in the special case of small bids. It has been open ever since whether there is an algorithm for general bids better than the 0.5-competitive greedy algorithm. This paper presents a 0.5016-competitive algorithm for AdWords, answering this open question on the positive end. The algorithm builds on several ingredients, including a combination of the online primal dual framework and the configuration linear program of matching problems recently explored by Huang and Zhang (STOC 2020), a novel formulation of AdWords which we call the panorama view, and a generalization of the online correlated selection by Fahrbach, Huang, Tao, and Zadimorghaddam (FOCS 2020) which we call the panoramic online correlated selection.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/10722/3014092020-01-01T00:00:00Z
- Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Modelhttp://hdl.handle.net/10722/273020Title: Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model
Authors: Huang, Z; Peng, B; Tang, Z; Tao, R; Wu, X; Zhang, Y
Abstract: Huang et al. (STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive online and considers general graphs. They showed that the ranking algorithm by Karp et al. (STOC 1990) is strictly better than 0.5-competitive and the problem is strictly harder than the online bipartite matching problem in that no algorithms can be (1 – 1/e)-competitive.
This paper pins down two tight competitive ratios of classic algorithms for the fully online matching problem. For the fractional version of the problem, we show that a natural instantiation of the water-filling algorithm is 2 –√2 ≈ 0.585-competitive, together with a matching hardness result. Interestingly, our hardness result applies to arbitrary algorithms in the edge-arrival models of the online matching problem, improving the state-of-art 1/1+1n2≈0.5906 upper bound. For integral algorithms, we show a tight competitive ratio of ≈ 0.567 for the ranking algorithm on bipartite graphs, matching a hardness result by Huang et al. (STOC 2018). Read More: https://epubs.siam.org/doi/10.1137/1.9781611975482.178
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/10722/2730202019-01-01T00:00:00Z
- Online auctions in IaaS clouds: welfare and profit maximization with server costshttp://hdl.handle.net/10722/213809Title: Online auctions in IaaS clouds: welfare and profit maximization with server costs
Authors: Zhang, X; Huang, Z; Wu, C; Li, Z; Lau, FCM
Abstract: Auction design has recently been studied for dynamic resource bundling and VM provisioning in IaaS clouds, but is mostly restricted to the one-shot or offline setting. This work targets a more realistic case of online VM auction design, where: (i) cloud users bid for resources into the future to assemble customized VMs with desired occupation durations; (ii) the cloud provider dynamically packs multiple types of resources on heterogeneous physical machines (servers) into the requested VMs; (iii) the operational costs of servers are considered in resource allocation; (iv) both social welfare and the cloud provider's net profit are to be maximized over the system running span. We design truthful, polynomial time auctions to achieve social welfare maximization and/or the provider's profit maximization with good competitive ratios. Our mechanisms consist of two main modules: (1) an online primal-dual optimization framework for VM allocation to maximize the social welfare with server costs, and for revealing the payments through the dual variables to guarantee truthfulness; and (2) a randomized reduction algorithm to convert the social welfare maximizing auctions to ones that provide a maximal expected profit for the provider, with competitive ratios comparable to those for social welfare. We adopt a new application of Fenchel duality in our primal-dual framework, which provides richer structures for convex programs than the commonly used Lagrangian duality, and our optimization framework is general and expressive enough to handle various convex server cost functions. The efficacy of the online auctions is validated through careful theoretical analysis and trace-driven simulation studies. © 2015 ACM, Inc.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/10722/2138092015-01-01T00:00:00Z
- Private matchings and allocationshttp://hdl.handle.net/10722/201109Title: Private matchings and allocations
Authors: Hsu, J; Huang, Z; Roth, A; Roughgarden, T; Wu, SZ
Abstract: We consider a private variant of the classical allocation problem: given k goods and n agents with individual, private valuation functions over bundles of goods, how can we partition the goods amongst the agents to maximize social welfare? An important special case is when each agent desires at most one good, and specifies her (private) value for each good: in this case, the problem is exactly the maximum-weight matching problem in a bipartite graph. Private matching and allocation problems have not been considered in the differential privacy literature, and for good reason: they are plainly impossible to solve under differential privacy. Informally, the allocation must match agents to their preferred goods in order to maximize social welfare, but this preference is exactly what agents wish to hide! Therefore, we consider the problem under the relaxed constraint of joint differential privacy: for any agent i, no coalition of agents excluding i should be able to learn about the valuation function of agent i. In this setting, the full allocation is no longer published---instead, each agent is told what good to get. We first show that with a small number of identical copies of each good, it is possible to efficiently and accurately solve the maximum weight matching problem while guaranteeing joint differential privacy. We then consider the more general allocation problem, when bidder valuations satisfy the gross substitutes condition. Finally, we prove that the allocation problem cannot be solved to non-trivial accuracy under joint differential privacy without requiring multiple copies of each type of good. © 2014 ACM.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/10722/2011092014-01-01T00:00:00Z
- Making the most of your sampleshttp://hdl.handle.net/10722/218927Title: Making the most of your samples
Authors: Huang, Z; Mansour, Y; Roughgarden, T
Abstract: We study the problem of setting a price for a potential buyer with a valuation drawn from an unknown distribution D. The seller has "data" about D in the form of m ≥ 1 i.i.d. samples, and the algorithmic challenge is to use these samples to obtain expected revenue as close as possible to what could be achieved with advance knowledge of D.
Our first set of results quantifies the number of samples m that are necessary and sufficient to obtain a …
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/10722/2189272015-01-01T00:00:00Z
- Speed scaling in the non-clairvoyant modelhttp://hdl.handle.net/10722/218928Title: Speed scaling in the non-clairvoyant model
Authors: Azar, Y; Devanur, NR; Huang, Z; Panigrahi, D
Abstract: In recent years, there has been a growing interest in speed scaling algorithms, where a set of jobs need to be scheduled on a machine with variable speed so as to optimize the flow-times of the jobs and the energy consumed by the machine. A series of results have culminated in constant-competitive algorithms for this problem in the clairvoyant model, i.e., when job parameters are revealed on releasing a job (Bansal, Pruhs, and Stein, SODA 2007; Bansal, Chan, and Pruhs, SODA 2009). Our main contribution in this paper is the first constant-competitive speed scaling algorithm in the nonclairvoyant model, which is typically used in the scheduling literature to model practical settings where job volume is revealed only after the job has been completely processed. Unlike in the clairvoyant model, the speed scaling problem in the non-clairvoyant model is non-trivial even for a single job. Our non-clairvoyant algorithm is defined by using the existing clairvoyant algorithm in a novel inductive way, which then leads to an inductive analytical tool that may be of independent interest for other online optimization problems. We also give additional algorithmic results and lower bounds for speed scaling on multiple identical parallel machines.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/10722/2189282015-01-01T00:00:00Z
- Occupation-Oblivious Pricing of Cloud Jobs via Online Learninghttp://hdl.handle.net/10722/259648Title: Occupation-Oblivious Pricing of Cloud Jobs via Online Learning
Authors: Zhang, X; Wu, C; Huang, Z; Li, Z
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/10722/2596482018-01-01T00:00:00Z
- A technique for polygon inclusion problemhttp://hdl.handle.net/10722/259650Title: A technique for polygon inclusion problem
Authors: Jin, K; Huang, Z
Abstract: The widely known linear time algorithm for computing the maximum area triangle in a convex polygon was found incorrect recently by Keikha et. al. We present an alternative algorithm in this paper. Comparing to the only previously known correct solution, ours is much simpler and more efficient. More importantly, our new approach is powerful in solving related problems.
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/10722/2596502018-01-01T00:00:00Z
- Online Auctions and Multi-scale Online Learninghttp://hdl.handle.net/10722/246609Title: Online Auctions and Multi-scale Online Learning
Authors: Bubeck, S; Devanur, NR; Huang, Z; Niazadeh, R
Abstract: We consider revenue maximization in online auctions and pricing. A seller sells an identical item in each period to a new buyer, or a new set of buyers. For the online posted pricing problem, we show regret bounds that scale with the best fixed price, rather than the range of the values. We also show regret bounds that are almost scale free, and match the offline sample complexity, when comparing to a benchmark that requires a lower bound on the market share. These results are obtained by generalizing the classical learning from experts and multi-armed bandit problems to their multi-scale versions. In this version, the reward of each action is in a different range, and the regret w.r.t. a given action scales with its own range, rather than the maximum range.
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/10722/2466092017-01-01T00:00:00Z
- Private Matchings and Allocationshttp://hdl.handle.net/10722/246195Title: Private Matchings and Allocations
Authors: Hsu, J; Huang, Z; Roth, A; Roughgarden, T; Wu, ZS
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/10722/2461952016-01-01T00:00:00Z
- Privacy Preserving Auctionhttp://hdl.handle.net/10722/218314Title: Privacy Preserving Auction
Authors: Huang, Z
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/10722/2183142015-01-01T00:00:00Z
- Online Primal Dual: Beyond Linear Programshttp://hdl.handle.net/10722/218315Title: Online Primal Dual: Beyond Linear Programs
Authors: Huang, Z
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/10722/2183152014-01-01T00:00:00Z
- Learning Resource Allocation and Pricing for Cloud Profit Maximizationhttp://hdl.handle.net/10722/273018Title: Learning Resource Allocation and Pricing for Cloud Profit Maximization
Authors: Du, B; Wu, C; Huang, Z
Abstract: Cloud computing has been widely adopted to support various computation services. A fundamental problem faced by cloud providers is how to efficiently allocate resources upon user requests and price the resource usage, in order to maximize resource efficiency and hence provider profit. Existing studies establish detailed performance models of cloud resource usage, and propose offline or online algorithms to decide allocation and pricing. Differently, we adopt a blackbox approach, and leverage model-free Deep Reinforcement Learning (DRL) to capture dynamics of cloud users and better characterize inherent connections between an optimal allocation/pricing policy and the states of the dynamic cloud system. The goal is to learn a policy that maximizes net profit of the cloud provider through trial and error, which is better than decisions made on explicit performance models. We combine long short-term memory (LSTM) units with fully-connected neural networks in our DRL to deal with online user arrivals, and adjust the output and update methods of basic DRL algorithms to address both resource allocation and pricing. Evaluation based on real-world datasets shows that our DRL approach outperforms basic DRL algorithms and state-of-theart white-box online cloud resource allocation/pricing algorithms significantly, in terms of both profit and the number of accepted users.
Description: Tech Session 9: Planning, Routing, and Scheduling 2 - Oral Presentation no. 3542
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/10722/2730182019-01-01T00:00:00Z
- Learning Optimal Reserve Price against Non-myopic Biddershttp://hdl.handle.net/10722/273021Title: Learning Optimal Reserve Price against Non-myopic Bidders
Authors: Huang, Z; Liu, J; Wang, X
Abstract: We consider the problem of learning optimal reserve price in repeated auctions against non-myopic bidders, who may bid strategically in order to gain in future rounds even if the single-round auctions are truthful. Previous algorithms, e.g., empirical pricing, do not provide non-trivial regret rounds in this setting in general. We introduce algorithms that obtain small regret against non-myopic bidders either when the market is large, i.e., no bidder appears in a constant fraction of the rounds, or when the bidders are impatient, i.e., they discount future utility by some factor mildly bounded away from one. Our approach carefully controls what information is revealed to each bidder, and builds on techniques from differentially private online learning as well as the recent line of works on jointly differentially private algorithms.
Description: Poster Session A
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/10722/2730212018-01-01T00:00:00Z
- Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora’s Problemhttp://hdl.handle.net/10722/304054Title: Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora’s Problem
Authors: Guo, C; Huang, Z; Tang, Z; Zhang, X
Abstract: This paper explores a theory of generalization for learning problems on product distributions, complementing the existing learning theories in the sense that it does not rely on any complexity measures of the hypothesis classes. The main contributions are two general sample complexity bounds: (1) O~(nkϵ2) samples are sufficient and necessary for learning an ϵ-optimal hypothesis in emph{any problem} on an n-dimensional product distribution, whose marginals have finite supports of sizes at most k; (2) O~(nϵ2) samples are sufficient and necessary for any problem on n-dimensional product distributions if it satisfies a notion of strong monotonicity from the algorithmic game theory literature. As applications of these theories, we match the optimal sample complexity for single-parameter revenue maximization (Guo et al., STOC 2019), improve the state-of-the-art for multi-parameter revenue maximization (Gonczarowski and Weinberg, FOCS 2018) and prophet inequality (Correa et al., EC 2019; Rubinstein et al., ITCS 2020), and provide the first and tight sample complexity bound for Pandora’s problem.
Fri, 01 Jan 2021 00:00:00 GMThttp://hdl.handle.net/10722/3040542021-01-01T00:00:00Z
- Welfare maximization with production costs: a primal dual approachhttp://hdl.handle.net/10722/209631Title: Welfare maximization with production costs: a primal dual approach
Authors: Huang, Z; Kim, A
Abstract: We study online combinatorial auctions with production costs proposed by Blum et al. using the online primal dual framework. In this model, buyers arrive online, and the seller can produce multiple copies of each item subject to a non-decreasing marginal cost per copy. The goal is to allocate items to maximize social welfare less total production cost. For arbitrary (strictly convex and differentiable) production cost functions, we characterize the optimal competitive ratio achievable by online mechanisms/algorithms. We show that online posted pricing mechanisms, which are incentive compatible, can achieve competitive ratios arbitrarily close to the optimal, and construct lower bound instances on which no online algorithms, not necessarily incentive compatible, can do better. Our positive results improve or match the results in several previous work, e.g., Bartal et al., Blum et al., and Buchbinder and Gonen. Our lower bounds apply to randomized algorithms and resolve an open problem by Buchbinder and Gonen.
Description: CP2: Session 1B
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/10722/2096312015-01-01T00:00:00Z
- The power of multiple choices in online stochastic matchinghttp://hdl.handle.net/10722/333747Title: The power of multiple choices in online stochastic matching
Authors: Huang, Zhiyi; Shu, Xinkai; Yan, Shuyi
Abstract: <p>We study the power of multiple choices in online stochastic matching. Despite a long line of research, existing algorithms still only consider two choices of offline neighbors for each online vertex because of the technical challenge in analyzing multiple choices. This paper introduces two approaches for designing and analyzing algorithms that use multiple choices. For unweighted and vertex-weighted matching, we adopt the online correlated selection (OCS) technique into the stochastic setting, and improve the competitive ratios to 0.716, from 0.711 and 0.7 respectively. For edge-weighted matching with free disposal, we propose the Top Half Sampling algorithm. We directly characterize the progress of the whole matching instead of individual vertices, through a differential inequality. This improves the competitive ratio to 0.706, breaking the 1−1/<em>e</em> barrier in this setting for the first time in the literature. Finally, for the harder edge-weighted problem without free disposal, we prove that no algorithms can be 0.703 competitive, separating this setting from the aforementioned three.<br></p>
Fri, 10 Jun 2022 00:00:00 GMThttp://hdl.handle.net/10722/3337472022-06-10T00:00:00Z
- Online Makespan Minimization: The Power of Restarthttp://hdl.handle.net/10722/260347Title: Online Makespan Minimization: The Power of Restart
Authors: Huang, Z; Kang, N; Tang, Z; Wu, X; Zhang, Y
Abstract: We consider the online makespan minimization problem on identical machines. Chen and Vestjens (ORL 1997) show that the largest processing time first (LPT) algorithm is 1.5-competitive. For the special case of two machines, Noga and Seiden (TCS 2001) introduce the SLEEPY algorithm that achieves a competitive ratio of (5−5 – √ )/2≈1.382 , matching the lower bound by Chen and Vestjens (ORL 1997). Furthermore, Noga and Seiden note that in many applications one can kill a job and restart it later, and they leave an open problem whether algorithms with restart can obtain better competitive ratios.
We resolve this long-standing open problem on the positive end. Our algorithm has a natural rule for killing a processing job: a newly-arrived job replaces the smallest processing job if 1) the new job is larger than other pending jobs, 2) the new job is much larger than the processing one, and 3) the processed portion is small relative to the size of the new job. With appropriate choice of parameters, we show that our algorithm improves the 1.5 competitive ratio for the general case, and the 1.382 competitive ratio for the two-machine case.
Description: The 21st International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'2018), and the 22nd International Conference on Randomization and Computation (RANDOM'2018)
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/10722/2603472018-01-01T00:00:00Z
- Scalable and Jointly Differentially Private Packinghttp://hdl.handle.net/10722/273019Title: Scalable and Jointly Differentially Private Packing
Authors: Huang, Z; Zhu, X
Abstract: We introduce an (\epsilon, \delta)-jointly differentially private algorithm for packing problems. Our algorithm not only achieves the optimal trade-off between the privacy parameter \epsilon and the minimum supply requirement (up to logarithmic factors), but is also scalable in the sense that the running time is linear in the number of agents n. Previous algorithms either run in cubic time in n, or require a minimum supply per resource that is \sqrt{n} times larger than the best possible.
Description: Track: A - Session A.2.1
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/10722/2730192019-01-01T00:00:00Z
- Whole-Page Optimization and Submodular Welfare Maximization with Online Biddershttp://hdl.handle.net/10722/232834Title: Whole-Page Optimization and Submodular Welfare Maximization with Online Bidders
Authors: Devanur, NR; Huang, Z; Korula, N; Mirrokni, V; Yan, Q
Abstract: In the context of online ad serving, display ads may appear on different types of webpages, where each page includes several ad slots and therefore multiple ads can be shown on each page. The set of ads that can be assigned to ad slots of the same page needs to satisfy various prespecified constraints including exclusion constraints, diversity constraints, and the like. Upon arrival of a user, the ad serving system needs to allocate a set of ads to the current webpage respecting these per-page allocation constraints. Previous slot-based settings ignore the important concept of a page and may lead to highly suboptimal results in general. In this article, motivated by these applications in display advertising and inspired by the submodular welfare maximization problem with online bidders, we study a general class of page-based ad allocation problems, present the first (tight) constant-factor approximation algorithms for these problems, and confirm the performance of our algorithms experimentally on real-world datasets.
A key technical ingredient of our results is a novel primal-dual analysis for handling free disposal, which updates dual variables using a “level function” instead of a single level and unifies with previous analyses of related problems. This new analysis method allows us to handle arbitrarily complicated allocation constraints for each page. Our main result is an algorithm that achieves a 1 &minus frac 1 e &minus o(1)-competitive ratio. Moreover, our experiments on real-world datasets show significant improvements of our page-based algorithms compared to the slot-based algorithms.
Finally, we observe that our problem is closely related to the submodular welfare maximization (SWM) problem. In particular, we introduce a variant of the SWM problem with online bidders and show how to solve this problem using our algorithm for whole-page optimization.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/10722/2328342016-01-01T00:00:00Z
- Online algorithms for covering and packing problems with convex objectiveshttp://hdl.handle.net/10722/232177Title: Online algorithms for covering and packing problems with convex objectives
Authors: Azar, Y; Buchbinder, N; Chan, HTH; Chen, S; Cohen, IR; Gupta, A; Huang, Z; Kang, N; Nagarjajan, V; Naor, JS; Panigrahi, D
Abstract: We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as ...
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/10722/2321772016-01-01T00:00:00Z
- Applications of Online Matchinghttp://hdl.handle.net/10722/339121Title: Applications of Online Matching
Authors: Huang, Zhiyi; Trobst, Thorben
Sat, 13 May 2023 00:00:00 GMThttp://hdl.handle.net/10722/3391212023-05-13T00:00:00Z
- Near Optimal Jointly Private Packing Algorithms via Dual Multiplicative Weight Updatehttp://hdl.handle.net/10722/251826Title: Near Optimal Jointly Private Packing Algorithms via Dual Multiplicative Weight Update
Authors: Huang, Z; Zhu, X
Abstract: We present an improved (ε, δ-jointly differentially private algorithm for packing problems. Our algorithm gives a feasible output that is approximately optimal up to an αn additive factor as long as the supply of each resource is at least , where m is the number of resources. This improves the previous result by Hsu et al. (SODA ’16), which requires the total supply to be at least Õ(m2/αε), and only guarantees approximate feasibility in terms of total violation. Further, we complement our algorithm with an almost matching hardness result, showing that supply is necessary for any (ε, δ)-jointly differentially private algorithm to compute an approximately optimal packing solution. Finally, we introduce an alternative approach that runs in linear time, is exactly truthful, can be implemented online, and can be ε-jointly differentially private, but requires a larger supply of each resource.
Mon, 01 Jan 2018 00:00:00 GMThttp://hdl.handle.net/10722/2518262018-01-01T00:00:00Z
- Improved Online Correlated Selectionhttp://hdl.handle.net/10722/317524Title: Improved Online Correlated Selection
Authors: Gao, R; He, Z; Huang, Z; Nie, Z; Yuan, B; Zhong, Y
Sat, 01 Jan 2022 00:00:00 GMThttp://hdl.handle.net/10722/3175242022-01-01T00:00:00Z
- Class Fairness in Online Matchinghttp://hdl.handle.net/10722/333746Title: Class Fairness in Online Matching
Authors: Hosseini, Hadi; Huang, Zhiyi; Igarashi, Ayumi; Shah, Nisarg
Abstract: <p>We initiate the study of fairness among classes of agents in online bipartite matching where there is a given set of offline vertices (aka agents) and another set of vertices (aka items) that arrive online and must be matched irrevocably upon arrival. In this setting, agents are partitioned into a set of classes and the matching is required to be fair with respect to the classes. We adopt popular fairness notions (e.g. envy-freeness, proportionality, and maximin share) and their relaxations to this setting and study deterministic and randomized algorithms for matching indivisible items (leading to integral matchings) and for matching divisible items (leading to fractional matchings). For matching indivisible items, we propose an adaptive-priority-based algorithm, MATCH-AND-SHIFT, prove that it achieves (1/2)-approximation of both class envy-freeness up to one item and class maximin share fairness, and show that each guarantee is tight. For matching divisible items, we design a water-filling-based algorithm, EQUAL-FILLING, that achieves (1-1/e)-approximation of class envy-freeness and class proportionality; we prove (1-1/e) to be tight for class proportionality and establish a 3/4 upper bound on class envy-freeness.</p>
Mon, 26 Jun 2023 00:00:00 GMThttp://hdl.handle.net/10722/3337462023-06-26T00:00:00Z
- Online Combinatorial Optimization Problems with Non-linear Objectiveshttp://hdl.handle.net/10722/273340Title: Online Combinatorial Optimization Problems with Non-linear Objectives
Authors: Huang, Z
Abstract: We survey some recent progress on the design and the analysis of online algorithms for optimization problems with non-linear, usually convex, objectives. We focus on an extension of the online primal dual technique, and highlight its application in a number of applications, including an online matching problem with concave returns, an online scheduling problem with speed-scalable machines subjective to convex power functions, and a family of online covering and packing problems with convex objectives.
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/10722/2733402019-01-01T00:00:00Z
- Algorithmic Price Discriminationhttp://hdl.handle.net/10722/284139Title: Algorithmic Price Discrimination
Authors: Cummings, R; Devanur, N; Huang, Z; WANG, X
Abstract: We consider a generalization of the third degree price discrimination problem studied in [4](Bergemann et al., 2015), where an intermediary between the buyer and the seller can design market segments to maximize any linear combination of consumer surplus and seller revenue. Unlike in [4], we assume that the intermediary only has partial information about the buyer's value. We consider three different models of information, with increasing order of difficulty. In the first model, we assume that the intermediary's information allows him to construct a probability distribution of the buyer's value. Next we consider the sample complexity model, where we assume that the intermediary only sees samples from this distribution. Finally, we consider a bandit online learning model, where the intermediary can only observe past purchasing decisions of the buyer, rather than her exact value. For each of these models, we present algorithms to compute optimal or near optimal market segmentation.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/10722/2841392020-01-01T00:00:00Z
- Fully Online Matchinghttp://hdl.handle.net/10722/284233Title: Fully Online Matching
Authors: Huang, Z; Kang, N; Tang, ZG; Wu, X; ZHANG, Y; ZHU, X
Abstract: We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors’ arrivals. If a vertex remains unmatched until its deadline, then the algorithm must irrevocably either match it to an unmatched neighbor or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, and so on.
We show that the Ranking algorithm by Karp et al. (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step toward solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, then we show a tight competitive ratio ≈0.5671 of Ranking. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317 < 1- 1/e-competitive in our model, even for bipartite graphs.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/10722/2842332020-01-01T00:00:00Z
- Dynamic VM Scaling: Provisioning and Pricing through an Online Auctionhttp://hdl.handle.net/10722/259900Title: Dynamic VM Scaling: Provisioning and Pricing through an Online Auction
Authors: ZHANG, X; Huang, Z; Wu, C; Li, Z; Lau, FCM
Fri, 01 Jan 2021 00:00:00 GMThttp://hdl.handle.net/10722/2599002021-01-01T00:00:00Z
- Targeting Makes Sample Efficiency in Auction Designhttp://hdl.handle.net/10722/304340Title: Targeting Makes Sample Efficiency in Auction Design
Authors: Hu, Y; Huang, Z; Shen, Y; Wang, X
Abstract: This paper introduces the targeted sampling model in optimal auction design. In this model, the seller may specify a quantile interval and sample from a buyer's prior restricted to the interval. This can be interpreted as allowing the seller to, for example, examine the top 40% bids from previous buyers with the same characteristics. The targeting power is quantified with a parameter Δ ∈ [0, 1] which lower bounds how small the quantile intervals could be. When Δ = 1, it degenerates to Cole and Roughgarden's model of i.i.d. samples; when it is the idealized case of Δ = 0, it degenerates to the model studied by [7]. For instance, for n buyers with bounded values in [0, 1], ~O(ε-1) targeted samples suffice while it is known that at least ~Ømega(n ε-2) i.i.d. samples are needed. In other words, targeted sampling with sufficient targeting power allows us to remove the linear dependence in n, and to improve the quadratic dependence in ε-1 to linear. In this work, we introduce new technical ingredients and show that the number of targeted samples sufficient for learning an ε-optimal auction is substantially smaller than the sample complexity of i.i.d. samples for the full spectrum of Δ ∈ [0, 1). Even with only mild targeting power, i.e., whenever Δ = o(1), our targeted sample complexity upper bounds are strictly smaller than the optimal sample complexity of i.i.d. samples.
Fri, 01 Jan 2021 00:00:00 GMThttp://hdl.handle.net/10722/3043402021-01-01T00:00:00Z
- Strong revenue (non-)monotonicity of single-parameter auctionshttp://hdl.handle.net/10722/337149Title: Strong revenue (non-)monotonicity of single-parameter auctions
Authors: Chen, Ziyun; Huang, Zhiyi; Majdi, Dorsa; Yan, Zipeng
Sun, 09 Jul 2023 00:00:00 GMThttp://hdl.handle.net/10722/3371492023-07-09T00:00:00Z
- Online Nash Welfare Maximization Without Predictionshttp://hdl.handle.net/10722/340468Title: Online Nash Welfare Maximization Without Predictions
Authors: Huang, Zhiyi; Li, Minming; Shu, Xinkai; Wei, Tianze
Abstract: <p>The maximization of Nash welfare, which equals the geometric mean of agents’ utilities, is widely studied because it balances efficiency and fairness in resource allocation problems. Banerjee, Gkatzelis, Gorokh, and Jin (2022) recently introduced the model of online Nash welfare maximization for T divisible items and N agents with additive utilities with predictions of each agent’s utility for receiving all items. They gave online algorithms whose competitive ratios are logarithmic. We initiate the study of online Nash welfare maximization without predictions, assuming either that the agents’ utilities for receiving all items differ by a bounded ratio, or that their utilities for the Nash welfare maximizing allocation differ by a bounded ratio. We design online algorithms whose competitive ratios only depend on the logarithms of the aforementioned ratios of agents’ utilities and the number of agents.<br></p>
Mon, 04 Dec 2023 00:00:00 GMThttp://hdl.handle.net/10722/3404682023-12-04T00:00:00Z
- An Efficient Cloud Market Mechanism for Computing Jobs with Soft Deadlineshttp://hdl.handle.net/10722/243531Title: An Efficient Cloud Market Mechanism for Computing Jobs with Soft Deadlines
Authors: Zhou, R; Li, Z; Wu, C; Huang, Z
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/10722/2435312017-01-01T00:00:00Z