Competitive algorithms for online matching and vertex cover problems

Competitive algorithms for online matching and vertex cover problems

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013.

Bibliographic Details
Main Author:	Wong, Chiu Wai, M. Eng. Massachusetts Institute of Technology
Other Authors:	Michel X. Goemans.
Format:	Thesis
Language:	eng
Published:	Massachusetts Institute of Technology 2014
Subjects:	Electrical Engineering and Computer Science.
Online Access:	http://hdl.handle.net/1721.1/85521

Similar Items

Dynamic Approximate Vertex Cover and Maximum Matching
by: Onak, Krzysztof, et al.
Published: (2012)

Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
by: Cheung, Wang Chi, et al.
Published: (2015)

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
by: Ghaffari, Mohsen, et al.
Published: (2021)

Maintaining a large matching and a small vertex cover
by: Onak, Krzysztof, et al.
Published: (2012)

Vertex sparsification and universal rounding algorithms
by: Moitra, Ankur
Published: (2011)

Experimental implementations of stereo matching algorithms in Halide
by: Zhang, Min, M. Eng. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science (2016)
Published: (2018)

Modeling problem solving in Massive Open Online Courses
by: Han, Fang, M. Eng. Massachusetts Institute of Technology
Published: (2014)

Algorithmically supported moderation in children's online communities
by: Tan, Flora, M. Eng. Massachusetts Institute of Technology
Published: (2018)

A near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size
by: Onak, Krzysztof, et al.
Published: (2012)

Probabilistic graphical models : distributed inference and learning models with small feedback vertex sets
by: Liu, Ying, Ph. D. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Published: (2014)

System architecture for mode-matching a MEMS gyroscope
by: Wu, Henry, M. Eng. Massachusetts Institute of Technology
Published: (2010)

Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios
by: Ma, Will, et al.
Published: (2023)

Hamiltonian cycle and related problems : vertex-breaking, grid graphs, and Rubik's Cubes
by: Rudoy, Mikhail
Published: (2018)

DNA Computing Technique to Solve Vertex Coloring Problem
by: Hasudungan, Rofilde, et al.
Published: (2013)

Matching scan paths for insights into the usability problems of online supermarkets
by: See Tho, Wai Loon
Published: (2015)

An Improved of Channel Allocation for WLAN Using Vertex Merge Algorithm
by: Mr, Handrizal, et al.
Published: (2012)

Kid's Survey Network : teaching data literacy with multiplayer online games
by: Wong, Christopher, M. Eng. Massachusetts Institute of Technology
Published: (2010)

On the vertex-oriented triangle propagation (VTP) algorithm : parallelization and approximation
by: Du, Jie, et al.
Published: (2021)

Cooperation and competition : modeling intention and behavior in dual-agent interactions
by: Zhang, Lily, M. Eng. Massachusetts Institute of Technology
Published: (2018)

Vertex Sparsifiers and Abstract Rounding Algorithms
by: Charikar, Moses, et al.
Published: (2013)

Visualizing remixes in an online programming community
by: Liu, Di, M. Eng. Massachusetts Institute of Technology
Published: (2014)

Automatically learning optimal formula simplifiers and database entity matching rules
by: Singh, Rohit, Ph. D. Massachusetts Institute of Technology
Published: (2018)

Algebraic Algorithms for Matching and Matroid Problems
by: Harvey, Nicholas J. A.
Published: (2010)

Minimum-correction second-moment matching : theory, algorithms and applications
by: Lin, Jing,Ph. D.Massachusetts Institute of Technology.
Published: (2020)

Existence of competitive equilibria in combinatorial auctions
by: Lee, Ji Young, Ph. D. Massachusetts Institute of Technology
Published: (2015)

An implementation of terrain geomorphing in the vertex shader for synthetic planetary surfaces
by: Colagiovanni, Lawrence W. (Lawrence William)
Published: (2009)

Online matching with its applications to ridesharing
by: Wang, Hao
Published: (2022)

Online Stochastic Matching: New Algorithms with Better Bounds
by: Jaillet, Patrick, et al.
Published: (2015)

Online learning algorithm for structural control using magnetorheological actuators
by: Laflamme, Simon, M. Eng. Massachusetts Institute of Technology
Published: (2007)

Tracking eye behavior in decision-making maze problems
by: Wang, Jing Xian,M. Eng.Massachusetts Institute of Technology.
Published: (2019)

Parallel Quick-Skip Search Hybrid Algorithm For The Exact String Matching Problem.
by: Naser, Mustafa Abdulsahib
Published: (2010)

An operadic approach to vertex algebra and Poisson vertex algebra cohomology
by: Kac, Victor
Published: (2020)

A study of the description matching problem.
by: Spencer, David Alan
Published: (2005)

Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path Based Formulation
by: Goyal, Vineet, et al.
Published: (2022)

Sublinear-time Parallel Algorithms for Matching and Related Problems
by: Goldberg, Andrew V., et al.
Published: (2023)

Comparison of natural language processing algorithms for medical texts
by: Chen, Michelle W., M. Eng. Massachusetts Institute of Technology
Published: (2015)

A note on the greedy approximation algorithm for the unweighted set covering problem
Published: (2003)

Algorithms and algorithmic obstacles for probabilistic combinatorial structures
by: Li, Quan, Ph. D. Massachusetts Institute of Technology
Published: (2018)

The vertex-to-vertex contact analysis in the two-dimensional discontinuous deformation analysis
by: Bao, Huirong, et al.
Published: (2013)

A study on pattern matching algorithms
by: Ng, Kee Wan.
Published: (2008)