SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

Scalar-linear solvability of matroidal networks associated with representable matroids

2010-09-01
Anthony Kim , Muriel Médard
We study matroidal networks introduced by Dougherty et al. We prove the converse of the following theorem: If a network is scalar-linearly solvable over some finite field, then the network … We study matroidal networks introduced by Dougherty et al. We prove the converse of the following theorem: If a network is scalar-linearly solvable over some finite field, then the network is a matroidal network associated with a representable matroid over a finite field. It follows that a network is scalar-linearly solvable if and only if the network is a matroidal network associated with a representable matroid over a finite field. We note that this result combined with the construction method due to Dougherty et al. gives a method for generating scalar-linearly solvable networks. Using the converse implicitly, we demonstrate scalar-linear solvability of two classes of matroidal networks: networks constructed from uniform matroids and those constructed from graphic matroids.
View PDF Chat

Welfare Maximization with Production Costs: A Primal Dual Approach

2014-12-22
Zhiyi Huang , Anthony Kim
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Welfare Maximization with Production Costs: A Primal Dual ApproachZhiyi Huang and Anthony KimZhiyi Huang … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Welfare Maximization with Production Costs: A Primal Dual ApproachZhiyi Huang and Anthony KimZhiyi Huang and Anthony Kimpp.59 - 72Chapter DOI:https://doi.org/10.1137/1.9781611973730.6PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We study online combinatorial auctions with production costs proposed by Blum et al. [4] 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. [a], Blum et al. [4], and Buchbinder and Conen [6]. Our lower bounds apply to randomized algorithms and resolve an open problem by Buchbinder and Gonen [6]. Previous chapter Next chapter RelatedDetails Published:2015ISBN:978-1-61197-374-7eISBN:978-1-61197-373-0 https://doi.org/10.1137/1.9781611973730Book Series Name:ProceedingsBook Code:PRDA15Book Pages:viii + 2048
View PDF Chat

Minimizing Latency in Online Ride and Delivery Services

2018-01-01
Abhimanyu Das , Sreenivas Gollapudi , Anthony Kim +2 more
Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles … Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles located at depots to serve requests located on a metric space so as to minimize the total latency. In this paper, we consider point-to-point requests that come with source-destination pairs and release-time constraints that restrict when each request can be served. The point-to-point requests and release-time constraints model taxi rides and deliveries. For all the variants considered, we show constant-factor approximation algorithms based on a linear programming framework. To the best of our knowledge, these are the first set of results for the aforementioned variants of the minimum latency problems. Furthermore, we provide an empirical study of heuristics based on our theoretical algorithms on a real data set of taxi rides.
View PDF Chat

Welfare maximization with production costs: A primal dual approach

2018-03-18
Zhiyi Huang , Anthony Kim
View PDF Chat

Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems

2015-01-01
Anthony Kim
View PDF Chat

Minimizing Latency in Online Ride and Delivery Services

2018-02-08
Abhimanyu Das , Sreenivas Gollapudi , Anthony Kim +2 more
Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles … Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles located at depots to serve request located on a metric space so as to minimize the total latency. In this paper, we consider point-to-point requests that come with source-destination pairs and release-time constraints that restrict when each request can be served. The point-to-point requests and release-time constraints model taxi rides and deliveries. For all the variants considered, we show constant-factor approximation algorithms based on a linear programming framework. To the best of our knowledge, these are the first set of results for the aforementioned variants of the minimum latency problems. Furthermore, we provide an empirical study of heuristics based on our theoretical algorithms on a real data set of taxi rides.

Computing bounds on network capacity regions as a polytope reconstruction problem

2011-07-01
Anthony Kim , Muriel Médard
We define a notion of network capacity region of networks that generalizes the notion of network capacity defined by Cannons et al. and prove its notable properties such as closedness, … We define a notion of network capacity region of networks that generalizes the notion of network capacity defined by Cannons et al. and prove its notable properties such as closedness, boundedness and convexity when the finite field is fixed. We show that the network routing capacity region is a computable rational polytope and provide exact algorithms and approximation heuristics for computing the region. We define the semi-network linear coding capacity region, with respect to a fixed finite field, that inner bounds the corresponding network linear coding capacity region, show that it is a computable rational polytope, and provide exact algorithms and approximation heuristics. We show connections between computing these regions and a polytope reconstruction problem and some combinatorial optimization problems, such as the minimum cost directed Steiner tree problem. We provide an example to illustrate our results. The algorithms are not necessarily polynomial-time.
View PDF Chat

The Shapley Value in Knapsack Budgeted Games

2014-01-01
Smriti Bhagat , Anthony Kim , S. Muthukrishnan +1 more
View PDF Chat

The Shapley Value in Knapsack Budgeted Games

2014-09-18
Smriti Bhagat , Anthony Kim , S. Muthukrishnan +1 more
We propose the study of computing the Shapley for a new class of cooperative games that we call budgeted games, and investigate in particular knapsack budgeted games, a version modeled … We propose the study of computing the Shapley for a new class of cooperative games that we call budgeted games, and investigate in particular knapsack budgeted games, a version modeled after the classical knapsack problem. In these games, the value of a set $S$ of agents is determined only by a critical subset $T\subseteq S$ of the agents and not the entirety of $S$ due to a budget constraint that limits how large $T$ can be. We show that the Shapley can be computed in time faster than by the naive exponential time algorithm when there are sufficiently many agents, and also provide an algorithm that approximates the Shapley within an additive error. For a related budgeted game associated with a greedy heuristic, we show that the Shapley can be computed in pseudo-polynomial time. Furthermore, we generalize our proof techniques and propose what we term algorithmic representation framework that captures a broad class of cooperative games with the property of efficient computation of the Shapley value. The main idea is that the problem of determining the efficient computation can be reduced to that of finding an alternative representation of the games and an associated algorithm for computing the underlying function with small time and space complexities in the representation size.

