Approximation Algorithms via Contraction Decomposition by Hajiaghayi, Mohammad Taghi, Demaine, Erik D., Mohar, Bojan

Get full text
Get full text

Improved Approximation Algorithms for Projection Games by Manurangsi, Pasin, Moshkovitz Aaronson, Dana Hadar

“…In this paper we design several approximation algorithms for projection games: 1. A polynomial-time approximation algorithm that improves on the previous best approximation by Charikar, Hajiaghayi and Karloff [7]. 2. …”
Get full text
Get full text

Approximation Algorithms for Model-Based Compressive Sensing by Hegde, Chinmay, Indyk, Piotr, Schmidt, Ludwig

“…Moreover, an approximation algorithm is not sufficient for this optimization to provably succeed. …”
Get full text
Get full text
Get full text

Tight Approximation Algorithms for Maximum Separable Assignment Problems by Goemans, Michel X., Fleischer, Lisa, Mirrokni, Vahab, Sviridenko, Maxim

“…A polynomial-time LP-rounding based ((1 − 1/e)β)-approximation algorithm. ii. A simple polynomial-time local search (β/(β + 1) − ε)-approximation algorithm, for any ε > 0. …”
Get full text
Get full text

Approximation algorithms for capacitated stochastic inventory systems with setup costs by Shi, Cong, Zhang, Huanan, Chao, Xiuli, Levi, Retsef

“…We develop the first approximation algorithm with worst-case performance guarantee for capacitated stochastic periodic-review inventory systems with setup costs. …”
Get full text
Get full text

Sampling-Based Approximation Algorithms for Reachability Analysis with Provable Guarantees by Liebenwein, Lucas, Baykal, Cenk, Gilitschenski, Igor, Karaman, Sertac, Rus, Daniela L

Get full text
Get full text
Get full text
Get full text
Get full text

Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk by Hajiaghayi, MohammadTaghi, Kortsarz, Guy, Salavatipour, Mohammad R.

“…Thefirstnon-trivial approximation algorithm for this problem is due toCharikarand Karagiozova (STOC' 05) whose algorithm has anapproximation guarantee of$\exp(O(\sqrt{\log n\log\log n}))$,when all $\delta_i=1$ and$\exp(O(\sqrt{\log N\log\log N}))$ for the generaldemand case where $N$ isthe sum of all demands. …”
Get full text

Reducing Revenue to Welfare Maximization: Approximation Algorithms and Other Generalizations by Cai, Yang, Daskalakis, Konstantinos, Weinberg, Seth Matthew

“…In this paper, we extend the reduction to accommodate approximation algorithms, providing an approximation preserving reduction from (truthful) revenue maximization to (not necessarily truthful) welfare maximization. …”
Get full text
Get full text

A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees by Badoiu, Mihai, Indyk, Piotr, Sidiropoulos, Anastasios

Subjects: Get full text

Nonlinear Formations and Improved Randomized Approximation Algorithms for Multiway and Multicut Problems by Bertsimas, Dimitris J., Teo, Chungpiaw, Vohra, Rakesh

Get full text

Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size by Moitra, Ankur

“…Our structural results are motivated by the meta question: Suppose we are given a poly(log n) approximation algorithm for a flow or cut problem when can we give a poly(log k) approximation algorithm for a generalization of this problem to a Steiner cut or flow problem? …”
Get full text
Get full text

Approximation algorithms via structural results for apex-minor-free graphs by Demaine, Erik D., Hajiaghayi, Mohammad Taghi, Kawarabayashi, Ken-ichi

“…We develop new structural results for apex-minor-free graphs and show their power by developing two new approximation algorithms. The first is an additive approximation for coloring within 2 of the optimal chromatic number, which is essentially best possible, and generalizes the seminal result by Thomassen [32] for bounded-genus graphs. …”
Get full text
Get full text

A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees by Badoiu, Mihai, Indyk, Piotr, Sidiropoulos, Anastasios

Subjects: Get full text

Approximation algorithms and hardness results for the joint replenishment Problepm with constant demands by Telha Cornejo, Claudio A., Schulz, Andreas S

Get full text
Get full text

Approximation Algorithms for the Stochastic Lot-Sizing Problem with Order Lead Times by Levi, Retsef, Shi, Cong

Get full text
Get full text

A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix by Gamarnik, David, Rogozhnikov, Dmitriy A.

“…For a class of matrices corresponding to constant degree expanders we construct a deterministic polynomial time approximation algorithm to within a multiplicative factor ( 1 + ∈)[superscript η] for arbitrary∈ > 0. …”
Get full text
Get full text

Data-driven approximation algorithms for rapid performance evaluation and optimization of civil structures by Tseranidis, Stavros, Brown, Nathan Collin, Mueller, Caitlin T

“…This paper explores the use of data-driven approximation algorithms, often called surrogate modeling, in the early-stage design of structures. …”
Get full text
Get full text
Get full text
Get full text

Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms by Daskalakis, Konstantinos, Weinberg, Seth Matthew

“…Our mechanisms are obtained by establishing a polynomial-time approximation-sensitive reduction from the problem of designing approximately optimal mechanisms for some arbitrary objective O to that of designing bi-criterion approximation algorithms for the same objective O plus a linear allocation cost term. …”
Get full text
Get full text

An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem by Asadpour, Arash, Goemans, Michel X., Madry, Aleksander, Gharan, Shayan Oveis, Saberi, Amin

Get full text
Get full text
Get full text

Single Machine Scheduling with Release Dates by Goemans, Michel X., Queyranne, Maurice, Schulz, Andreas S., Skutella, Martin, Wang, Yaoguang

Subjects: “…approximation algorithm, LP relaxation, scheduling, online algorithm…”
Get full text