The G-Convexity and the G-Centroids of Composite Graphs by Prakash Veeraraghavan

“…Thus, it is necessary to devise an approximation algorithm for general graphs and polynomial-time algorithms for some special classes of graphs. …”
Get full text

Regularity and removal lemmas and their applications by Lovász, László Miklós

Get full text

Robust Dynamic Pricing with Strategic Customers by Chen, Yiwei, Farias, Vivek F.

“…We thus provide the first approximation algorithm for this problem. The robust pricing mechanism is practical, since it is an anonymous posted price mechanism and since the seller can compute the robust pricing policy for a problem without any knowledge of the distribution of customer discount factors and monitoring costs. …”
Get full text
Get full text

The Stackelberg Minimum Spanning Tree Game by Cardinal, Jean, Demaine, Erik D, Fiorini, Samuel, Joret, Gwenaël, Langerman, Stefan, Newman, Ilan, Weimann, Oren

“…In particular, we prove that the problem is APX-hard even if there are only two different red costs, and give an approximation algorithm whose approximation ratio is at most min {k,1+ln b,1+ln W}, where k is the number of distinct red costs, b is the number of blue edges, and W is the maximum ratio between red costs. …”
Get full text

A continuous analogue of the tensor-train decomposition by Gorodetsky, Alex, Karaman, Sertac, Marzouk, Youssef M.

“…We develop new approximation algorithms and data structures for representing and computing with multivariate functions using the functional tensor-train (FT), a continuous extension of the tensor-train (TT) decomposition. …”
Get full text

Revenue Maximization and Ex-Post Budget Constraints by Daskalakis, Konstantinos, Devanur, Nikhil R., Weinberg, S. Matthew

“…Our main technical contribution is a computationally efficient 3-approximation algorithm for the algorithmic problem that results from an application of their framework to this problem. …”
Get full text

Outer approximation with conic certificates for mixed-integer convex problems by Coey, Chris, Lubin, Miles, Vielma, Juan P

“…We present a branch-and-bound LP outer approximation algorithm for an MI-convex problem transformed to MI-conic form. …”
Get full text

Sparse classification: a scalable discrete optimization perspective by Bertsimas, Dimitris J, Pauphilet, Jean, Van Parys, Bart Paul Gerard

“…Consequently, on numerous real-world experiments, our outer-approximation algorithms returns sparser classifiers while achieving similar predictive accuracy as Lasso. …”
Get full text

Data-Driven Approximation Schemes for Joint Pricing and Inventory Control Models by Qin, Hanzhang, Simchi-Levi, David, Wang, Li

“…We propose a data-driven approximation algorithm that uses precollected demand data to solve the joint pricing and inventory control problem. …”
Get full text

A computational study of a geometric embedding of minimum multiway cut by Shin, David (David Donghun)

Get full text

Approximate inference : decomposition methods with applications to networks by Jung, Kyomin

Get full text

Node-weighted Steiner tree and group Steiner tree in planar graphs by Demaine, Erik D., Hajiaghayi, Mohammad Taghi, Klein, Philip N.

“…We obtain an O(log n polyloglog n) approximation algorithm for the special case where the graph is planar embedded and each group is the set of nodes on a face. …”
Get full text
Get full text

Approximating the influence of monotone boolean functions in O(√n) query complexity by Ron, Dana, Rubinfeld, Ronitt, Safra, Muli, Weinstein, Omri

Get full text
Get full text

PTAS for maximum weight independent set problem with random weights in bounded degree graphs by Gamarnik, David, Goldberg, David A., Weber, Theophane G.

“…Moreover, even for graphs with largest degree 3, no polynomial time approximation algorithm exists with a 1.0071-factor approximation guarantee, unless P = NP [BK98]. …”
Get full text
Get full text

An asymptotically optimal algorithm for pickup and delivery problems by Pavone, Marco, Frazzoli, Emilio, Treleaven, Kyle Ballantyne

“…The SCP is NP-Hard and the best know approximation algorithm only provides a 9/5 approximation ratio. …”
Get full text
Get full text

The submodular joint replenishment problem by Cheung, Maurice, Elmachtoub, Adam N., Levi, Retsef, Shmoys, David B.

“…For the tree and cardinality cases, we provide two different linear programming based approximation algorithms that provide guarantees of three and five, respectively.…”
Get full text
Get full text

Retrieving regions of interest for user exploration by Cao, Xin, Cong, Gao, Jensen, Christian S., Yiu, Man Lung

“…We develop an approximation algorithm with a (5 + ε) approximation ratio utilizing a technique that scales node weights into integers. …”
Get full text
Get full text
Get full text

Approximation approaches for solving security games with surveillance cost : a preliminary study by Guo, Qingyu, An, Bo, Kolobov, Andrey

“…We also propose an iterative deepening based approximation algorithm. Experimental results show that these approaches can solve much larger security games with surveillance cost.…”
Get full text
Get full text

Multi-relation graph summarization by Ke, Xiangyu, Khan, Arijit, Bonchi, Francesco

“…In doing this, as a side contribution, we provide the first polynomial-time approximation algorithm based on the k-Median clustering for the classic problem of lossless single-relation graph summarization. …”
Get full text

Busy-time scheduling on heterogeneous machines: algorithms and analysis by Liu, Mozhengfu, Tang, Xueyan

“…We develop an O(1)-approximation algorithm in the offline setting and an O(μ)-competitive algorithm in the online setting (where μ is the max/min job length ratio), both of which are asymptotically optimal. …”
Get full text