Welfare Maximization with Production Costs: A Primal Dual Approach

2014-01-01
Zhiyi Huang , Anthony Kim
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 … 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.
View PDF Chat

Depth First Always On Routing Trace Algorithm

2017-01-01
Anthony Kim , Sung Hyun Chen , Zheng Chen
In this paper, we discussed current limitation in the electronic-design-automotation (EDA) tool on tracing the always on routing. We developed an algorithm to efficiently track the secondary power routing and … In this paper, we discussed current limitation in the electronic-design-automotation (EDA) tool on tracing the always on routing. We developed an algorithm to efficiently track the secondary power routing and accurately estimate the routing quality using approximate voltage drop as the criteria. The fast check can identify potential hotspot issues without going through sign-off checks. It helps designers to capture issues at early stages and fix the issues with less design effort. We also discussed some limitations to our algorithm.

Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems

2015-01-01
Anthony Kim
We design approximate weakly group strategy-proof mechanisms for resource reallocation problems using Milgrom and Segal's deferred acceptance auction framework: the radio spectrum and network bandwidth reallocation problems in the procurement … We design approximate weakly group strategy-proof mechanisms for resource reallocation problems using Milgrom and Segal's deferred acceptance auction framework: the radio spectrum and network bandwidth reallocation problems in the procurement auction setting and the cost minimization problem with set cover constraints in the selling auction setting. Our deferred acceptance auctions are derived from simple greedy algorithms for the underlying optimization problems and guarantee approximately optimal social welfare (cost) of the agents retaining their rights (contracts). In the reallocation problems, we design procurement auctions to purchase agents' broadcast/access rights to free up some of the resources such that the unpurchased rights can still be exercised with respect to the remaining resources. In the cost minimization problem, we design a selling auction to sell early termination rights to agents with existing contracts such that some minimal constraints are still satisfied with remaining contracts. In these problems, while the "allocated" agents transact, exchanging rights and payments, the objective and feasibility constraints are on the "rejected" agents.
View PDF Chat

The Shapley Value in Knapsack Budgeted Games

2014-01-01
Smriti Bhagat , Anthony Kim , S. Muthukrishnan +1 more
We propose the study of computing the Shapley value for a new class of cooperative games that we call budgeted games, and investigate in particular knapsack budgeted games, a version … We propose the study of computing the Shapley value for a new class of cooperative games that we call budgeted games, and investigate in particular knapsack budgeted games, a version modeled after the classical knapsack problem. In these games, the "value" of a set $S$ of agents is determined only by a critical subset $T\subseteq S$ of the agents and not the entirety of $S$ due to a budget constraint that limits how large $T$ can be. We show that the Shapley value can be computed in time faster than by the na\"ive exponential time algorithm when there are sufficiently many agents, and also provide an algorithm that approximates the Shapley value within an additive error. For a related budgeted game associated with a greedy heuristic, we show that the Shapley value can be computed in pseudo-polynomial time. Furthermore, we generalize our proof techniques and propose what we term algorithmic representation framework that captures a broad class of cooperative games with the property of efficient computation of the Shapley value. The main idea is that the problem of determining the efficient computation can be reduced to that of finding an alternative representation of the games and an associated algorithm for computing the underlying value function with small time and space complexities in the representation size.
View PDF Chat

Minimizing Latency in Online Ride and Delivery Services

2018-01-01
Abhimanyu Das , Sreenivas Gollapudi , Anthony Kim +2 more
Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles … Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles located at depots to serve request located on a metric space so as to minimize the total latency. In this paper, we consider point-to-point requests that come with source-destination pairs and release-time constraints that restrict when each request can be served. The point-to-point requests and release-time constraints model taxi rides and deliveries. For all the variants considered, we show constant-factor approximation algorithms based on a linear programming framework. To the best of our knowledge, these are the first set of results for the aforementioned variants of the minimum latency problems. Furthermore, we provide an empirical study of heuristics based on our theoretical algorithms on a real data set of taxi rides.
View PDF Chat

ĐÁNH GIÁ HIỆU QUẢ CHƯƠNG TRÌNH QUẢN LÝ TĂNG HUYẾT ÁP TẠI MỘT SỐ TRẠM Y TẾ XÃ TỈNH NINH BÌNH

2025-05-14
Giang Nguyễn Hoàng , My Đỗ Trà , Thắng Nguyễn Thị +2 more
Nghiên cứu nhằm đánh giá hiệu quả của một chương trình can thiệp tại tuyến y tế cơ sở ở tỉnh Ninh Bình, Việt Nam. Thiết kế nghiên cứu phỏng … Nghiên cứu nhằm đánh giá hiệu quả của một chương trình can thiệp tại tuyến y tế cơ sở ở tỉnh Ninh Bình, Việt Nam. Thiết kế nghiên cứu phỏng thực nghiệm, đánh giá trước và sau can thiệp có nhóm chứng, được triển khai tại 6 trạm y tế xã thuộc tỉnh Ninh Bình. Tổng cộng 470 người bệnh được theo dõi trong suốt quá trình nghiên cứu từ năm 2021 đến 2023. Dữ liệu được thu thập thông qua phỏng vấn trực tiếp bằng bảng hỏi điện tử trước và sau can thiệp, sau đó phân tích bằng phần mềm Stata với phương pháp phân tích sự khác biệt trong khác biệt để đánh giá kết quả can thiệp. Kết quả cho thấy, người bệnh tại nhóm can thiệp có cải thiện đáng kể về kiến thức, thái độ, thực hành điều chỉnh lối sống, tuân thủ điều trị và tái khám định kỳ so với nhóm chứng. Mô hình cho thấy tính khả thi và hiệu quả trong việc tăng cường quản lý tăng huyết áp tại tuyến y tế cơ sở. Nghiên cứu khuyến nghị mở rộng mô hình này và tích hợp vào chương trình quản lý bệnh mạn tính tại cộng đồng.

