In online sales, sellers usually offer each potential buyer a posted price in take-it-or-leave fashion. Buyers can sometimes see prices faced by other buyers, and changing the frequently could be considered unfair. The literature on posted-price mechanisms prophet inequality problems has studied two extremes of pricing policies, fixed-price policy fully dynamic pricing. former is suboptimal revenue but perceived as fairer than latter. This work examines middle situation, where there are at...

For some positive constant ϵ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> , we give a (3/2-ϵ )-approximation algorithm for the following problem: given graph G = (V,V ), find shortest tour that visits every vertex at least once. This is special case of metric traveling salesman problem when underlying defined by path distances in Go. The result improves on 3/2-approximation due to Christofides [13] this case. Similar Christofides, our...

In the Minimum Bounded Degree Spanning Tree problem, we aregiven an undirected graph with a degree upper bound Bv on eachvertex v, and task is to find spanning tree of minimumcost which satisfies all bounds. Let OPT be costof optimal solution this problem. paper, presenta polynomial time algorithm returns T ofcost at most dT(v) ≤ Bv+1 for where denotes v in T. This generalizes aresult Furer Raghavachari [8] weighted graphs, andsettles 15-year-old conjecture Goemans [10] affirmatively. The...

We study the problem of computing max-entropy distributions over a discrete set objects subject to observed marginals. There has been tremendous amount interest in such due their applicability areas as statistical physics, economics, biology, information theory, machine learning, combinatorics and algorithms. However, rigorous systematic how compute lacking. Since underlying can be exponential input size, first question is if have polynomially-sized descriptions. start by giving structural...

We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design constraints on vertices. objective to find a minimum cost subgraph which satisfies connectivity requirements between vertices also upper bounds $B_v$ This includes well-studied Minimum Bounded Degree Spanning Tree as special case. Our main result $(2,2B_v+3)$-approximation algorithm edge-connectivity constraints, where of...

In the Minimum Bounded Degree Spanning Tree problem, we are given an undirected graph G = ( V, E ) with a degree upper bound B v on each vertex ∈ V , and task is to find spanning tree of minimum cost that satisfies all bounds. Let OPT be optimal solution this problem. article present polynomial-time algorithm which returns T at most d ≤ + 1 for where denotes in . This generalizes result Fürer Raghavachari [1994] weighted graphs, settles conjecture Goemans [2006] affirmatively. The when has...

Linear programming (LP) has played a key role in the study of algorithms for combinatorial optimization problems. In field approximation algorithms, this is well illustrated by uncapacitated facility location problem. A variety algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to evolved from Unfortunately, collection powerful techniques had not yet applicable more general capacitated fact, all known with good performance guarantees were based on single...

Robust optimization has traditionally focused on uncertainty in data and costs problems to formulate models whose solutions will be optimal the worst-case among various uncertain scenarios model. While these approaches may thought of defining data- or cost-robust problems, we a new "demand-robust" model motivated by recent work two-stage stochastic problems. We propose this framework general covering prove structural lemma about special types first-stage for such problems: there exists...

We obtain the first online algorithms for node-weighted Steiner tree, forest and group tree problems that achieve a poly-logarithmic competitive ratio. Our algorithm problem runs in polynomial time, while those other two take quasi-polynomial time. can be viewed as LP rounding framework of Buchbinder Naor (Foundations Trends Theoretical Computer Science, 2009); however, natural formulation these do lead to fractional with ratio, we are unable round LPs without losing factor. Therefore,...

In the classical secretary problem an employer would like to choose best candidate among n competing candidates that arrive in a random order. each iteration, one candidate's rank vis-a-vis previously arrived is revealed and makes irrevocable decision about her selection. This basic concept of elements arriving order decisions made by algorithm have been explored extensively over years, used for modeling behavior many processes. Our main contribution new linear programming technique we...

Given a positive semidefinte matrix L whose columns and rows are indexed by set U, partition matroid M=(U, I), we study the problem of selecting basis B M such that determinant submatrix induced in is maximized. This appears many areas including determinantal point processes machine learning, experimental design, geographical placement problems, discrepancy theory computational geometry to model subset selection problems incorporate diversity.

Article Share on Survivable network design with degree or order constraints Authors: Lap Chi Lau The Chinese University of Hong Kong, Kong KongView Profile , Joseph (Seffi) Naor Technion, Haifa, Israel IsraelView Mohammad R. Salavatipour Alberta, Edmonton, Canada CanadaView Mohit Singh Carnegie Mellon University, Pittsburgh, PA PAView Authors Info & Claims STOC '07: Proceedings the thirty-ninth annual ACM symposium Theory computingJune 2007 Pages...

Relational database-as-a-service (DaaS) providers need to rely on multi-tenancy and resource sharing among tenants, since statically reserving resources for a tenant is not cost effective. A major consequence of that the performance one can be adversely affected by demands other co-located tenants. One such essential good tenant's workload buffer pool memory. In this paper, we study problem how effectively share memory in multi-tenant relational DaaS. We first develop an SLA framework...

We study the problem of allocating m items to n agents subject maximizing Nash social welfare (NSW) objective. write a novel convex programming relaxation for this problem, and we show that simple randomized rounding algorithm gives 1/e approximation factor objective, breaking 1/2e^(1/e) Cole Gkatzelis. Our main technical contribution is an extension Gurvits's lower bound on coefficient square-free monomial degree m-homogeneous stable polynomial variables all homogeneous polynomials. use...

Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In field approximation algorithms, this is well illustrated by uncapacitated facility location problem. A variety algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to evolved from Unfortunately, collection powerful techniques had not yet applicable more general capacitated fact, all known with good performance guarantees were based on single...

We study a general network design problem with additional degree constraints. Given connectivity requirements ruv for all pairs of vertices, Steiner is graph in which there are at least edge-disjoint paths between u and v vertices u,v. In the MINIMUM BOUNDED-DEGREE STEINER NETWORK problem, we given an undirected G edge cost each edge, requirement pair v, upper bound vertex v. The task to find minimum satisfies bounds.

We investigate whether the standard dimensionality reduction technique of PCA inadvertently produces data representations with different fidelity for two populations. show on several real-world sets, has higher reconstruction error population A than B (for example, women versus men or lower- higher-educated individuals). This can happen even when set a similar number samples from and B. motivates our study techniques which maintain define notion Fair give polynomial-time algorithm finding...