On extensions of the deterministic online model for bipartite matching and max-sat
From MaRDI portal
Publication:1740687
DOI10.1016/j.tcs.2018.10.015zbMath1422.68325OpenAlexW2897485334WikidataQ129085544 ScholiaQ129085544MaRDI QIDQ1740687
Publication date: 2 May 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2018.10.015
Related Items
An Experimental Study of Algorithms for Online Bipartite Matching ⋮ Advice complexity of priority algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Toward a model for backtracking and dynamic programming
- Greedy matching: guarantees and limitations
- Online computation with advice
- Models of greedy algorithms for graph problems
- Simplified tight analysis of Johnson's algorithm
- Randomized priority algorithms
- Priority algorithms for graph optimization problems
- Approximation algorithms for combinatorial problems
- Tight bound on Johnson's algorithm for maximum satisfiability
- Erratum to: ``Greedy matching: guarantees and limitations
- (Incremental) priority algorithms
- On graph problems in a semi-streaming model
- An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
- Simpler 3/4-Approximation Algorithms for MAX SAT
- Online Stochastic Matching: Online Actions Based on Offline Statistics
- Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization
- On the Advice Complexity of the k-Server Problem
- Bounds on Greedy Algorithms for MAX SAT
- Submodular Max-SAT
- A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
- Data Streams: Algorithms and Applications
- Improved Bounds for Online Stochastic Matching
- New Algorithms for Bin Packing
- Randomized greedy matching. II
- Deterministic Algorithms for Submodular Maximization Problems
- An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
- Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
- Online Stochastic Matching: Beating 1-1/e
- Online Stochastic Matching: New Algorithms with Better Bounds
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- Online bipartite matching with unknown distributions
- Online bipartite matching with random arrivals
- Some optimal inapproximability results
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching
- Approximation and Online Algorithms
- On conceptually simple algorithms for variants of online bipartite matching
This page was built for publication: On extensions of the deterministic online model for bipartite matching and max-sat