ĐÁNH GIÁ HIỆU QUẢ CHƯƠNG TRÌNH QUẢN LÝ TĂNG HUYẾT ÁP TẠI MỘT SỐ TRẠM Y TẾ XÃ TỈNH NINH BÌNH

2025-05-14
Giang Nguyễn Hoàng , My Đỗ Trà , Thắng Nguyễn Thị +2 more
Nghiên cứu nhằm đánh giá hiệu quả của một chương trình can thiệp tại tuyến y tế cơ sở ở tỉnh Ninh Bình, Việt Nam. Thiết kế nghiên cứu phỏng … Nghiên cứu nhằm đánh giá hiệu quả của một chương trình can thiệp tại tuyến y tế cơ sở ở tỉnh Ninh Bình, Việt Nam. Thiết kế nghiên cứu phỏng thực nghiệm, đánh giá trước và sau can thiệp có nhóm chứng, được triển khai tại 6 trạm y tế xã thuộc tỉnh Ninh Bình. Tổng cộng 470 người bệnh được theo dõi trong suốt quá trình nghiên cứu từ năm 2021 đến 2023. Dữ liệu được thu thập thông qua phỏng vấn trực tiếp bằng bảng hỏi điện tử trước và sau can thiệp, sau đó phân tích bằng phần mềm Stata với phương pháp phân tích sự khác biệt trong khác biệt để đánh giá kết quả can thiệp. Kết quả cho thấy, người bệnh tại nhóm can thiệp có cải thiện đáng kể về kiến thức, thái độ, thực hành điều chỉnh lối sống, tuân thủ điều trị và tái khám định kỳ so với nhóm chứng. Mô hình cho thấy tính khả thi và hiệu quả trong việc tăng cường quản lý tăng huyết áp tại tuyến y tế cơ sở. Nghiên cứu khuyến nghị mở rộng mô hình này và tích hợp vào chương trình quản lý bệnh mạn tính tại cộng đồng.

Welfare maximization with production costs: A primal dual approach

2018-03-18
Zhiyi Huang , Anthony Kim
View PDF Chat

Minimizing Latency in Online Ride and Delivery Services

2018-02-08
Abhimanyu Das , Sreenivas Gollapudi , Anthony Kim +2 more
Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles … Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles located at depots to serve request located on a metric space so as to minimize the total latency. In this paper, we consider point-to-point requests that come with source-destination pairs and release-time constraints that restrict when each request can be served. The point-to-point requests and release-time constraints model taxi rides and deliveries. For all the variants considered, we show constant-factor approximation algorithms based on a linear programming framework. To the best of our knowledge, these are the first set of results for the aforementioned variants of the minimum latency problems. Furthermore, we provide an empirical study of heuristics based on our theoretical algorithms on a real data set of taxi rides.

Minimizing Latency in Online Ride and Delivery Services

2018-01-01
Abhimanyu Das , Sreenivas Gollapudi , Anthony Kim +2 more
Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles … Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles located at depots to serve requests located on a metric space so as to minimize the total latency. In this paper, we consider point-to-point requests that come with source-destination pairs and release-time constraints that restrict when each request can be served. The point-to-point requests and release-time constraints model taxi rides and deliveries. For all the variants considered, we show constant-factor approximation algorithms based on a linear programming framework. To the best of our knowledge, these are the first set of results for the aforementioned variants of the minimum latency problems. Furthermore, we provide an empirical study of heuristics based on our theoretical algorithms on a real data set of taxi rides.
View PDF Chat

Minimizing Latency in Online Ride and Delivery Services

2018-01-01
Abhimanyu Das , Sreenivas Gollapudi , Anthony Kim +2 more
Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles … Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles located at depots to serve request located on a metric space so as to minimize the total latency. In this paper, we consider point-to-point requests that come with source-destination pairs and release-time constraints that restrict when each request can be served. The point-to-point requests and release-time constraints model taxi rides and deliveries. For all the variants considered, we show constant-factor approximation algorithms based on a linear programming framework. To the best of our knowledge, these are the first set of results for the aforementioned variants of the minimum latency problems. Furthermore, we provide an empirical study of heuristics based on our theoretical algorithms on a real data set of taxi rides.
View PDF Chat

Depth First Always On Routing Trace Algorithm

2017-01-01
Anthony Kim , Sung Hyun Chen , Zheng Chen
In this paper, we discussed current limitation in the electronic-design-automotation (EDA) tool on tracing the always on routing. We developed an algorithm to efficiently track the secondary power routing and … In this paper, we discussed current limitation in the electronic-design-automotation (EDA) tool on tracing the always on routing. We developed an algorithm to efficiently track the secondary power routing and accurately estimate the routing quality using approximate voltage drop as the criteria. The fast check can identify potential hotspot issues without going through sign-off checks. It helps designers to capture issues at early stages and fix the issues with less design effort. We also discussed some limitations to our algorithm.

Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems

2015-01-01
Anthony Kim
View PDF Chat

Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems

2015-01-01
Anthony Kim
We design approximate weakly group strategy-proof mechanisms for resource reallocation problems using Milgrom and Segal's deferred acceptance auction framework: the radio spectrum and network bandwidth reallocation problems in the procurement … We design approximate weakly group strategy-proof mechanisms for resource reallocation problems using Milgrom and Segal's deferred acceptance auction framework: the radio spectrum and network bandwidth reallocation problems in the procurement auction setting and the cost minimization problem with set cover constraints in the selling auction setting. Our deferred acceptance auctions are derived from simple greedy algorithms for the underlying optimization problems and guarantee approximately optimal social welfare (cost) of the agents retaining their rights (contracts). In the reallocation problems, we design procurement auctions to purchase agents' broadcast/access rights to free up some of the resources such that the unpurchased rights can still be exercised with respect to the remaining resources. In the cost minimization problem, we design a selling auction to sell early termination rights to agents with existing contracts such that some minimal constraints are still satisfied with remaining contracts. In these problems, while the "allocated" agents transact, exchanging rights and payments, the objective and feasibility constraints are on the "rejected" agents.
View PDF Chat

