# Questions tagged [approximation-algorithms]

513 questions
Filter by
Sorted by
Tagged with
39 views

### Approximation ratio of randomized rounding for integral multi-commodity flow

In , Raghavan and Thompson showed that we can use randomized rounding to approximate integral multi-commodity flow and routing with congestion. The result is that suppose the optimal solution is $W$...
41 views

### Greedy rounding technique

I have an assignment problem-like structure with a bunch of additional constraints formulated as an integer linear program. By relaxing the integral constraint I ended up in a relaxed LP problem for ...
23 views

### Finding an algorithm EF[1,1] and PO division for more than two agents

From this research paper I want to write an algorithm for finding envy-freeness(EF) and Pareto optimality(PO) division for more than two agents. We consider the problem of fairly and efficiently ...
1 vote
237 views

43 views

### Submodulare welfare maximization: is an additive approximation algorithm known?

Sudmodular welfare maximization is the problem of allocating items among agents with different valuations, represented by submodular set functions, such that the sum of agents' values is as large as ...
332 views

### A k-approximation to k-way number partitioning

The $k$-way number partitioning problem accepts as input a multiset $S$ of positive numbers, and returns a partition of $S$ into $k$ subsets such that the subset sums are as nearly-equal as possible, ...
25 views

### Understanding the transition rule for the Markov chain in the JSV algorithm for approximating the permanent

I was making my way through the paper by Jerrum, Sinclair, and Vigoda on developing a randomized polynomial time procedure (FRPAS) for approximating the permanent of a matrix $A$ with non-negative ...
147 views

### Finding $k \times k$ rectangle in a matrix with maximum sum

Given an $n \times n$ matrix $A$ with $0-1$ entries, I want to maximize $\sum\limits_{i \in I, j \in J} a_{ij}$ subject to $|I| = |J| = k.$ I expect the problem to be NP-hard, so I want a polynomial ...
56 views

### Generalized assignment problem with overall budget

The problem has N tasks. We have M workers. We have the cost of assigning task i to worker j. We have a profit for assigning task i to worker j. We want to assign each task to exactly one worker. One ...
342 views

1k views

### Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed

The MAX-CUT problem has constant factor approximation, but we can't control the sizes of the sets in resulting partition. What is known about maximizing cut size, if we restrict one part of the ...
893 views

### Maximizing difference of a submodular and a modular function

I'm considering a network planning problem which is stated as follows: From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that \begin{equation} f(\mathcal{A}) - \...
190 views

### Hashing-based vs almost uniform sampling-based approximate counting

Corollary 3.6 in the UniqueSAT paper by Valiant and Vazirani  states: For any $\varepsilon > 0$ there is a randomized polynomial-time TM with a SAT oracle, which given a SAT formula $f$ outputs ...
58 views

### Submodular welfare maximization: what is the best known approximation ratio of a deterministic algorithm?

In the submodular welfare maximization problem, there is a set $M$ of items that should be partitioned among $n$ agents. Each agent $i$ has a value function $v_i: 2^M\to \mathbb{R}_+$. All value ...
45 views

### Maximum independent set in "subgraph-claw-free" graphs

A $d$-claw in a graph is a set of $d+1$ vertices, one of which (the "center") is connected to the other $d$, but the other $d$ are not connected to each other. A graph is called $d$-claw ...
68 views

### Proper terminology for input, parameter or variable fixing. Refinement? Projection? Fixation? Partial valuation?

I contemplate writing a paper on automating fixing some inputs/parameters to specific values in a kind of workflow/pipeline definition language/system and looking for best terminology. English is not ...
360 views

### Partition a graph into two clusters

Suppose given a complete weighted graph $G=(V,E)$, Is there an algorithm that partition $G$ into two clusters $C_1,C_2$ such that sum of heaviest edges in $C_1,C_2$ minimized? Note that, heaviest edge ...
23 views

### Is there a theoretical runtime guarantee to eigen decomposition (up to some convergence distance)?

I'm familiar with the QR algorithm for eigen decomposition in symmetric matrices, which takes roughly O(n^3) time. But that O(n^3) only holds if you take a constant number of QR steps per eigenvalue, ...
1 vote
52 views

### Better approximation of the subset in the membership oracle

A standard tool for estimating the size of a subset via membership oracle queries is given below. Lemma 2.8: . Consider two (finite) sets $B ⊆ U$, where $n = |U|$. Let $ε ∈ (0, 1)$ and $γ ∈ (0, 1/2)$ ...
1 vote
71 views

### How to enforce convexity?

I have a problem for which the solution is known to be a convex $f:[a,b]\times[c,d] \rightarrow \mathbb{R}$ over some rectangular domain ($a<b$ and $c<d$). There are many situations (e.g. ...