BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Bartosz Rybicki

Bartosz Rybicki contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete Mathematics

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

4 published item(s)

preprint2016arXiv

A $4/5$ - Approximation Algorithm for the Maximum Traveling Salesman Problem

In the maximum traveling salesman problem (Max TSP) we are given a complete undirected graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour of maximum weight. We present a fast combinatorial $\frac 45$ - approximation algorithm for Max TSP. The previous best approximation for this problem was $\frac 79$. The new algorithm is based on a novel technique of eliminating difficult subgraphs via half-edges, a new method of edge coloring and a technique of exchanging edges. A half-edge of edge $e=(u,v)$ is informally speaking "a half of $e$ containing either $u$ or $v$".

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

An Improved Approximation for $k$-median, and Positive Correlation in Budgeted Optimization

Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to \emph{negative correlation} properties. However, what if an application naturally calls for dependent rounding on the one hand, and desires \emph{positive} correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding, but also have nearly best-possible behavior - near-independence, which generalizes positive correlation - on "small" subsets of the variables. The recent breakthrough of Li & Svensson for the classical $k$-median problem has to handle positive correlation in certain dependent-rounding settings, and does so implicitly. We improve upon Li-Svensson's approximation ratio for $k$-median from $2.732 + ε$ to $2.675 + ε$ by developing an algorithm that improves upon various aspects of their work. Our dependent-rounding approach helps us improve the dependence of the runtime on the parameter $ε$ from Li-Svensson's $N^{O(1/ε^2)}$ to $N^{O((1/ε) \log(1/ε))}$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An approximation algorithm for Uniform Capacitated k-Median problem with 1 + ε capacity violation

We study the Capacitated k-Median problem, for which all the known constant factor approximation algorithms violate either the number of facilities or the capacities. While the standard LP-relaxation can only be used for algorithms violating one of the two by a factor of at least two, Shi Li [SODA'15, SODA'16] gave algorithms violating the number of facilities by a factor of 1+ε exploring properties of extended relaxations. In this paper we develop a constant factor approximation algorithm for Uniform Capacitated k-Median violating only the capacities by a factor of 1+ε. The algorithm is based on a configuration LP. Unlike in the algorithms violating the number of facilities, we cannot simply open extra few facilities at selected locations. Instead, our algorithm decides about the facility openings in a carefully designed dependent rounding process.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Improved approximation algorithm for Fault-Tolerant Facility Placement

We consider the Fault-Tolerant Facility Placement problem ($FTFP$), which is a generalization of the classical Uncapacitated Facility Location problem ($UFL$). In the $FTFP$ problem we have a set of clients $C$ and a set of facilities $F$. Each facility $i \in F$ can be opened many times. For each opening of facility $i$ we pay $f_i \geq 0$. Our goal is to connect each client $j \in C$ with $r_j \geq 1$ open facilities in a way that minimizes the total cost of open facilities and established connections. In a series of recent papers $FTFP$ was essentially reduced to $FTFL$ and then to $UFL$ showing it could be approximated with ratio $1.575$. In this paper we show that $FTFP$ can actually be approximated even better. We consider approximation ratio as a function of $r = min_{j \in C} r_j$ (minimum requirement of a client). With increasing $r$ the approximation ratio of our algorithm $λ_r$ converges to one. Furthermore, for $r > 1$ the value of $λ_r$ is less than 1.463 (hardness of approximation of $UFL$). We also show a lower bound of 1.278 for the approximability of the Fault-Tolerant Facility Location problem ($FTFL$) for arbitrary $r$. Already for $r > 3$ we obtain that $FTFP$ can be approximated with ratio 1.275, showing that under standard complexity theoretic assumptions $FTFP$ is strictly better approximable than $FTFL$.

0 citations0 reviewsNo code linkedOpen access