Welfare Maximization with Production Costs: A Primal Dual Approach

2014-12-22
Zhiyi Huang , Anthony Kim
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Welfare Maximization with Production Costs: A Primal Dual ApproachZhiyi Huang and Anthony KimZhiyi Huang … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Welfare Maximization with Production Costs: A Primal Dual ApproachZhiyi Huang and Anthony KimZhiyi Huang and Anthony Kimpp.59 - 72Chapter DOI:https://doi.org/10.1137/1.9781611973730.6PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We study online combinatorial auctions with production costs proposed by Blum et al. [4] 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. [a], Blum et al. [4], and Buchbinder and Conen [6]. Our lower bounds apply to randomized algorithms and resolve an open problem by Buchbinder and Gonen [6]. Previous chapter Next chapter RelatedDetails Published:2015ISBN:978-1-61197-374-7eISBN:978-1-61197-373-0 https://doi.org/10.1137/1.9781611973730Book Series Name:ProceedingsBook Code:PRDA15Book Pages:viii + 2048
View PDF Chat

The Shapley Value in Knapsack Budgeted Games

2014-09-18
Smriti Bhagat , Anthony Kim , S. Muthukrishnan +1 more
We propose the study of computing the Shapley for a new class of cooperative games that we call budgeted games, and investigate in particular knapsack budgeted games, a version modeled … We propose the study of computing the Shapley for a new class of cooperative games that we call budgeted games, and investigate in particular knapsack budgeted games, a version modeled after the classical knapsack problem. In these games, the value of a set $S$ of agents is determined only by a critical subset $T\subseteq S$ of the agents and not the entirety of $S$ due to a budget constraint that limits how large $T$ can be. We show that the Shapley can be computed in time faster than by the naive exponential time algorithm when there are sufficiently many agents, and also provide an algorithm that approximates the Shapley within an additive error. For a related budgeted game associated with a greedy heuristic, we show that the Shapley can be computed in pseudo-polynomial time. Furthermore, we generalize our proof techniques and propose what we term algorithmic representation framework that captures a broad class of cooperative games with the property of efficient computation of the Shapley value. The main idea is that the problem of determining the efficient computation can be reduced to that of finding an alternative representation of the games and an associated algorithm for computing the underlying function with small time and space complexities in the representation size.

The Shapley Value in Knapsack Budgeted Games

2014-01-01
Smriti Bhagat , Anthony Kim , S. Muthukrishnan +1 more
View PDF Chat

The Shapley Value in Knapsack Budgeted Games

2014-01-01
Smriti Bhagat , Anthony Kim , S. Muthukrishnan +1 more
We propose the study of computing the Shapley value for a new class of cooperative games that we call budgeted games, and investigate in particular knapsack budgeted games, a version … We propose the study of computing the Shapley value for a new class of cooperative games that we call budgeted games, and investigate in particular knapsack budgeted games, a version modeled after the classical knapsack problem. In these games, the "value" of a set $S$ of agents is determined only by a critical subset $T\subseteq S$ of the agents and not the entirety of $S$ due to a budget constraint that limits how large $T$ can be. We show that the Shapley value can be computed in time faster than by the na\"ive exponential time algorithm when there are sufficiently many agents, and also provide an algorithm that approximates the Shapley value within an additive error. For a related budgeted game associated with a greedy heuristic, we show that the Shapley value can be computed in pseudo-polynomial time. Furthermore, we generalize our proof techniques and propose what we term algorithmic representation framework that captures a broad class of cooperative games with the property of efficient computation of the Shapley value. The main idea is that the problem of determining the efficient computation can be reduced to that of finding an alternative representation of the games and an associated algorithm for computing the underlying value function with small time and space complexities in the representation size.
View PDF Chat

Welfare Maximization with Production Costs: A Primal Dual Approach

2014-01-01
Zhiyi Huang , Anthony Kim
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 … 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.
View PDF Chat

Computing bounds on network capacity regions as a polytope reconstruction problem

2011-07-01
Anthony Kim , Muriel Médard
We define a notion of network capacity region of networks that generalizes the notion of network capacity defined by Cannons et al. and prove its notable properties such as closedness, … We define a notion of network capacity region of networks that generalizes the notion of network capacity defined by Cannons et al. and prove its notable properties such as closedness, boundedness and convexity when the finite field is fixed. We show that the network routing capacity region is a computable rational polytope and provide exact algorithms and approximation heuristics for computing the region. We define the semi-network linear coding capacity region, with respect to a fixed finite field, that inner bounds the corresponding network linear coding capacity region, show that it is a computable rational polytope, and provide exact algorithms and approximation heuristics. We show connections between computing these regions and a polytope reconstruction problem and some combinatorial optimization problems, such as the minimum cost directed Steiner tree problem. We provide an example to illustrate our results. The algorithms are not necessarily polynomial-time.
View PDF Chat

Scalar-linear solvability of matroidal networks associated with representable matroids

2010-09-01
Anthony Kim , Muriel Médard
We study matroidal networks introduced by Dougherty et al. We prove the converse of the following theorem: If a network is scalar-linearly solvable over some finite field, then the network … We study matroidal networks introduced by Dougherty et al. We prove the converse of the following theorem: If a network is scalar-linearly solvable over some finite field, then the network is a matroidal network associated with a representable matroid over a finite field. It follows that a network is scalar-linearly solvable if and only if the network is a matroidal network associated with a representable matroid over a finite field. We note that this result combined with the construction method due to Dougherty et al. gives a method for generating scalar-linearly solvable networks. Using the converse implicitly, we demonstrate scalar-linear solvability of two classes of matroidal networks: networks constructed from uniform matroids and those constructed from graphic matroids.
View PDF Chat
Coauthor Papers Together
Debmalya Panigrahi 3
Udi Weinsberg 3
Smriti Bhagat 3
Sreenivas Gollapudi 3
Abhimanyu Das 3
Chaitanya Swamy 3
Muriel Médard 2
Zhiyi Huang 2
S. Muthukrishnan 2
S. Muthukrishnan 1
Oanh Trần Thị 1
Zhiyi Huang 1
Zheng Chen 1
Sung Hyun Chen 1
Giang Nguyễn Hoàng 1
Thắng Nguyễn Thị 1
My Đỗ Trà 1

Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality

