NDLI: MaxMin allocation via degree lower-bounded arborescences

Please wait, while we are loading the content...

Message passing algorithms and improved LP decoding

Exact learning of random DNF over the uniform distribution

An efficient algorithm for partial order production

New direct-product testers and 2-query PCPs

Fully homomorphic encryption using ideal lattices

Approximating edit distance in near-linear time

Finding sparse cuts locally using evolving sets

Integrality gaps for Sherali-Adams relaxations

Public-key cryptosystems from the worst-case shortest vector problem: extended abstract

Universally utility-maximizing privacy mechanisms

Quantum algorithms using the curvelet transform

Affiliation networks

On the complexity of communication complexity

A new approach to auctions and resilient mechanism design

How long does it take to catch a wild kangaroo?

Non-malleable extractors and symmetric key cryptography from weak secrets

Every planar graph is the intersection graph of segments in the plane: extended abstract

A constant-factor approximation for stochastic Steiner forest

An axiomatic approach to algebrization

The work of Leslie Valiant

List decoding tensor products and interleaved codes

Polynomial-time theory of matrix groups

A nearly optimal oracle for avoiding failed vertices and edges

On proximity oblivious testing

A unified framework for concurrent security: universal composability from stand-alone non-malleability

Numerical linear algebra in the streaming model

On the geometry of graphs with a forbidden minor

Sherali-adams relaxations of the matching polytope

A constructive proof of the Lovász local lemma

Private coresets

Short seed extractors against quantum storage

Fault-tolerant spanners for general graphs

Bit-probe lower bounds for succinct data structures

Intrinsic robustness of the price of anarchy

Random walks on polytopes and an affine interior point method for linear programming

Inaccessible entropy

Small-size ε-nets for axis-parallel rectangles and boxes

Multiple intents re-ranking

Random graphs and the parity quantifier

Athena lecture: Controlling Access to Programs?

Artin automorphisms, cyclotomic function fields, and folded list-decodable codes

Affine dispersers from subspace polynomials

Distributed (δ+1)-coloring in linear (in δ) time

Testing juntas nearly optimally

Non-malleability amplification

A fast and efficient algorithm for low-rank approximation of a matrix

Twice-ramanujan sparsifiers

CSP gaps and reductions in the lasserre hierarchy

Differential privacy and robust statistics

Efficient discrete-time simulations of continuous-time quantum query algorithms

Hadwiger's conjecture is decidable

Randomly supported independence and resistance

On the convergence of regret minimization dynamics in concave games

Mixing time for the solid-on-solid model

On cryptography with auxiliary input

Explicit construction of a small epsilon-net for linear threshold functions

A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation

Holant problems and counting CSP

A deterministic reduction for the gap minimum distance problem: [extended abstract]

On oblivious PTAS's for nash equilibrium

Near-perfect load balancing by randomized rounding

Green's conjecture and testing linear-invariant properties

An improved constant-time approximation algorithm for maximum~matchings

Max cut and the smallest eigenvalue

Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems

On the complexity of differentially private data release: efficient algorithms and hardness results

The detectability lemma and quantum gap amplification

Finding, minimizing, and counting weighted subgraphs

Conditional hardness for satisfiable 3-CSPs

Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract

Reconstruction for the Potts model

Online and stochastic survivable network design

A new line of attack on the dichotomy conjecture

3-query locally decodable codes of subexponential length

The extended BG-simulation and the characterization of t-resiliency

Homology flows, cohomology cuts

Non-monotone submodular maximization under matroid and knapsack constraints

MaxMin allocation via degree lower-bounded arborescences

Tight lower bounds for greedy routing in uniform small world rings

MaxMin allocation via degree lower-bounded arborescences

Content Provider	ACM Digital Library
Author	Bateni, MohammadHossein Charikar, Moses Guruswami, Venkatesan
Abstract	We consider the problem of MaxMin allocation of indivisible goods. There are m items to be distributed among n players. Each player \$i\$ has a nonnegative valuation $p_{ij}$ for an item j, and the goal is to allocate items to players so as to maximize the minimum total valuation received by each player. There is a large gap in our understanding of this problem. The best known positive result is an ~O(√ n)-approximation algorithm, while there is only a factor 2 hardness known. Better algorithms are known for the restricted assignment case where each item has exactly one nonzero value for the players. We study the effect of bounded degree for items: each item has a nonzero value for at most D players. We show that essentially the case D = 3 is equivalent to the general case, and give a 4-approximation algorithm for D = 2. The current algorithmic results for MaxMin Allocation are based on a complicated LP relaxation called the configuration LP. We present a much simpler LP which is equivalent in power to the configuration LP. We focus on a special case of MaxMin Allocation-a family of instances on which this LP has a polynomially large gap. The technical core of our result for this case comes from an algorithm for an interesting new optimization problem on directed graphs, MaxMinDegree Arborescence, where the goal is to produce an arborescence of large outdegree. We develop an $n^{ε}-approximation$ for this problem that runs in $n^{O(1/ε)}$ time and obtain a a polylogarithmic approximation that runs in quasipolynomial time, using a lift-and-project inspired LP formulation. In fact, we show that our results imply a rounding algorithm for the relaxations obtained by t rounds of the Sherali-Adams hierarchy applied to a natural LP relaxation of the problem. Roughly speaking, the integrality gap of the relaxation obtained from t rounds of Sherali-Adams is at most $n^{1/t}.$ We are able to extend the latter result to a more general class of instances. Along the way, we prove a result about the existence of a perfect matching in a probabilistically pruned graph which may be of independent interest.
Starting Page	543
Ending Page	552
Page Count	10
File Format	PDF
ISBN	9781605585062
DOI	10.1145/1536414.1536488
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-05-31
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Approximation algorithms Graphs Linear programming Lift-and-project
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in