NDLI: Matroid Online Bipartite Matching and Vertex Cover

Please wait, while we are loading the content...

Ironing in the Dark

Position-Indexed Formulations for Kidney Exchange

Deferred Acceptance with Compensation Chains

The Revelation Principle for Mechanism Design with Reporting Costs

When Should an Expert Make a Prediction?

Optimal Commitments in Asymmetric Auctions with Incomplete Information

On Voting and Facility Location

Planning Problems for Sophisticated Agents with Present Bias

The Invisible Hand of Dynamic Market Pricing

Dynamic Pricing in a Labor Market: Surge Pricing and Flexible Work on the Uber Platform

Imperfect-Recall Abstractions with Bounds in Games

The Seasonality Of Paid Search Effectiveness From A Long Running Field Test

Mechanism Design for Subadditive Agents via an Ex Ante Relaxation

General Threshold Model for Social Cascades: Analysis and Simulations

Pricing with Limited Knowledge of Demand

Computational Extensive-Form Games

Strategic Payment Routing in Financial Credit Networks

Petty Envy When Assigning Objects

The Pareto Frontier for Random Mechanisms

Large Market Games with Near Optimal Efficiency

Truthful Outcomes from Non-Truthful Position Auctions

Fair Resource Allocation in A Volatile Marketplace

A/B Testing of Auctions

The Stochastic Matching Problem with (Very) Few Queries

Which Is the Fairest (Rent Division) of Them All?

Optimal Auctions for Negatively Correlated Items

The Possibilities and Limitations of Private Prediction Markets

Sequential Mechanisms with Ex-post Participation Guarantees

Towards Large-Scale Deliberative Decision-Making: Small Groups and the Importance of Triads

Procrastination with Variable Present Bias

Lottery Pricing Equilibria

Intrinsic Robustness of the Price of Anarchy: Abstract of the Kalai Prize Talk

A Hydraulic Approach to Equilibria of Resource Selection Games

Returns to Consumer Search: Evidence from eBay

Where to Sell: Simulating Auctions From Learning Algorithms

Impact of Community Structure on Cascades

The Strange Case of Privacy in Equilibrium Models

Ascending-Price Algorithms for Unknown Markets

Sybil Detection Using Latent Network Structure

"Strategic" Behavior in a Strategy-proof Environment

Mechanism Design with Selective Verification

Rate of Price Discovery in Iterative Combinatorial Auctions

Dynamic Mechanism Design with Budget Constrained Buyers under Limited Commitment

Revealed Preference at Scale: Learning Personalized Preferences from Assortment Choices

The FedEx Problem

Cadet-Branch Matching in a Quasi-Linear Labor Market

Strategic Ironing in Pay-as-Bid Auctions: Equilibrium Existence with Private Information

Arbitrage-Free Combinatorial Market Making via Integer Programming

Optimal Auctions with Restricted Allocations

The Unreasonable Fairness of Maximum Nash Welfare

A Dynamic Model of Crowdfunding

Online Budgeted Allocation with General Budgets

Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games

The Good, the Bad, and the Unflinchingly Selfish: Cooperative Decision-Making can be Predicted with high Accuracy when using only Three Behavioral Types

A Near-Optimal Exploration-Exploitation Approach for Assortment Selection

Dynamics of Evolving Social Groups

Bayesian Exploration: Incentivizing Exploration in Bayesian Games

Competitive Equilibrium and Trading Networks: A Network Flow Approach

Economic Recommendation Systems: One Page Abstract

On Matching and Thickness in Heterogeneous Dynamic Markets

Mechanisms with Referrals: VCG Mechanisms and Multilevel Mechanisms

On the Efficacy of Static Prices for Revenue Management in the Face of Strategic Customers

Feature-based Dynamic Pricing

Dynamic Taxes for Polynomial Congestion Games

Descending Price Optimally Coordinates Search

Virtual Demand and Stable Mechanisms

Pay-as-Bid: Selling Divisible Goods

Informed Truthfulness in Multi-Task Peer Prediction

Does Information Revelation Improve Revenue?

How Effective Can Simple Ordinal Peer Grading Be?

Blockchain Mining Games

Matroid Online Bipartite Matching and Vertex Cover

The Mysteries of Security Games: Equilibrium Computation Becomes Combinatorial Algorithm Design

Understanding Emerging Threats to Online Advertising

Minimizing Regret with Multiple Reserves

Dynamic Conflict on a Network

Persuasion with Limited Communication

Average Case Performance of Replicator Dynamics in Potential Games via Computing Regions of Attraction

Clearing Payments in Financial Networks with Credit Default Swaps [Extended Abstract]

What Matters in School Choice Tie-breakings?: How Competition Guides Design

Simple Mechanisms for Agents with Complements

Assortment Optimization under a Random Swap based Distribution over Permutations Model

Matroid Online Bipartite Matching and Vertex Cover

Content Provider	ACM Digital Library
Author	Wang, Yajun Wong, Sam Chiu-wai
Abstract	The Adwords and Online Bipartite Matching problems have enjoyed a renewed attention over the past decade due to their connection to Internet advertising. Our community has contributed, among other things, new models (notably stochastic) and extensions to the classical formulations to address the issues that arise from practical needs. In this paper, we propose a new generalization based on matroids and show that many of the previous results extend to this more general setting. Because of the rich structures and expressive power of matroids, our new setting is potentially of interest both in theory and in practice. In the classical version of the problem, the offline side of a bipartite graph is known initially while vertices from the online side arrive one at a time along with their incident edges. The objective is to maintain a decent approximate matching from which no edge can be removed. Our generalization, called Matroid Online Bipartite Matching, additionally requires that the set of matched offline vertices be independent in a given matroid. In particular, the case of partition matroids corresponds to the natural scenario where each advertiser manages multiple ads with a fixed total budget. Our algorithms attain the same performance as the classical version of the problems considered, which are often provably the best possible. We present \$1-1/e\$-competitive algorithms for Matroid Online Bipartite Matching under the small bid assumption, as well as a \$1-1/e\$-competitive algorithm for Matroid Online Bipartite Matching in the random arrival model. A key technical ingredient of our results is a carefully designed primal-dual waterfilling procedure that accommodates for matroid constraints. This is inspired by the extension of our recent charging scheme for Online Bipartite Vertex Cover. Finally, given that only few online problems were studied in the submodular fashion, the techniques introduced in this paper for tackling submodularity in the online setting may be of independent interest.
Starting Page	437
Ending Page	454
Page Count	18
File Format	PDF
ISBN	9781450339360
DOI	10.1145/2940716.2940793
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Matching Primal-dual Vertex cover
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in