2013-04-20
Tomasz Michalak , Karthik Aadithya , Piotr Szczepański +2 more
The Shapley value---probably the most important normative payoff division scheme in coalitional games---has recently been advocated as a useful measure of centrality in networks. However, although this approach has a … The Shapley value---probably the most important normative payoff division scheme in coalitional games---has recently been advocated as a useful measure of centrality in networks. However, although this approach has a variety of real-world applications (including social and organisational networks, biological networks and communication networks), its computational properties have not been widely studied. To date, the only practicable approach to compute Shapley value-based centrality has been via Monte Carlo simulations which are computationally expensive and not guaranteed to give an exact answer. Against this background, this paper presents the first study of the computational aspects of the Shapley value for network centralities. Specifically, we develop exact analytical formulae for Shapley value-based centrality in both weighted and unweighted networks and develop efficient (polynomial time) and exact algorithms based on them. We empirically evaluate these algorithms on two real-life examples (an infrastructure network representing the topology of the Western States Power Grid and a collaboration network from the field of astrophysics) and demonstrate that they deliver significant speedups over the Monte Carlo approach. For instance, in the case of unweighted networks our algorithms are able to return the exact solution about 1600 times faster than the Monte Carlo approximation, even if we allow for a generous 10% error margin for the latter method.
View PDF Chat

Linear-Programming based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems

2014-11-17
Ian Post , Chaitanya Swamy
We consider various {\em multi-vehicle versions of the minimum latency problem}. There is a fleet of $k$ vehicles located at one or more depot nodes, and we seek a collection … We consider various {\em multi-vehicle versions of the minimum latency problem}. There is a fleet of $k$ vehicles located at one or more depot nodes, and we seek a collection of routes for these vehicles that visit all nodes so as to minimize the total latency incurred, which is the sum of the client waiting times. We obtain an $8.497$-approximation for the version where vehicles may be located at multiple depots and a $7.183$-approximation for the version where all vehicles are located at the same depot, both of which are the first improvements on this problem in a decade. Perhaps more significantly, our algorithms exploit various LP-relaxations for minimum-latency problems. We show how to effectively leverage two classes of LPs---{\em configuration LPs} and {\em bidirected LP-relaxations}---that are often believed to be quite powerful but have only sporadically been effectively leveraged for network-design and vehicle-routing problems. This gives the first concrete evidence of the effectiveness of LP-relaxations for this class of problems. The $8.497$-approximation the multiple-depot version is obtained by rounding a near-optimal solution to an underlying configuration LP for the problem. The $7.183$-approximation can be obtained both via rounding a bidirected LP for the single-depot problem or via more combinatorial means. The latter approach uses a bidirected LP to obtain the following key result that is of independent interest: for any $k$, we can efficiently compute a rooted tree that is at least as good, with respect to the prize-collecting objective (i.e., edge cost + number of uncovered nodes) as the best collection of $k$ rooted paths. Our algorithms are versatile and extend easily to handle various extensions involving: (i) weighted sum of latencies, (ii) constraints specifying which depots may serve which nodes, (iii) node service times.

The minimum latency problem

1994-01-01
Avrim Blum , Prasad Chalasani , Don Coppersmith +3 more
Article The minimum latency problem Share on Authors: Avrim Blum School of Computer Science, CMU School of Computer Science, CMUView Profile , Prasad Chalasani School of Computer Science, CMU School … Article The minimum latency problem Share on Authors: Avrim Blum School of Computer Science, CMU School of Computer Science, CMUView Profile , Prasad Chalasani School of Computer Science, CMU School of Computer Science, CMUView Profile , Don Coppersmith IBM T.J. Watson Research Center IBM T.J. Watson Research CenterView Profile , Bill Pulleyblank IBM T.J. Watson Research Center IBM T.J. Watson Research CenterView Profile , Prabhakar Raghavan IBM T.J. Watson Research Center IBM T.J. Watson Research CenterView Profile , Madhu Sudan IBM T.J. Watson Research Center IBM T.J. Watson Research CenterView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 163–171https://doi.org/10.1145/195058.195125Online:23 May 1994Publication History 174citation1,215DownloadsMetricsTotal Citations174Total Downloads1,215Last 12 Months78Last 6 weeks13 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access
View PDF Chat

On describing the routing capacity regions of networks

2010-05-03
Ali Kakhbod , S. M. Sadegh Tabatabaei Yazdi
View PDF Chat

Market Equilibrium with Transaction Costs

2010-01-01
Sourav Chakraborty , Nikhil R. Devanur , Chinmay Karande
View PDF Chat

Limitations of Randomized Mechanisms for Combinatorial Auctions

2011-10-01
Shaddin Dughmi , Jan Vondr ́k
The design of computationally efficient and incentive compatible mechanisms that solve or approximate fundamental resource allocation problems is the main goal of algorithmic mechanism design. A central example in both … The design of computationally efficient and incentive compatible mechanisms that solve or approximate fundamental resource allocation problems is the main goal of algorithmic mechanism design. A central example in both theory and practice is welfare-maximization in combinatorial auctions. Recently, a randomized mechanism has been discovered for combinatorial auctions that is truthful in expectation and guarantees a (1-1/e)-approximation to the optimal social welfare when players have coverage valuations [DRY11]. This approximation ratio is the best possible even for non-truthful algorithms, assuming P does not equal NP. Given the recent sequence of negative results for combinatorial auctions under more restrictive notions of incentive compatibility, this development raises a natural question: Are truthful-in-expectation mechanisms compatible with polynomial-time approximation in a way that deterministic or universally truthful mechanisms are not? In particular, can polynomial-time truthful-in-expectation mechanisms guarantee a near-optimal approximation ratio for more general variants of combinatorial auctions? We prove that this is not the case. Specifically, the result of [DRY11] cannot be extended to combinatorial auctions with sub modular valuations in the value oracle model. (Absent strategic considerations, a (1-1/e)-approximation is still achievable in this setting.) More precisely, we prove that there is a constant \gamma>0 such that there is no randomized mechanism that is truthful-in-expectation -- or even approximately truthful-in-expectation -- and guarantees an m^{-\gamma}-approximation to the optimal social welfare for combinatorial auctions with sub modular valuations in the value oracle model. We also prove an analogous result for the flexible combinatorial public projects (CPP) problem, where a truthful-in-expectation $(1-1/e)$-approximation for coverage valuations has been recently developed [Dughmi11]. We show that there is no truthful-in-expectation -- or even approximately truthful-in-expectation -- mechanism that achieves an m^{-\gamma}-approximation to the optimal social welfare for combinatorial public projects with sub modular valuations in the value oracle model. Both our results present an unexpected separation between coverage functions and sub modular functions, which does not occur for these problems without strategic considerations.
View PDF Chat

Polytope Containment and Determination by Linear Probes

1995-05-01
Peter Gritzmann , Victor Klee , John Westwater
As the terms are used here, a body in Rd is a compact convex set with non-empty interior, and a polytope is a body that has only finitely many extreme … As the terms are used here, a body in Rd is a compact convex set with non-empty interior, and a polytope is a body that has only finitely many extreme points. The class of all bodies whose interior includes the origin 0 is denoted by C 0 d . A set X is symmetric if X = −X. The ray-oracle of a body C ∈ C 0 d is the function Oc which, accepting as input an arbitrary ray R issuing from 0, produces the point at which R intersects the boundary of C. This paper is concerned with a few central aspects of the following general question: given certain information about C, what additional information can be obtained by questioning the ray-oracle, and how efficiently can it be obtained? It is assumed that infinite-precision real arithmetic and the usual vector operations in Rd are available at no cost, so the efficiency of an algorithm is measured solely in terms of its number of calls to the ray-oracle. The paper discusses two main problems, the first of which—the containment problem—arose from a question in abstract numerical analysis. Here the goal is to construct a polytope P(not necessarily in any sense a small one) that contains C, where this requires precise specification of the vertices of P. There are some sharp positive results for the case in which d = 2 and C is known not to be too asymmetric, but the main result on the containment problem is negative. It asserts that when d ⩾ 3 and the body is known only to be rotund and symmetric, there is no algorithm for the containment problem. This is the case even when there is available a certain master oracle whose question-answering power far exceeds that of the ray-oracle. However, it turns out that even when there is no additional information about C, the following relaxation of the containment problem admits an algorithmic solution based solely on the ray-oracle: construct a polytope containing C or conclude that the centred condition number of C exceeds a prescribed bound. In the other main problem—the reconstruction problem— it is known only that C is itself a polytope and the problem is to construct C with the aid of a finite number of calls to the ray-oracle. That is accomplished with a number of calls that depends on the number of faces (and hence on the ‘combinatorial complexity’) of C.

Welfare and Profit Maximization with Production Costs

2011-10-01
Avrim Blum , Anupam Gupta , Yishay Mansour +1 more
Combinatorial Auctions are a central problem in Algorithmic Mechanism Design: pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare, revenue, … Combinatorial Auctions are a central problem in Algorithmic Mechanism Design: pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare, revenue, or profit). The problem has been well-studied in the case of limited supply (one copy of each item), and in the case of digital goods (the seller can produce additional copies at no cost). Yet in the case of resources -- oil, labor, computing cycles, etc. -- neither of these abstractions is just right: additional supplies of these resources can be found, but at increasing difficulty (marginal cost) as resources are depleted. In this work, we initiate the study of the algorithmic mechanism design problem of combinatorial pricing under increasing marginal cost. The goal is to sell these goods to buyers with unknown and arbitrary combinatorial valuation functions to maximize either the social welfare, or the seller's profit, specifically we focus on the setting of posted item prices with buyers arriving online. We give algorithms that achieve constant factor approximations for a class of natural cost functions - linear, low-degree polynomial, logarithmic - and that give logarithmic approximations for more general increasing marginal cost functions (along with a necessary additive loss). We show that these bounds are essentially best possible for these settings.
View PDF Chat

Dynamic and Nonuniform Pricing Strategies for Revenue Maximization

2013-01-01
Tanmoy Chakraborty , Zhiyi Huang , Sanjeev Khanna
We consider the item pricing problem for revenue maximization, where a single seller with multiple distinct items caters to multiple buyers with unknown subadditive valuation functions who arrive in a … We consider the item pricing problem for revenue maximization, where a single seller with multiple distinct items caters to multiple buyers with unknown subadditive valuation functions who arrive in a sequence. The seller sets the prices on individual items, and we design randomized pricing strategies to maximize expected revenue. We consider dynamic uniform strategies, which can change the price upon the arrival of each buyer but the price on all unsold items is the same at all times, and static nonuniform strategies, which can assign different prices to different items but can never change it after setting it initially. We design pricing strategies that guarantee poly-logarithmic (in number of items) approximation to maximum possible social welfare, which is an upper bound on revenue. We also show that any static uniform pricing strategy cannot yield such approximation, thus highlighting a large gap between the powers of dynamic and static pricing. Finally, our pricing strategies imply poly-logarithmic approximation for revenue-optimal incentive compatible mechanisms, in multiparameter combinatorial auctions with subaddititve buyer valuations, which is the best known guarantee given by efficient mechanisms for both prior-free and Bayesian settings.
View PDF Chat

Network coding capacity: A functional dependence bound

2009-06-01
Satyajit Thakor , Alex Grant , Terence Chan
Explicit characterization and computation of the multi-source network coding capacity region (or even bounds) is long standing open problem. In fact, finding the capacity region requires determination of the set … Explicit characterization and computation of the multi-source network coding capacity region (or even bounds) is long standing open problem. In fact, finding the capacity region requires determination of the set of all entropic vectors Gamma*, which is known to be an extremely hard problem. On the other hand, calculating the explicitly known linear programming bound is very hard in practice due to an exponential growth in complexity as a function of network size. We give a new, easily computable outer bound, based on characterization of all functional dependencies in networks. We also show that the proposed bound is tighter than some known bounds.
View PDF Chat

Simple heuristics for unit disk graphs

1995-03-01
Madhav Marathe , Heinz Breu , Harry B. Hunt +2 more
Abstract Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP‐hard optimization problems … Abstract Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP‐hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring, and minimum dominating set. We also present an on‐line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and intersection graphs of higher dimensional regular objects.
View PDF Chat

On Network Coding Capacity - Matroidal Networks and Network Capacity Regions

2011-01-01
Anthony Eli Kim
One fundamental problem in the field of network coding is to determine the network coding capacity of networks under various network coding schemes. In this thesis, we address the problem … One fundamental problem in the field of network coding is to determine the network coding capacity of networks under various network coding schemes. In this thesis, we address the problem with two approaches: matroidal networks and capacity regions. In our matroidal approach, we prove the converse of the theorem which states that, if a network is scalar-linearly solvable then it is a matroidal network associated with a representable matroid over a finite field. As a consequence, we obtain a correspondence between scalar-linearly solvable networks and representable matroids over finite fields in the framework of matroidal networks. We prove a theorem about the scalar-linear solvability of networks and field characteristics. We provide a method for generating scalar-linearly solvable networks that are potentially different from the networks that we already know are scalar-linearly solvable. In our capacity region approach, we define a multi-dimensional object, called the network capacity region, associated with networks that is analogous to the rate regions in information theory. For the network routing capacity region, we show that the region is a computable rational polytope and provide exact algorithms and approximation heuristics for computing the region. For the network linear coding capacity region, we construct a computable rational polytope, with respect to a given finite field, that inner bounds the linear coding capacity region and provide exact algorithms and approximation heuristics for computing the polytope. The exact algorithms and approximation heuristics we present are not polynomial time schemes and may depend on the output size.
View PDF Chat

Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems

2015-01-01
Anthony Kim
View PDF Chat

Limitations of randomized mechanisms for combinatorial auctions

2014-01-31
Shaddin Dughmi , Jan Vondrák
View PDF Chat

Non Uniform On Chip Power Delivery Network Synthesis Methodology

2017-01-01
Patrick Benediktsson , Jon A. Flandrin , Zheng Chen
In this paper, we proposed a non-uniform power delivery network (PDN) synthesis methodology. It first constructs initial PDN using uniform approach. Then preliminary power integrity analysis is performed to derive … In this paper, we proposed a non-uniform power delivery network (PDN) synthesis methodology. It first constructs initial PDN using uniform approach. Then preliminary power integrity analysis is performed to derive IR-safe candidate window. Congestion map is obtained based global route congestion estimation. A self-adaptive non-uniform PDN synthesis is then performed to globally and locally optimize PDN over selected regions. The PDN synthesis is congestion-driven and IR- guarded. Experimental results show significant timing important in trade-off small PDN length reduction with no EM/IR impact. We further explored potential power savings using our non-uniform PDN synthesis methodology.

Customized Routing Optimization Based on Gradient Boost Regressor Model

2017-01-01
Zheng Chen , Clara Grzegorz Kasprowicz , Carol Saunders
In this paper, we discussed limitation of current electronic-design-automoation (EDA) tool and proposed a machine learning framework to overcome the limitations and achieve better design quality. We explored how to … In this paper, we discussed limitation of current electronic-design-automoation (EDA) tool and proposed a machine learning framework to overcome the limitations and achieve better design quality. We explored how to efficiently extract relevant features and leverage gradient boost regressor (GBR) model to predict underestimated risky net (URN). Customized routing optimizations are applied to the URNs and results show clear timing improvement and trend to converge toward timing closure.

Price of Anarchy for Greedy Auctions

2010-01-17
Brendan Lucier , Allan Borodin
Previous chapter Next chapter Full AccessProceedings Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Price of Anarchy for Greedy AuctionsB. Lucier and A. BorodinB. Lucier and A. Borodinpp.537 … Previous chapter Next chapter Full AccessProceedings Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Price of Anarchy for Greedy AuctionsB. Lucier and A. BorodinB. Lucier and A. Borodinpp.537 - 553Chapter DOI:https://doi.org/10.1137/1.9781611973075.46PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We study mechanisms for utilitarian combinatorial allocation problems, where agents are not assumed to be single-minded. This class of problems includes combinatorial auctions, multi-unit auctions, unsplittable flow problems, and others. We focus on the problem of designing mechanisms that approximately optimize social welfare at every Bayes-Nash equilibrium (BNE), which is the standard notion of equilibrium in settings of incomplete information. For a broad class of greedy approximation algorithms, we give a general black-box reduction to deterministic mechanisms with almost no loss to the approximation ratio at any BNE. We also consider the special case of Nash equilibria in full-information games, where we obtain tightened results. This solution concept is closely related to the well-studied price of anarchy. Furthermore, for a rich subclass of allocation problems, pure Nash equilibria are guaranteed to exist for our mechanisms. For many problems, the approximation factors we obtain at equilibrium improve upon the best known results for deterministic truthful mechanisms. In particular, we exhibit a simple deterministic mechanism for general combinatorial auctions that obtains an approximation at every BNE. Previous chapter Next chapter RelatedDetails Published:2010ISBN:978-0-89871-701-3eISBN:978-1-61197-307-5 https://doi.org/10.1137/1.9781611973075Book Series Name:ProceedingsBook Code:PR135Book Pages:xviii + 1667
View PDF Chat

Polynomial time approximation schemes for the traveling repairman and other minimum latency problems.

2013-12-18
René Sitters
We give a polynomial time, (1 + ∊)-approximation algorithm for the traveling repairman problem (TRP) in the Euclidean plane, on weighted planar graphs, and on weighted trees. This improves on … We give a polynomial time, (1 + ∊)-approximation algorithm for the traveling repairman problem (TRP) in the Euclidean plane, on weighted planar graphs, and on weighted trees. This improves on the known quasi-polynomial time approximation schemes for these problems. The algorithm is based on a simple technique that reduces the TRP to what we call the segmented TSP. Here, we are given numbers l1, …, lK and n1, …, nK and we need to find a path that visits at least nh points within path distance lh from the starting point for all h ∊ {1, …, K}. A solution is α-approximate if at least nh points are visited within distance αlh. It is shown that any algorithm that is α-approximate for every constant K in some metric space, gives an α(1 + ∊)-approximation for the TRP in the same metric space. Subsequently, approximation schemes are given for this segmented TSP problem in different metric spaces. The segmented TSP with only one segment (K = 1) is equivalent to the k-TSP for which a (2 + ∊)-approximation is known for a general metric space. Hence, this approach through the segmented TSP gives new impulse for improving on the 3.59-approximation for TRP in a general metric space. A similar reduction applies to many other minimum latency problems. To illustrate the strength of this approach we apply it to the well-studied scheduling problem of minimizing total weighted completion time under precedence constraints, 1|prec|Σ wjCj, and present a polynomial time approximation scheme for the case of interval order precedence constraints. This improves on the known 3/2-approximation for this problem. Both approximation schemes apply as well if release dates are added to the problem.
View PDF Chat

From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions

2011-01-01
Shaddin Dughmi , Tim Roughgarden , Qiqi Yan
We design an expected polynomial-time, truthful-in-expectation, (1-1/e)-approximation mechanism for welfare maximization in a fundamental class of combinatorial auctions. Our results apply to bidders with valuations that are m matroid rank … We design an expected polynomial-time, truthful-in-expectation, (1-1/e)-approximation mechanism for welfare maximization in a fundamental class of combinatorial auctions. Our results apply to bidders with valuations that are m matroid rank sums (MRS), which encompass most concrete examples of submodular functions studied in this context, including coverage functions, matroid weighted-rank functions, and convex combinations thereof. Our approximation factor is the best possible, even for known and explicitly given coverage valuations, assuming P != NP. Ours is the first truthful-in-expectation and polynomial-time mechanism to achieve a constant-factor approximation for an NP-hard welfare maximization problem in combinatorial auctions with heterogeneous goods and restricted valuations. Our mechanism is an instantiation of a new framework for designing approximation mechanisms based on randomized rounding algorithms. A typical such algorithm first optimizes over a fractional relaxation of the original problem, and then randomly rounds the fractional solution to an integral one. With rare exceptions, such algorithms cannot be converted into truthful mechanisms. The high-level idea of our mechanism design framework is to optimize directly over the (random) output of the rounding algorithm, rather than over the input to the rounding algorithm. This approach leads to truthful-in-expectation mechanisms, and these mechanisms can be implemented efficiently when the corresponding objective function is concave. For bidders with MRS valuations, we give a novel randomized rounding algorithm that leads to both a concave objective function and a (1-1/e)-approximation of the optimal welfare.
View PDF Chat

2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011)

2011-01-01
Yevgeniy Dodis , Xin Li , Trevor D. Wooley +1 more
View PDF Chat

Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling

2013-01-01
Anupam Gupta , Ravishankar Krishnaswamy , Kirk Pruhs
View PDF Chat

The Shapley Value in Knapsack Budgeted Games

2014-01-01
Smriti Bhagat , Anthony Kim , S. Muthukrishnan +1 more
View PDF Chat

Mission impossible: Computing the network coding capacity region

2008-07-01
Terence Chan , Alex Grant
One of the main theoretical motivations for the emerging area of network coding is the achievability of the max-flow/min-cut rate for single source multicast. This can exceed the rate achievable … One of the main theoretical motivations for the emerging area of network coding is the achievability of the max-flow/min-cut rate for single source multicast. This can exceed the rate achievable with routing alone, and is achievable with linear network codes. The multi-source problem is more complicated. Computation of its capacity region is equivalent to determination of the set of all entropy functions Gamma*, which is non-polyhedral. The aim of this paper is to demonstrate that this difficulty can arise even in single source problems. In particular, for single source networks with hierarchical sink requirements, and for single source networks with secrecy constraints. In both cases, we exhibit networks whose capacity regions involve Gamma*. As in the multi-source case, linear codes are insufficient.
View PDF Chat

A Rational Convex Program for Linear Arrow-Debreu Markets

2016-10-10
Nikhil R. Devanur , Jugal Garg , László A. Végh
We present a new flow-type convex program describing equilibrium solutions to linear Arrow-Debreu markets. Whereas convex formulations were previously known ([Nenakov and Primak 1983; Jain 2007; Cornet 1989]), our program … We present a new flow-type convex program describing equilibrium solutions to linear Arrow-Debreu markets. Whereas convex formulations were previously known ([Nenakov and Primak 1983; Jain 2007; Cornet 1989]), our program exhibits several new features. It provides a simple necessary and sufficient condition and a concise proof of the existence and rationality of equilibria, settling an open question raised by Vazirani [2012]. As a consequence, we also obtain a simple new proof of the result in Mertens [2003] that the equilibrium prices form a convex polyhedral set.
View PDF Chat